Discrete Mathematics 51
For integers 0 ≤ k ≤ n, we define
n
k
, pronounced, “n choose k,” as the number of ways
to choose k items from a set of n items, disregarding the order.
Theorem 43. The number of ways to choose k items from a set of n items, for 0 ≤ k ≤ n,
is given by the formula
n
k
=
n!
k!(n − k)!
.
We shall give several proofs.
First proof of theorem 43. Consider the following process: enumerate all n items, and then
take just the first k in that enumeration. We will often get the same set of k elements, so
there is considerable multiple counting in this process. But how much? The number of
enumerations of n objects is precisely n!, by theorem 42. For a given enumeration of the
objects, there are k! many permutations of the first k elements of it, and (n − k)! many
permutations of the other elements. So there are k!(n − k)! many ways to permute the
elements in the enumeration, while having the same first k elements. So this is the factor
that we have double counted by, and so the number of ways to choose k elements from n is
precisely n!/k!(n − k)!, as desired.
The second proof will make use of the following lemma:
Lemma 44.
n+1
k+1
=
n
k
+
n
k+1
.
Proof. Consider a set A with n + 1 objects, and we wish to count the number of ways of
choosing k + 1 objects from A. Fix a particular element a ∈ A. Now, some of the size-
(k + 1) subsets of A have the element a, and some may not. There are exactly
n
k
many
size-(k + 1) subsets of A that have the element a, since once you choose a, then you must
choose k additional elements from A \
{
a
}
, a set of size n. Similarly, there are exactly
n
k+1
many ways to choose k + 1 elements from A without using the element a, since in this
case one is really choosing from amongst the other n elements. So the total number of
ways of choosing k + 1 elements from A is the sum of these two, and we have proved the
lemma.
Second proof of theorem 43. We prove the theorem by induction on n.Ifn = 0, then also
k = 0, and it is easy to verify that there is exactly one way to choose nothing from nothing,
so
0
0
= 1, which fits the formula
0!
0!·0!
, and so the anchor case is proved. Suppose now that
the formula is correct for a number n, using any k, and consider the next number, n + 1.
Since again there is only one way to choose nothing from an n element set, we see that
n+1
0
= 1, which is equal to
n!
0!n!
, verifying the theorem in this case. Next, we consider
n+1
k+1
. By lemma 44, this is equal to
n
k
+
n
k+1
. By the induction hypothesis, we know that
n
k
= n!/k!(n − k)! and
n
k+1
= n!/(k + 1)!(n − (k + 1))!.