4Counting and integers

IA Numbers and Sets


4.2 Combinations
“Combinations” is about counting the ways we can pick things without regards
to order. We can formulate these problems in the language of sets: given a set
X
, how many subsets of
X
are there that satisfy some particular properties?
For example, if we want to pick 3 people from 10, we can let
X
be the set of the
10 people. Then the number of ways of picking the 3 people is the number of
subsets of size three.
Example.
How many subsets of
{
1
,
2
, ···n}
are there? There are 2
×
2
×···×
2 =
2
n
. Since for each subset, every element is either in or out of the subset, and there
are two choices for each element. Equivalently, there are 2
n
possible indicator
functions, i.e. functions {1, 2, 3, ··· , n} → {0, 1}.
Definition
(Combination
n
r
)
.
The number of subsets of
{
1
,
2
,
3
, ··· , n}
of size
r is denoted by
n
r
. The symbol is pronounced as “n choose r”.
This is the definition of
n
r
. This does not in any way specify how we can
actually calculate the value of
n
r
.
Proposition. By definition,
n
0
+
n
1
+ ···+
n
n
= 2
n
Theorem (Binomial theorem). For n ∈ N with a, b ∈ R, we have
(a + b)
n
=
n
0
a
n
b
0
+
n
1
a
n−1
b
1
+ ··· +
n
r
a
n−r
b
r
+ ··· +
n
n
a
0
b
n
Proof.
We have (
a
+
b
)
n
= (
a
+
b
)(
a
+
b
)
···
(
a
+
b
). When we expand the product,
we get all terms attained by choosing
b
from some brackets,
a
from the rest. The
term
a
n−r
b
r
comes from choosing
b
from
r
brackets,
a
from the rest, and there
are
n
r
ways to make such a choice.
This theorem is not immediately useful since we do not know the value of
n
r
!
Because of this theorem,
n
r
is sometimes called a “binomial coefficient”.
Proposition.
(i)
n
r
=
n
n − r
. This is because choosing
r
things to keep is the same as
choosing n − r things to throw away.
(ii)
n
r − 1
+
n
r
=
n + 1
r
(Pascal’s identity) The RHS counts the number
of ways to choose a team of
r
players from
n
+ 1 available players, one of
whom is Pietersen. If Pietersen is chosen, there are
n
r−1
ways to choose
the remaining players. Otherwise, there are
n
r
ways. The total number
of ways is thus
n
r−1
+
n
r
.
Now given that
n
0
=
n
n
= 1, since there is only one way to choose
nothing or everything, we can construct Pascal’s triangle:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
where each number is the sum of the two numbers above it, and the
r
th
item of the nth row is
n
r
(first row is row 0).
(iii)
n
k

k
r
=
n
r

n − r
k − r
. We are counting the number of pairs of sets
(
Y, Z
) with
|Y |
=
k
and
|Z|
=
r
with
Z ⊆ Y
. In the LHS, we first choose
Y
then choose
Z ⊆ Y
. The RHS chooses
Z
first and then choose the
remaining Y \ Z from {1, 2, ···n} \Z.
(iv)
a
r

b
0
+
a
r − 1

b
1
+
···
+
a
r − k

b
k
+
···
a
0

b
r
=
a + b
r
(Vandermonde’s convolution) Suppose we have
a
men and
b
women, and
we need to choose a committee of
r
people. The right hand side is the total
number of choices. The left hand side breaks the choices up according to
the number of men vs women.
Example.
A greengrocer stocks
n
kinds of fruit. In how many ways can we
choose a bag of
r
fruits? If we are only allowed to choose one of each kind, then
the answer is
n
r
. But we might have
r
= 4, and we want to allow picking 2
apples, 1 plum and 1 quince. The total number of ways to choose is
n+r−1
r
.
Why?
Each choice can be represented by a binary string of length
n
+
r −
1, with
r
0’s and
n −
1 1’s. The string can be constructed as follows (by example): when
n
= 5 and
r
= 8, a possible binary string 000100110010. The block of zeros
corresponds to the number of each fruit chosen, and the 1s separate the choices.
In the string above, we have 3 of type 1, 2 of type 2, 0 of type 3, 2 of type 4 and
1 of type 5.
Then clearly the number of possible strings is
n+r−1
r
.
Proposition.
n
r
=
n!
(n − r)!r!
.
Proof.
There are
n
(
n−
1)(
n−
2)
···
(
n−r
+1) =
n!
(n−r)!
ways to choose
r
elements
in order. Each choice of subsets is chosen this way in
r
! orders, so the number of
subsets is
n!
(n−r)!r!
.
We might write
x
r
for the polynomial
x
(
x −
1)
···
(
x − r
+ 1). We call this
“
x
to the
r
falling”. We can write
n
r
=
n
r
r!
. Multiplying Vandermonde by
r
!,
we obtain the “falling binomial theorem”
r
0
a
r
b
0
+
r
1
a
r−1
b
1
+ ··· +
r
r
a
0
b
r
= (a + b)
r
.
Example.
A bank prepares a letter for each of its
n
customers, saying how
much it cares. (Each of these letters costs the customer £40) There are
n
! ways
to put the letters in the envelopes. In how many ways can this be done so that no
one gets the right letter (i.e. how many derangements are there of
n
elements)?
We let
X
be the set of all envelopings (permutation of
n
).
|X|
=
n
!. For each
i
, let
A
i
=
{x ∈ X
:
x assigns the correct letter to customer i}
. We want to
know
|
T
i
¯
A
i
|
. We know that
|A
i
|
= (
n −
1)! since
i
’s letter gets in
i
’s envelopes
and all others can be placed randomly. We have
|A
i
∩ A
j
|
= (
n −
2)! as well.
Similarly, |A
i
∩ A
j
∩ A
k
| = (n − 3)!.
By the inclusion-exclusion formula, we have
\
i
¯
A
i
= |X| −
X
|A
i
| +
X
|A
i
∩ A
j
| + ···
= n! −
n
1
(n − 1)! +
n
2
(n − 2)! − ···
= n!
1 −
1
1!
+
1
2!
− ··· +
(−1)
n
n!
≈ n!e
−1