**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.

_{}

^{}

## No comments:

## Post a Comment