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


Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \tbinom {n-k} k = F(n+1)}

where F(n) denote the nth Fibonacci number.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle \sum_{j=0}^n (-1)^j\tbinom n j = 0}
.

Applications[edit]

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