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.