|
1
1 1
1 2 1
1
3 3 1
1
4 6 4 1
1 5 10
10 5 1
1 6 15 20
15 6 1
1 7 21 35 35
21 7 1
1 8 28 56
70 56 28 8 1
1 9 36 84 126
126 84 36 9 1
Combination Identities
C(n,r) is the number of r-element subsets of an n-element set.
C(n,r) = n!/(r!(n-r)!) = (n-r+1)(n-r+2)(n-r+3)...(n) / ((1)(2)(3)...(r))
Example: C(7,3) = 7!/(3! 4!) = (5)(6)(7) / ((1)(2)(3))
1
1 1
1
2 1
1
3 3 1
1 4
6 4 1
1 5 10 10
5 1
1 6 15 20 15
6 1
1 7 21 35 35 21
7 1
1 8 28 56 70 56 28 8
1
1 9 36 84 126
126 84 36 9 1
Mirror Identity
C(n,r) = C(n,n-r)
Proof: C(n,r) = n!/(r!(n-r)!) = n!/((n-r)!(r!)) = C(n,n-r)
Example: C(9,3) = (7)(8)(9) / ((1)(2)(3)) = (4)(5)(6)(7)(8)(9) /
((1)(2)(3)(4)(5)(6)) = C(9,6)
Pascal's Triangle Identity
C(n,r) = C(n-1,r-1) + C(n-1,r), whenever 0 < r < n.
1
1 1
1 2 1
1
3 3 1
1
4 6 4 1
1 5 10
10 5 1
1 6 15 20
15 6 1
1 7 21 35 35
21 7 1
1 8 28 56
70 56 28 8 1
1 9 36 84 126
126 84 36 9 1
The proof involves rewriting n! as (n)(n-1)!, and then splitting n into r and
(n-r):
C(n,r)
= n!/(r!(n-r)!)
= (n)(n-1)!/(r!(n-r)!)
= (r+(n-r))(n-1)!/(r!(n-r)!)
= (r)(n-1)!/(r!(n-r)!) + (n-r)(n-1)!/(r!(n-r)!)
= (n-1)!/((r-1)!(n-r)!) + (n-1)!/(r!(n-r-1)!)
= C(n-1,r-1) + C(n-1,r)
Example:
C(9,3) = (7)(8)(9) / ((1)(2)(3)) = (3+6)(7)(8) / ((1)(2)(3)) = (3)(7)(8) /
((1)(2)(3)) + (6)(7)(8) / ((1)(2)(3)) = (7)(8) / ((1)(2)) + (6)(7)(8) /
((1)(2)(3)) = C(8,2) + C(8,3)
A more intuitive demonstration starts by noting that every r-element subset
of an n-element set either contains "element X" (any element picked
out in advance) or it doesn't. Each of the r-element sets containing X is
the union of {X} and an r-1-element subset of the n-1-element set missing
X. Each of the r-element sets not containing X is an r-element subset of
the n-1-element set missing X.
Extended Pascal's Triangle Identity
The standard Pascal's Triangle identity, introduced above, is a special case
of the more general identity,
| C(n,r) = |
k
Σ
i=0 |
C(n-k,r-k-i) C(k,i) |
|
1
1 1
1 2 1
1
3 3 1
1
4 6 4 1
0(1) 1(4)
5(6) 10(4)10(1)5 1
1 6 15 20
15 6 1
1 7 21 35 35
21 7 1
1 8 28 56
70 56 28 8 1
1 9 36 84 126
126 84 36 9 1
|
In the example shown above, we have extended the definition of
"Combination" so that any number outside Pascal's triangle is
considered zero. The next section elaborates on this idea.
Proof by induction on k: The "ordinary" Pascal's Triangle
identity, proved in the previous section is the base case. Now assume it's
true for k.
| C(n,r) = |
k
Σ
i=0 |
C(n-k,r-k-i) C(k,i) |
Applying the ordinary identity to C(n-k,r-k-i), expressing each
term as the sum of the two above it in the triangle,
| C(n,r) = |
k
Σ
i=0 |
C(n-k-1,r-k-1-i) C(k,i) + C(n-k-1,r-k-2-i) C(k,i) |
Then observe that, apart from the first and last term, each term in row n-k-1
is multiplied first by C(k,i) then by C(k,i+1), adding the results. Thus
the second factor of each term can be simplified using the ordinary identity:
| C(n,r) = |
k+1
Σ
i=0 |
C(n-k-1,r-k-1-i) C(k+1,i) |
Extending the definition of "Combination"
It is helpful and intuitive to extend the definition of
"combination" to include C(n,r) where r is less than zero or greater
than n, and define such combinations as zero. For example, the number of
5-element subsets of a 3-element set is zero: C(3,5)=0.
By extending the definition this way, the Pascal's Triangle Identity need no
longer restrict r, and proofs such as those, below, that depend on it are
simplified. Since it is helpful, and nothing is "broken" by this
convention, it is a fairly common convention, and we will use it here.
Row Sums
|
1
1 1
1 2 1
1
3 3 1
1
4 6 4 1
1 + 5 +10 +10 + 5 +
1 = 32
1 6 15 20
15 6 1
1 7 21 35 35
21 7 1
1 8 28 56
70 56 28 8 1
1 9 36 84 126
126 84 36 9 1
|
The proof works by showing that every number of this row is the sum of two
numbers above it, so each number in the row above this one is used twice in the
sum. Thus, the sum of each row is twice that of the row above it.
It's true when n=1, because C(1,0)+C(1,1)=2=21.
Assume it's true when n=k.
Let S = C(k+1,0) + C(k+1,1) + ... + C(k+1,k+1)
Recall that C(k+1,j) = C(k,j-1) + C(k,j) whenever 0 < j < k+1
So S = 1 + (C(k,0)+C(k,1)) + (C(k,1)+C(k,2)) + ... + (C(k,k-1)+C(k,k)) + 1
Rearranging the parentheses,
So S = (1 + (C(k,0)) + (C(k,1)+C(k,1)) + ... + (C(k,k))+1), which by
assumption is (2)(2k)
So S = 2k+1, proving the identity
Diagonal Sums
n
Σ
i=r |
C(i,r) = C(n+1,r+1) |
|
1
1 1
1 2 1
1
3 3 1
1
4 6 +4 1
1 5 10 +10
5 1
1 6 15 +20
15 6 1
1 7 21 35 =35
21 7 1
1 8 28 56
70 56 28 8 1
1 9 36 84 126
126 84 36 9 1
|
Proof:
The statement is true when n=0, because C(0,0) = C(1,1).
Assume it's true when n=k, and consider the following sums:
S = sum from i=r-1 to k of C(i,r-1) = C(k+1,r), and
T = sum from i=r to k of C(i,r) = C(k+1,r+1)
Looking at the sum of S and the individual terms of T, S+T = sum from i=r to
k+1 of C(i,r)
Looking at the sums of S and T, S+T = C(k+2,r+1)
So the sum from i=r to k+1 of C(i,r) = C(k+2,r+1), proving the identity.
Example: C(3,3) + C(4,3) + C(5,3) + C(6,3) = 1+4+10+20 = 35 = C(7,4)
Second Order Diagonal Sum
n
Σ
i=r |
(n-i+1)C(i,r) = C(n+2,r+2) |
|
1
1 1
1 2 1
1
3 3 1(4)
1
4 6 +4(3)
1
1 5 10 +10(2) 5 1
1 6 15 +2015 6 1
1 7 21 35 35 21
7 1
1 8 28 56
70 56 28 8 1
1 9 36 84 126
126 84 36 9
|
Proof:
n
Σ
i=r |
(n-i+1)C(i,r) = |
n
Σ
j=r |
j
Σ
i=r |
C(i,r) = |
n
Σ
j=r |
C(j+1,r+1) = C(n+2,r+2) |
kth Order Diagonal Sum
n
Σ
i=r |
C(n-i+k-1,k-1)C(i,r) = C(n+k,r+k) |
|
1
1 1
1 2 1
1
3 3 1(10)
1
4 6 +4(6)
1
1 5 10 +10(3) 5 1
1 6 15 +20(1)
15 6 1
1 7 21 35 35
21 7 1
1 8 28 56
70 56 28 8 1
1 9 36 84 126
126 84 36 9 1
Diagram illustrates 3rd order diagonal sum;
k=3, n=6, r=3
|
Proof: assume it's true for k-1, and show it's true for k:
n
Σ
i=r |
C(n-i+k-1,k-1)C(i,r) = |
n
Σ
j=r |
C(n-j+k-2,k-2) |
j
Σ
i=r |
C(i,r) = |
n
Σ
j=r |
C(n-j+k-2,k-2)C(j+1,r+1) = C(n+k,r+k) |
Internet References
Related Pages in this Website
Counting Primes method of proving the
following are integers: C(n,k) = n!/(k!(n-k)!), (2a)!(2b)!/((a+b)!a!b!)
Floor Function Identities,
which are used in proofs that combinatorial identities are integers
|
