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.