Combinatorics

In today's blog, I review some basic formulas regarding permutations and combinations. These are standard counting formulas. I assume that you are familiar with factorials and exponents.
Postulate 1: Sum Rule

If there a ways to A and b ways to B with A,B being completely independent, then there are (a+b) ways to A or B.

Postulate 2: Product Rule

If there a ways to A and b ways to B and a process consists of doing step A and then doing step B, then there are a*b ways to the process (A then B).

Definition 1: Permutations P(n,r)

P(n,r) = the number of permutations possible by choosing r elements from n without allowing repeats.

Defintion 2: r-Permutation of n

An r-permutation of n is any ordering of r elements from a set n.

Lemma 1: r-permuations of n without repeats

P(n,r) = n!/(r-n)!

Proof:

(1) We can view the selection of r elements from n as a process of r steps where each step consists of select 1 of the remaining elements.

(2) For step1, we have n choices. For step2, we have n-1 choices and so on until we reach the last step where we have n-r+1 choices.

(3) Using the Product Rule above, this gives us:
P(r,n) = (n)*(n-1)*...*(n-r+1)

(4) Using some simple multiplication we get:

(n)*(n-1)*...*(n-r+1) = [(n)*(n-1)*...*(n-r+1)]*[(n-r)*...*(1)]/[(n-r)*...(1)] = = n!/(n-r)!

QED

Corollary 1.1: P(n,n) = n!

Proof:

This follows directly from Lemma 1 above since:

P(n,n) = n!/(n-n)! = n!/0! = n!/1 = n!

QED

Lemma 2: r-permutation of a set n with repeats

If repeats are allowed, then there are n^r ways to order r elements from a set n

Proof:

(1) We can view the selection of r elements from n as a process of r steps where each step consists of select 1 of the n elements.

(2) For step1, we have n choices. For step2, we have n choices and so on until we reach the last step where we still have n choices.

(3) Using the Product Rule above, this gives us:

Number of permutations = n*n*...*n = n^r

QED

Definition 3: Combinations C(n,r)

C(n,r) = the number of combinations possible by selecting r elements from a set of n without allowing repeats and ignoring the order of selection.

Definition 4: r-Combinations of a set n

r-Combinations of a set n refers to a set of r elements that are selected from a set of n elements.

Lemma 3: Nonrepeating r-combinations of a set n

C(n,r) = n!/(n-r)!r!

Proof:

(1) Let P(n,r) = the number of permutations of r elements from a set of n.

(2) Let C(n,r) = the number of r combinations from of a set of n elements.

(3) Let P(r,r) = the number of ways to order r elements.

[The number of ways of ordering r elements is logically equivalent to the number of nonrepeating permutations of r elements since each possible permutation corresponds to a possible ordering]

(4) Now, we can see that:
P(n,r) = C(n,r)*P(r,r)

Since the total number of permutations of r elements from the set of n is equal to the total number of combinations of r elements multiplied by the total number of orderings of these same r elements.

(5) This then gives us:

C(n,r) = P(n,r)/P(r,r) = [n!/(n-r)!][1/r!] = n!/(n-r)!r!

QED

Lemma 4: r-combinations of a set n with repeats

If repeats are allowed, then there are C(n+r-1,r) ways to select r elements from a set n

Proof:

(1) We can restate the problem in terms of (n-1) slashes (/) and r asterisks (*).

(2) We can characterize any selection of r elements as the placement of r asterisks within (n-1) slashes. For example, if we wanted to select 10 elements from 5 choices, we could represent the selection of 3 of the 1st, 2 of the 2nd, 3 of the third, 1 of the fourth, and 1 of the fifth as follows:

***/**/***/*/*

We can see that the 5 possible choices corresponds to the four slashes and the 10 selections corresponds to 10 asterisks.

(3) Another way to look at this is to consider each place to be an element. In the above example we have r + n - 1 = 14 elements.

(4) Selection with repeats, then, is the same as either selecting 4 out of 14 elements (if we select which ones are slashes) or selecting 10 out of 14 elements (if we select which ones are asterisks).

(5) Indeed, generalizing this result gives us:

C(r+n-1,r) = (r+n-1)!/(r)!(r+n-1-r)! = (r+n-1)!/(r)!(n-1)!

C(r+n-1,n-1) = (r+n-1)!(n-1)!(r+n-1-n+1)! = (r+n-1)!/(n-1)!(r)!

QED

Lemma 5: C(n,r) is an integer

Proof:

(1) For n=1, this is true since:

C(1,0) = 1!/(0!)(1!) = 1

C(1,1) = 1!/(1!)(0!) = 1

(2) Assume it is true for all r up to some n.

(3) To complete the proof, we only need to show that it is true for all r for n+1.

(4) We can do this using Pascal's Rule (see Theorem, here) which gives us:

C(n,k) + C(n,k-1) = C(n+1,k)

(5) We can now show that C(n+1,r) is an integer for all r ≤ n since:

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

and C(n,r) is an integer and C(n,r-1) is an integer by step #2.

If r = n+1, then we have C(n+1,n+1) = (n+1)!/(n+1)!0! = 1

(6) By induction, we are done.

QED