A Review of Basic Tools for Counting
1. (Addition vs. Multiplication) If a work can be done in either m ways or n ways then
the total no. of ways to do it is m + n. If a work can be split in two parts, where the
first part can be done in m ways and the second part in n ways, then the total no. of
ways to do it is mn.
2. The number of ways to permute (arrange in a line) n distinct objects is
n! = n(n − 1) · · · 1.
We define 0! = 1 as a convention.
Note. In mathematics, empty sums are always defined as 0 and empty products are
always defined as 1. That is why it is natural to take 0!=1.
3. Number of ways to pick k objects one-by-one from n distinct objects is
n
Pk = n(n − 1) . . . (n − k + 1) = n! /(n − k)! .
Note, the order in which we take the objects matter in this case.
n
4. Number of ways to choose k objects from n distinct objects is denoted by n Ck or k
.
n
n n(n − 1) . . . (n − k + 1) Pk n!
= = =
k k! k! k! (n − k)!
Here we consider the selection as an unordered set, so it is same as picking k objects
at once.
Note. In some texts, nk is defined as 0 if k > n or k < 0. You may follow such
convention, but if you follow, you should mention that.
5. Binomial Theorem :
n
n
X n k n−k
(x + y) = x y
k=0
k
n n n n−1 n 2 n−2 n n
= y + xy + xy + ··· + x
0 1 2 n
n n n n−1 n n−2 2 n n
= x + x y+ x y + ··· + y
0 1 2 n
n
(This is why we call k
as ‘binomial coefficients.’)
1
Note. You can prove it by simple combinatorial logic. Hence this is not only true for
real numbers, but also true for complex numbers.
6. Following are some properties of binomial coefficients
n n
(a) = , 0 ≤ k ≤ n.
k n−k
n n n−1
(b) = , 1 ≤ k ≤ n.
k k k−1
n−1 n−1 n
(c) + = , 1 ≤ k ≤ n − 1.
k−1 k k
n n n
(d) + + ··· + = 2n .
0 1 n
n n n n
(e) − + · · · + (−1) = 0.
0 1 n
n m n m n m n+m
(f) + + ··· + = .
0 r 1 r−1 r 0 r
n m n n−k
(g) = , 0 ≤ k ≤ m ≤ n.
m k k m−k
n n n n
(h) +2 +3 ··· + n = n · 2n−1 .
1 2 3 n
Derive above identities by both simple algebra and combinatorial arguments.
7. Permutation with repetitions: Suppose there are k1 objects of one kind, k2 objects of
second kind, . . . , km objects of m-th kind. If n = k1 + · · · + km then no. of ways to
permute such n objects is given by
n!
.
k1 ! k2 ! . . . km !
8. Combination with repetitions: Suppose that we are choosing k objects from n distinct
objects where repetition is allowed
(i.e., drawing
with replacement) and ordering is not
n−1+k
considered. This can be done in ways.
k
n+r−1
9. No. of non-negative integer solutions to the eqn. x1 + x2 + · · · + xr = n is .
r−1
n−1
No. of positive integer solutions to the eqn. x1 + x2 + · · · + xr = n is .
r−1
2
Note, in both of the above situations the solutions are ordered, i.e., 1 + 2 + 3 = 6 and
2 + 1 + 3 = 6 are considered as different solutions.
10. Circular Permutations: Suppose some objects are to be arranged in a circle. We call
two arrangements identical if one of them can be obtained by rotating the other. The
number of circular permutations of n distinct objects is (n − 1)! . We are dividing n!
by n since each distinct circular permutation can be rotated n times to give n many
different arrangements on a line.
11. Inclusion and exclusion principle: If A, B are two finite sets,
|A ∪ B| = |A| + |B| − |A ∩ B| .
For three sets,
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C| .
This result can be generalized as: for finite sets A1 , A2 , . . . An we have
X X X
|A1 ∪ A2 ∪ . . . An | = |Ak | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak |
1≤k≤n 1≤i<j≤n 1≤i<j<k≤n
− · · · + (−1)n−1 |A1 ∩ A2 ∩ . . . ∩ An |.
12. Pigeonhole Principle: If n + 1 pigeons are to be put into n holes, then at least one hole
gets more than one pigeon. More generally, if nk + 1 balls are put into n boxes then
at least one box receives more than k balls.
References:
1. An Excursion in Mathematics.
2. A Path to Combinatorics For Undergraduates, by Titu Andreescu and Zuming Feng.
3. Problem Solving Strategies, by Arthur Engel.
4. 102 Combinatorial Problems, by Titu Andreescu and Zuming Feng.
Aditya Ghosh
