Graph Theory/Juggling with Binomial Coefficients

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:
 
  • 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:

 

Put   in

 

The Identities

edit
 
 
 
 
 
 


 
 
 
 
 

where F(n) denote the nth Fibonacci number.

 
 
 
 
 .
 

Applications

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