All Questions
Tagged with combinatorics number-theory
276
questions
6
votes
1
answer
990
views
Is there any perfect squares that are also binomial coefficients?
Examining the Tartaglia's triangle, I have observed that all the squares were the trivial cases, that is, $\binom{n^2}1$ or $\binom{n^2}{n^2-1}$.
More formally:
Conjecture: If $\binom nm=k^2$ then $...
- 65.9k
6
votes
3
answers
236
views
How to prove $\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$
Please help me to prove $\sum\limits_{i=0}^{\lfloor r/2\rfloor}\binom{r}{i}\binom{r-i}{r-2i}2^{r-2i}=\binom{2r}{r}$. By computer search I have found these for r varies from 0 to 10000. How to prove ...
- 159
6
votes
2
answers
5k
views
Same number of partitions of a certain type?
Is there a quick explanation of why the number of partitions of $n$ such that no parts are divisible by $d$ is the same as the number of partitions of $n$ where no part is repeated $d$ or more times, ...
- 63
4
votes
2
answers
403
views
Maximum run in binary digit expansions
For numbers between $2^{k-1}$ and $2^{k}-1$, how many have a maximum run of $n$ identical digits in base $2$? For instance, $1000110101111001$ in base $2$ has a maximum run of 4.
See picture below ...
- 3,645
3
votes
2
answers
127
views
$\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}=0, n>m\geq 0$
I got quite some trouble trying to prove this.
$$\sum_{k=m}^{n}(-1)^k\binom{n}{k}\binom{k}{m}=0, n>m\geq 0$$
I tried using $$\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$$ and then ...
- 378
2
votes
1
answer
365
views
Efficient computation of $\sum_{i=1}^{i=\left \lfloor {\sqrt{N}} \right \rfloor}\left \lfloor \frac{N}{i^{2}} \right \rfloor$
I have tried to find a closed form but did not succeed but is there an efficient way to calculate the following expression
$\sum_{i=1}^{i=\left \lfloor {\sqrt{N}} \right \rfloor}\left \lfloor \frac{N}...
- 37
0
votes
1
answer
1k
views
Polya's formula for determining the number of six-sided dice
Use Polya's enumeration to determine the number of six-sided dice that can be manufactured if each of three different labels must be placed on two of the faces.
Can you help me please to solve this ...
- 6,840
29
votes
3
answers
3k
views
When is $\binom{2n}{n}\cdot \frac{1}{2n}$ an integer?
In a recent question here, asking about the number of necklaces of $n$ white and $n$ black beads (reworded in terms of apples and oranges), one of the naive and incorrect answers was that as there are ...
- 80.2k
18
votes
1
answer
6k
views
What is the number of Sylow p subgroups in $S_p$?
I am reading the Wikipedia article entitiled Sylow theorems. This short segment of the article reads:
Part of Wilson's theorem states that
$(p-1)!$ is congruent to $-1$ (mod $p$) for every prime $p$....
- 3,711
15
votes
1
answer
8k
views
How to find the smallest number with just $0$ and $1$ which is divided by a given number?
Every positive integer divide some number whose representation (base $10$) contains only zeroes and ones. One can easily prove that using pigeonhole principle.
...
- 395
15
votes
4
answers
1k
views
When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?
Also asked on MathOverflow: When is the number of areas obtained by cutting a circle with $n$ chords a power of $2$?
Introduction
Recently, a friend told me about the following interesting fact:
...
- 13.8k
11
votes
3
answers
1k
views
Summation with combinations
Prove that $n$ divides $$\sum_{d \mid \gcd(n,k)} \mu(d) \binom{n/d}{k/d}$$ for every natural number $n$ and for every $k$ where $1 \leq k \leq n.$ Note: $\mu(n)$ denotes the Möbius function.
I have ...
- 15.6k
11
votes
5
answers
13k
views
How many non-negative integer solutions does the equation $3x + y + z = 24$ have?
If the equation is $x + y + z = 24$ then it is solvable with stars and bars theorem. But what to do if it is $3x + y + z = 24$?
- 3,146
11
votes
8
answers
17k
views
Proof of binomial coefficient formula.
How can we prove that the number of ways choosing $k$ elements among $n$ is $\frac{n!}{k!(n-k)!} = \binom{n}{k}$ with $k\leq n$?
This is an accepted fact in every book but i couldn't find a ...
- 9,173
7
votes
0
answers
189
views
Combinatorial interpretation of rational function on e
Over the last few weeks I have become obsessed with expressions like
$$
\frac{e+4 e^{2}+e^{3}}{(1-e)^{4}},
$$
$$
\frac{e+26 e^{2}+66 e^{3}+26 e^{4}+e^{5}}{(1-e)^{6}},
$$
or
$$
\frac{e+120 e^{2}+1191 e^...
