# 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 nth 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.