Graph Theory/Juggling with Binomial Coefficients

From Wikibooks, open books for an open world
Jump to: navigation, search

Introduction[edit]

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[edit]

  • 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[edit]

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[edit]

 \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[edit]

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