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} (\binom{n}{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

Template:ExampleRobox To get:

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}

Put $x = 1 and y = 1$ in

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} .

Template:Robox/Close

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 - 2 k}{n} (\binom{n}{k}) .

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n}) .

\sum_{k = 0}^{n} (\binom{n}{k}) (\binom{n}{n - k}) = (\binom{2 n}{n}) .

\sum_{k = 0}^{n} k (\binom{n}{k}) = n 2^{n - 1}

\sum_{k = 0}^{n} k^{2} (\binom{n}{k}) = (n + n^{2}) 2^{n - 2}

\sum_{m = 0}^{n} (\binom{m}{j}) (\binom{n - m}{k - j}) = (\binom{n + 1}{k + 1})

\sum_{m = 0}^{n} (\binom{m}{k}) = (\binom{n + 1}{k + 1}) .

\sum_{k = 0}^{⌊ \frac{n}{2} ⌋} (\binom{n - k}{k}) = F (n + 1)

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

\sum_{j = k}^{n} (\binom{j}{k}) = (\binom{n + 1}{k + 1})

\sum_{j = 0}^{k} (- 1)^{j} (\binom{n}{j}) = (- 1)^{k} (\binom{n - 1}{k})

\sum_{j = 0}^{n} (- 1)^{j} (\binom{n}{j}) = 0

\sum_{i = 0}^{n} i {(\binom{n}{i})}^{2} = \frac{n}{2} (\binom{2 n}{n})

\sum_{i = 0}^{n} i^{2} {(\binom{n}{i})}^{2} = n^{2} (\binom{2 n - 2}{n - 1})

.

\sum_{k = q}^{n} (\binom{n}{k}) (\binom{k}{q}) = 2^{n - q} (\binom{n}{q})

Applications

Find probability of cycles of certain length in a permutation.

Template:BookCat

Graph Theory/Juggling with Binomial Coefficients

Contents

Introduction

Techniques

Worked Examples

The Identities

Applications

Navigation menu

Graph Theory/Juggling with Binomial Coefficients

Introduction

Techniques

Worked Examples

The Identities

Applications

Navigation menu

Search