4Counting and integers
IA Numbers and Sets
4.1 Basic counting
A useful theorem is the pigeonhole principle.
Theorem
(Pigeonhole Principle)
.
If we put
mn
+ 1 pigeons into
n
pigeonholes,
then some pigeonhole has at least m + 1 pigeons.
Example.
In Cambridge, there are 2 people who have the same number of
hairs.
Another useful tool for counting is the indicator function.
Definition
(Indicator function/characteristic function)
.
Let
X
be a set. For
each
A ⊆ X
, the indicator function or characteristic function of
A
is the function
i
A
:
X → {
0
,
1
}
with
i
A
(
x
) = 1 if
x ∈ A
, 0 otherwise. It is sometimes written as
χ
A
.
Proposition.
(i) i
A
= i
B
⇔ A = B
(ii) i
A∩B
= i
A
i
B
(iii) i
¯
A
= 1 − i
A
(iv) i
A∪B
= 1
− i
A∪B
= 1
− i
¯
A∩
¯
B
= 1
− i
¯
A
i
¯
B
= 1
−
(1
− i
A
)(1
− i
B
) =
i
A
+ i
B
− i
A∩B
.
(v) i
A\B
= i
A∩
¯
B
= i
A
i
¯
B
= i
A
(1 − i
B
) = i
A
− i
A∩B
Example.
We can use the indicator function to prove certain properties about
sets:
(i) Proof that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C):
i
A∩(B∪C)
= i
A
i
B∪C
= i
A
(i
B
+ i
C
− i
B
i
C
)
= i
A
i
B
+ i
A
i
C
− i
A
i
B
i
C
i
(A∩B)∪(A∩C)
= i
A∩B
+ i
A∩C
− i
A∩C
i
A∩B
= i
A
i
B
+ i
A
i
C
− i
A
i
C
i
A
i
B
= i
A
i
B
+ i
A
i
C
− i
A
i
B
i
C
Therefore
i
A∩(B∪C)
=
i
(A∩B)∪(A∩C)
and thus
A ∩
(
B ∪ C
) = (
A ∩ B
)
∪
(A ∩ C).
Note that i
A
= i
2
A
since i
A
= 0 or 1, and 0
2
= 0 and 1
2
= 1.
(ii)
Proof that the symmetric difference is associative: Observe that
i
A∆B
≡
i
A
+ i
B
(mod 2). Thus i
(A∆B)∆C
= i
A∆(B∆C)
≡ i
A
+ i
B
+ i
C
(mod 2).
Indicator functions are handy for computing the sizes of finite sets because if
A ⊆ X, then |A| =
P
x∈X
i
A
(x).
Proposition. |A ∪ B| = |A|+ |B| − |A ∩ B|
Proof.
|A ∪ B| =
X
x∈X
i
A(x)∪B(x)
=
X
(i
A
(x) + i
B
(x) − i
A∩B
(x))
=
X
i
A
(x) +
X
i
B
(x) −
X
i
A∩B
(x)
= |A| + |B| − |A ∩ B|
More importantly, we will use indicator functions to prove a powerful result.
Theorem
(Inclusion-Exclusion Principle)
.
Let
A
i
be subsets of a finite set
X
,
for 1 ≤ i ≤ n. Then
|
¯
A
1
∩ ··· ∩
¯
A
n
| = |X| −
X
i
|A
i
| +
X
i<j
|A
i
∩ A
j
| − ··· + (−1)
n
|A
1
∩ ···A
n
|.
Equivalently,
|A
1
∪ ··· ∪ A
n
| =
X
i
|A
i
| −
X
i<j
|A
i
∩ A
j
| + ··· + (−1)
n−1
|A
1
∩ ··· ∩ A
n
|.
The two forms are equivalent since |A
1
∪ ··· ∪ A
n
| = |X| − |
¯
A
1
∩ ··· ∩
¯
A
n
|.
Proof. Using indicator functions,
i
¯
A
1
∩
¯
A
2
∩···∩
¯
A
n
=
Y
j
i
¯
A
j
=
Y
j
(1 − i
A
j
)
= 1 −
X
i
i
A
i
+
X
i<j
i
A
i
i
A
j
− ··· + (−1)
n
i
A
1
i
A
2
···i
A
n
= 1 −
X
i
i
A
i
+
X
i<j
i
A
i
∩A
j
− ··· + (−1)
n
i
A
1
∩A
2
∩A
3
∩···∩A
n
Thus
|
¯
A
1
∩ ··· ∩
¯
A
n
| =
X
x∈X
i
¯
A
1
∩
¯
A
2
∩···∩
¯
A
n
(x)
=
X
x
1 −
X
i
X
x
i
A
i
(x) +
X
i<j
X
x
i
A
i
∩A
j
(x) − ···
+
X
x
(−1)
n
i
A
1
∩A
2
∩A
3
∩···∩A
n
(x)
= |X| −
X
i
|A
i
| +
X
i<j
|A
i
∩ A
j
|
−
X
i<j<k
|A
i
∩ A
j
∩ A
k
| + ··· + (−1)
n
|A
1
∩ A
2
∩ ···A
n
|
Example. How many numbers ≤ 200 are coprime to 110?
Let
X
=
{
1
, ···
200
}
, and
A
1
=
{x
: 2
| x}
,
A
2
=
{x
: 5
| x}
,
A
3
=
{x
: 11
| x}
.
We know that
|A
1
| = b200/2c = 100
|A
2
| = b200/5c = 40
|A
3
| = b200/11c = 18
|A
1
∩ A
2
| = b200/10c = 20
|A
1
∩ A
3
| = b200/22c = 9
|A
2
∩ A
3
| = b200/55c = 3
|A
1
∩ A
2
∩ A
3
| = b200/110c = 1
Then the answer is 200 − 100 − 40 − 18 + 20 + 9 + 3 − 1 = 73.