# 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 = n 2^{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.