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: 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: Put in The Identities where F(n) denote the nth Fibonacci number. . Applications Find probability of cycles of certain length in a permutation.