# Questions tagged [combinatorial-proofs]

Combinatorial proofs of identities use double counting and combinatorial characterizations of binomial coefficients, powers, factorials etc. They avoid complicated algebraic manipulations.

364 questions
6k views

563 views

### Help with combinatorial proof of identity: $\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$

How to prove this identity? Can someone please give me some insight ? $$\sum_{k=1}^{n} \frac{(-1)^{k+1}}{k} \binom{n}{k} = \sum_{k=1}^{n} \frac{1}{k}$$
635 views

2k views

### Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$

Show that $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$. In the LHS $\binom{n+r-1}{r}$ counts the number of ways of selecting $r$ objects from a set of size $n$ where ...
91 views

### Binomial sum which adds to $2^n n!$

I'm looking for a combinatorial interpretation for the identity $$\sum_{k=0}^n\binom nk (2k-1)!!\,(2n - 2k - 1)!! = 2^n n!$$ where $(2n - 1)!! = (2n - 1)(2n - 3) \cdots 5 \cdot 3 \cdot 1$. ...
162 views

### Bijection between perfect matchings permutations with even cycles

It is possible to proof that the number of perfect matching on a set of $2n$ elements is $n!!$, and on the other hand, it is also possible to proof that the number of permutations $\varphi$ of a set ...
1k views

### Prove this using counting techniques: $\sum_{k=0}^{n}{\binom{2n+1}k} = 2^{2n}$

I recently came across a question while studying for an exam. I haven't been able to solve it. We had to prove: $$\sum_{k=0}^{n}{2n+1\choose k} = 2^{2n}$$ We had to use counting techniques. This was ...
### A combinatorial proof of the identity: $\sum_{k=1}^n k \binom{n}{k}^2 = {n}\binom{2n-1}{n-1}$?
Give a combinatorial proof of the identity: $$\sum_{k=1}^n k \binom{n}{k}^2 = {n}\binom{2n-1}{n-1}$$ I am not exactly sure where to start. Since $\binom{n}{k}^2 = \binom{n}{k}\binom{n}{k}$, thus, ...