Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Counting > Combination Identities

                  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

  n
Σ
 j=0
C(n,j)  =  2n 

                  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

 

The webmaster and author of this Math Help site is Graeme McRae.