Combinatorial Proofs

Give a combinatorial proof of the identity $2+2+2 = 3\cdot 2$.

Give a combinatorial proof for the identity $1 + 2 + 3 + \cdots + n = {n+1 \choose 2}$.

A woman is getting married. She has 15 best friends but can only select 6 of them to be her bridesmaids, one of which needs to be her maid of honor. How many ways can she do this?

1. What if she first selects the 6 bridesmaids, and then selects one of them to be the maid of honor?

2. What if she first selects her maid of honor, and then 5 other bridesmaids?

3. Explain why $6 {15 \choose 6} = 15 {14 \choose 5}$.

Give a combinatorial proof of the identity ${n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}$.

How many ways are there to rearrange the letters in the word “rearrange”? Answer this question in at least two different ways to establish a binomial identity.

Give a combinatorial proof for the identity $P(n,k) = {n \choose k}k!$

Establish the identity below using a combinatorial proof.

In each polynomial below, assume $x$ is some variable. Use the binomial theorem to expand and reduce modulo the appropriate number:

1. $(x+1)^2 \pmod 2$
2. $(x+1)^5 \pmod 5$
3. $(x+1)^7 \pmod 7$

Prove that $(x+1)^p \equiv x^p + 1 \pmod p$ for any prime $p$.