Graph Theory/Juggling with Binomial Coefficients

Introduction

Fluency with binomial coefficients is a great help in combinatorial arguments about graphs. You should learn to juggle with binomial coefficients as easily as you juggle with normal algebraic equations.

Techniques

• Substitute specific values in the general equations, e.g. careful choice of x and y in:

$(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}.$

• Sledgehammer proof using recursion formula. You may find it helpful to 'chase' binomial coefficients on a diagram of Pascal's triangle.
• Differentiation of a previous identity to get a new one.
• Combinatorial arguments about permutations and combinations.

Worked Examples

Example: 2n To get: $\sum _{k=0}^{n}{\tbinom {n}{k}}=2^{n}$ Put $\displaystyle x=1{\text{ and }}y=1$ in $(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}.$

The Identities

${\binom {n}{k}}={\binom {n}{n-k}}$

${\binom {n}{k}}={\frac {n}{k}}{\binom {n-1}{k-1}}$

${\binom {n-1}{k}}-{\binom {n-1}{k-1}}={\frac {n-2k}{n}}{\binom {n}{k}}.$

${n \choose k}={n-1 \choose k-1}+{n-1 \choose k}$

$\displaystyle \sum _{k=0}^{n}{\tbinom {n}{k}}^{2}={\tbinom {2n}{n}}.$

$\displaystyle \sum _{k=0}^{n}{\tbinom {n}{k}}{\tbinom {n}{n-k}}={\tbinom {2n}{n}}.$

$\sum _{k=0}^{n}k{\tbinom {n}{k}}=n2^{n-1}$

$\sum _{k=0}^{n}k^{2}{\tbinom {n}{k}}=(n+n^{2})2^{n-2}$

$\sum _{m=0}^{n}{\tbinom {m}{j}}{\tbinom {n-m}{k-j}}={\tbinom {n+1}{k+1}}$

$\sum _{m=0}^{n}{\tbinom {m}{k}}={\tbinom {n+1}{k+1}}\,.$

$\sum _{k=0}^{\lfloor {\frac {n}{2}}\rfloor }{\tbinom {n-k}{k}}=F(n+1)$

where F(n) denote the n^th Fibonacci number.

$\sum _{j=k}^{n}{\tbinom {j}{k}}={\tbinom {n+1}{k+1}}$

$\sum _{j=0}^{k}(-1)^{j}{\tbinom {n}{j}}=(-1)^{k}{\tbinom {n-1}{k}}$

$\sum _{j=0}^{n}(-1)^{j}{\tbinom {n}{j}}=0$

$\sum _{i=0}^{n}{i{\binom {n}{i}}^{2}}={\frac {n}{2}}{\binom {2n}{n}}$

$\sum _{i=0}^{n}{i^{2}{\binom {n}{i}}^{2}}=n^{2}{\binom {2n-2}{n-1}}$.

$\sum _{k=q}^{n}{\tbinom {n}{k}}{\tbinom {k}{q}}=2^{n-q}{\tbinom {n}{q}}$

Applications

• Find probability of cycles of certain length in a permutation.