All Questions
Tagged with binomial-coefficients combinatorics
3,233
questions
99
votes
4
answers
13k
views
Identity for convolution of central binomial coefficients: $\sum\limits_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$
It's not difficult to show that
$$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$
On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...
- 1,520
91
votes
9
answers
106k
views
Combinatorial proof of summation of $\sum\limits_{k = 0}^n {n \choose k}^2= {2n \choose n}$
I was hoping to find a more "mathematical" proof, instead of proving logically $\displaystyle \sum_{k = 0}^n {n \choose k}^2= {2n \choose n}$.
I already know the logical Proof:
$${n \choose k}^2 = {...
- 911
77
votes
20
answers
24k
views
Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$
After reading this question, the most popular answer use the identity
$$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1},$$
or, what is equivalent,
$$\sum_{t=k}^n \binom{t}{k} = \binom{n+1}{k+1}.$$
What's ...
- 1,620
74
votes
2
answers
7k
views
Combinatorial proof that $\sum \limits_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$ when $n$ is even
In my answer here I prove, using generating functions, a statement equivalent to
$$\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} (-1)^k = 2^n \binom{n}{n/2}$$
when $n$ is even. (Clearly the sum is $...
- 55.8k
71
votes
2
answers
51k
views
A comprehensive list of binomial identities?
Is there a comprehensive resource listing binomial identities? I am more interested in combinatorial proofs of such identities, but even a list without proofs will do.
user813
53
votes
2
answers
11k
views
How to reverse the $n$ choose $k$ formula?
If I want to find how many possible ways there are to choose k out of n elements I know you can use the simple formula below:
$$ \binom{n}{k} = \frac{n! }{ k!(n-k)! } .$$
What if I want to go the ...
- 831
47
votes
6
answers
78k
views
Expected Value of a Binomial distribution?
If $\mathrm P(X=k)=\binom nkp^k(1-p)^{n-k}$ for a binomial distribution, then from the definition of the expected value
$$\mathrm E(X) = \sum^n_{k=0}k\mathrm P(X=k)=\sum^n_{k=0}k\binom nkp^k(1-p)^{n-k}...
user31280
45
votes
6
answers
2k
views
You have to estimate $\binom{63}{19}$ in $2$ minutes to save your life.
This is from the lecture notes in this course of discrete mathematics I am following.
The professor is writing about how fast binomial coefficients grow.
So, suppose you had 2 minutes to save ...
- 467
45
votes
3
answers
2k
views
Solutions to $\binom{n}{5} = 2 \binom{m}{5}$
In Finite Mathematics by Lial et al. (10th ed.), problem 8.3.34 says:
On National Public Radio, the Weekend Edition program posed the
following probability problem: Given a certain number of ...
- 9,076
44
votes
3
answers
10k
views
How do I count the subsets of a set whose number of elements is divisible by 3? 4?
Let $S$ be a set of size $n$. There is an easy way to count the number of subsets with an even number of elements. Algebraically, it comes from the fact that
$\displaystyle \sum_{k=0}^{n} {n \...
- 432k
41
votes
7
answers
9k
views
Beautiful identity: $\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$
Let $m,n\ge 0$ be two integers. Prove that
$$\sum_{k=m}^n (-1)^{k-m} \binom{k}{m} \binom{n}{k} = \delta_{mn}$$
where $\delta_{mn}$ stands for the Kronecker's delta (defined by $\delta_{mn} = \begin{...
- 11.9k
41
votes
5
answers
13k
views
The Hexagonal Property of Pascal's Triangle
Any hexagon in Pascal's triangle, whose vertices are 6 binomial coefficients surrounding any entry, has the property that:
the product of non-adjacent vertices is constant.
the greatest common ...
- 4,139
40
votes
4
answers
6k
views
Combinatorial interpretation of Binomial Inversion
It is known that if $f_n = \sum\limits_{i=0}^{n} g_i \binom{n}{i}$ for all $0 \le n \le m$, then $g_n = \sum_{i=0}^{n} (-1)^{i+n} f_i \binom{n}{i}$ for $0 \le n \le m$. This sort of inversion is ...
- 6,265
34
votes
12
answers
39k
views
Proving Pascal's Rule : ${{n} \choose {r}}={{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$
I'm trying to prove that ${n \choose r}$ is equal to ${{n-1} \choose {r-1}}+{{n-1} \choose r}$ when $1\leq r\leq n$.
I suppose I could use the counting rules in probability, perhaps combination= ${{n}...
user6639
34
votes
1
answer
2k
views
A Combinatorial Proof of Dixon's Identity
Dixon's Identity states:
$$ \sum_{k} (-1)^k\binom {a+b}{b+k}\binom{b+c}{c+k}\binom{c+a}{a+k} = \binom{a+b+c}
{a,b,c}$$
A bit of history:
The case $a=b=c$ was proved by Dixon in 1891 using ...
- 6,265