## Monday, April 16, 2018

### Combinatorics Derivations

Combinatorics Derivations

The definition of the combination function is:

C(n, r) = n! / (r! *  (n – r)!)

Today I am going to mathematically verify three equivalents in combinatorics.

Newton’s Identity

C(n,r) * C(r,k) = C(n,k) * C(n – k, r – k)

Here I am going to assume that n > r > k.

Hence:

C(n, r) * C(r, k)

= n! / (r! * (n – r)!) * r! / (k! * (r – k)!)

= n! / (n – r)! * 1 /  (k! * (r – k)!)

Rearrange:

= n! / k! * 1 / ((n – r)! * (r – k)!)

Multiply by (n – k)!/(n- k)!:

= n! / (k! * (n – k)!) * (n – k)! / ((n – r)! * (r – k)!)

Observe that (n – k) – (r – k) = n – k – r + k = n – r.  Hence,

= C(n,k) * C(n – k, r – k)   QED

Pascal’s Identity

C(n,r) = C(n-1, r) + C(n – 1, r – 1)

I’m going to start with C(n-1, r) + C(n – 1, r – 1)

C(n-1, r) + C(n – 1, r – 1)

= (n – 1)! / (r! * (n – 1 – r)!) + (n – 1)! / ((r – 1)! * (n – r)!)

= (n – 1)! / (r! * (n – 1- r)!) + (r * (n – 1)!) / (r! *(n – r)!)

= ((n – 1)! * (n – r)) / (r! * (n – r)!) + (r * (n – 1)!) / (r! * (n – r)!)

= (n * (n – 1)! – r * (n – 1)! + r * (n – 1)!) / (r! * (n – r)!))

= (n * (n  - 1)!) / (r! * (n – r)!)

= n! / (r! * (n – r)!)

= C(n, r)  QED

Combinatorial Proof

C(m + n, 2) – C(m, 2) – C(n, 2) = m * n

C(m + n, 2) – C(m, 2) – C(n, 2)

Note that 2! = 2

= (m + n)! / (2 * (m + n – 2)!) – m! / (2 * (m – 2)!) – n! / (2 * (n – 2)!)

= ( (m + n)! * (m – 2)! * (n – 2)! – m! * (m + n – 2)! * (n – 2)!  - n! * (m – 2)! * (m + n – 2)!) / (2 * (m + n – 2)! * (m – 2)! * (n – 2)!)

= ( (m + n) * (m + n – 1) *(m + n – 2)! * (m – 2)! * (n – 2)! – m * (m – 1) *(m – 2)! * (n – 2)! * (m + n – 2)! – n * (n – 1) * (n – 2)! * (m – 2)! * (m + n – 2)! )

/  (2 * (m + n – 2)! * (m – 2)! * (n – 2)!)

= ( (m + n)*(m + n – 1) – m * (m – 1) – n * (n – 1) ) / 2

= ( m^2 + m*n – m + m*n + n^2 – n – m^2 + m – n^2 + n) / 2

= (2 * m * n) / 2

= m * n   QED

Eddie

Source where I got the identities from:

V.K. Balakrishnan Schaum’s Theory and Problems: Combinatorics including concepts of Graph Theory  McGraw-Hill, Inc. New York: 1995  ISBN 0-07-003575-X

The derivation and proof details are my work.

All original content copyright, © 2011-2018.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.  Please contact the author if you have questions.

### Casio fx-5000F: Auto Formulas

Casio fx-5000F:   Auto Formulas The formula listing can apply to (almost) any calculator that can handle formula programming. In November, t...