20 1. Let’s Count!
1.8 The Number of Subsets of a Given Size
From here, we can easily derive one of the most important counting results.
Theorem 1.8.1The number ofk-subsets of ann-set is
n(n−1)···(n−k+1)
k!=
n!
k!(n−k)!.
Proof. Recall that if we countorderedsubsets, we getn(n−1)···(n−
k+1)=n!/(n−k)!, by Theorem 1.7.1. Of course, if we want to know the
number ofunorderedsubsets, then we have overcounted; every subset was
counted exactlyk! times (with every possible ordering of its elements). So
we have to divide this number byk! to get the number of subsets withk
elements (without ordering).
The number ofk-subsets of ann-set is such an important quantity that
there is a special notation for it:
(n
k)
(read “nchoosek”). Thus
(
n
k)
=
n!
k!(n−k)!. (1.6)
The number of different lottery tickets is
( 90
5)
, the number of handshakesat the start of Alice’s birthday party is
( 7
2)
, etc. The numbers(n
k)
are also
calledbinomial coefficients(in Section 3.1 we will see why).
The value of
(n
n)
is 1, since ann-element set has exactly onen-element
subset, namely itself. It may look a bit more tricky to find that
(n
0)
=1,
but it is just as easy to explain: Every set has a single 0-element subset,
namely the empty set. This is true even for the empty set, so that
( 0
0)
=1.
1.8.1Which problems discussed during the party were special cases of theorem
1.8.1?
1.8.2Tabulate the values ofn
k
for 0≤k≤n≤5.1.8.3Find the values ofn
k
fork=0, 1 ,n− 1 ,nusing (1.6), and explain the
results in terms of the combinatorial meaning of
n
k
.Binomial coefficients satisfy many important identities. In the next theo-
rem we collect some of these; some other identities will occur in the exercises
and in the next chapter.
Theorem 1.8.2Binomial coefficients satisfy the following identities:
(
n
k
)
=
(
n
n−k