Module 5

Combinatorics - I

Combinatorics can be traced back more than 3000 years to India and China. For many centuries,
it primarily comprised the solving of problems relating to the permutations and combinations of
objects. The use of the word “combinatorial” can be traced back to Leibniz in his dissertation on
the art of combinatorial in 1666. Over the centuries, combinatorics evolved in recreational pastimes.
These include the Königsberg bridges problem, the four-colour map problem, the Tower of Hanoi, the
birthday paradox and Fibonacci’s ‘rabbits’ problem. In the modern era, the subject has developed
both in depth and variety and has cemented its position as an integral part of modern mathematics.
Undoubtedly part of the reason for this importance has arisen from the growth of computer science and
the increasing use of algorithmic methods for solving real-world practical problems. These have led
to combinatorial applications in a wide range of subject areas, both within and outside mathematics,
including network analysis, coding theory, and probability.

5.1 Addition and multiplication rules

We first consider some questions.

1. How many possible crossword puzzles are there?

2. Suppose we have to select 4 balls from a bag of 20 balls numbered 1 to 20. How often do two of
the selected balls have consecutive numbers?

3. How many ways are there of rearranging the letters in the word ALPHABET?

4. Can we construct a floor tiling from squares and regular hexagons?

We observe various things about the above problems. A priori, unlike many problems in math-
ematics, there is hardly any abstract or technical language. Despite the initial simplicity, some of
these problems will be frustratingly difficult to solve. Further, we notice that despite these problems
appearing to being diverse and unrelated, they principally involve selecting, arranging, and counting
objects of various types. We will first address the problem of counting. Clearly, we would like to be
able to count without actually counting. In other words, can we figure out how many things there
are with a given property without actually enumerating each of them. Quite often this entails deep
mathematical insight. We now introduce two standard techniques which are very useful for counting
without actually counting. These techniques can easily be motivated through the following examples.

Example 5.1.1.

71
5.2. PERMUTATIONS AND COMBINATIONS 72

1. Let the cars in New Delhi have license plates containing 2 alphabets followed by two numbers.
What is the total number of license plates possible?
Ans: Here, we observe that there are 26 choices for the first alphabet and another 26 choices
for the second alphabet. After this, there are two choices for each of the two numbers in the
license plate. Hence, we have a maximum of 26 × 26 × 10 × 10 = 67, 600 license plates.
2. Let the cars in New Delhi have license plates containing 2 alphabets followed by two numbers
with the added condition that “in the license plates that start with a vowel the sum of numbers
should always be even”. What is the total number of license plates possible?
Ans: Here, we need to consider two cases.
Case 1: The license plate doesn’t start with a vowel. Then using the previous example, the
number of license plates equals 21 × 26 × 10 × 10 = 54600.
Case 2: The license plate starts with a vowel. Then the number of license plates equals
5 × 26 × (5 × 5 + 5 × 5) = 6500.
Hence, we have a maximum of 54600 + 6500 = 61100 license plates.

Generalization of the first example leads to what is referred to as the rule of product and that of
the second leads to the rule of addition. To understand these rules, we explain the involved ideas.
Suppose we have a task to complete and that the task has some parts (subtasks). Assume that
each of the parts can be completed on their own and completion of one part does not result in the
completion of any other part. We say the parts are compulsory to mean that each of the parts must
be completed to complete the task. We say the parts are alternative to mean that exactly one of
the parts must be completed to complete the task. With this setting we state the two basic rules of
combinatorics.

Discussion 5.1.2. [Basic counting rules] Let n, m1, . . . , mn ∈ N.

1. [Multiplication/Product rule] If a task consists of n compulsory parts and the i-th part can
be completed in mi ways, i = 1, 2, . . . , n, then the task can be completed in m1m2 · · · mn ways.
2. [Addition rule] If a task consists of n alternative parts, and the i-th part can be completed in
mi ways, i = 1, . . . , n, then the task can be completed in m1 + m2 + · · · + mn ways.

To illustrate these rules once again let us consider the following examples.
Example 5.1.3. 1. How many three digit natural numbers can be formed using digits 0, 1, · · · , 9?
Identify the number of parts in the task and the type of the parts (compulsory or alternative).
Which rule applies here?
Ans: The task of forming a three digit number can be viewed as filling three boxes kept in a
horizontal row. Our task has three compulsory parts. Part 1: choose a digit for the leftmost
place. Part 2: choose a digit for the middle place. Part 3: choose a digit for the rightmost place.

Multiplication rule applies. Ans: 9 × 10 × 10.

2. How many three digit natural numbers with distinct digits can be formed using digits 1, · · · , 9
such that each digit is odd or each digit is even? Identify the number of parts in the task and
the type of the parts (compulsory or alternative). Which rule applies here?
5.2. PERMUTATIONS AND COMBINATIONS 73

Ans: The task has two alternative parts. Part 1: form a three digit number with distinct digits
using digits from {1, 3, 5, 7, 9}. Part 2: form a three digit number with distinct digits using
digits from {2, 4, 6, 8}. Observe that Part 1 is a task having three compulsory subparts. Using
multiplication rule, we see that Part 1 can be done in 5 × 4 × 3 ways. Part 2 is a task having
three compulsory subparts. So, it can be done in 4 × 3 × 2 ways. Since our task has alternative
parts, addition rule applies. Ans: 84.

Remark 5.1.4. There is another way to formulate the above rules. Let Ai be the set of all possible
ways in which the i-th part can be completed. In this setting, the multiplication rule can be re-written
as: if A1, A2, . . . , An are nonempty finite sets, then |A1 × A2 × · · · × An| = |A1| · |A2| |An|.
For the addition rule, note that, as the completion of one part does not result in the completion of any
other part, A1, A2, . . . , An are disjoint. Thus, the addition rule can be re-written as: if A1, A2, , An
are disjoint, nonempty finite sets, then |A1 ∪ A2 ∪ · · · ∪ An| = |A1| + |A2| + ······+ |An|.

5.2 Permutations and combinations

This section is primarily devoted to introduce some very common combinatorial objects and develop-
ment of methods to count them using the addition rule and multiplication rule.

5.2.1 Counting words made with elements of a set S

The first fundamental combinatorial object one commonly studies is a function f : [k] → S. The set
of all functions from A to B will be denoted by Map(A, B).

Discussion 5.2.1. 1. Let k ∈ N and let f ∈ Map([k], S). Then, we may view f as the ordered
k-tuple (f (1), . . . , f (k)). Thus f is an element of Sk = S × S × × S, k times.
2. Consider an ordered k-tuple (x1, x2, ..... , xk) of elements of X. If we remove the brackets and the
commas, then what we get is x1x2 ..... xk, which is called a word of length k made with elements
of X. Thus, the word corresponding to the tuple (a, a, b) is aab.
3. Consider a function f : [3] → {a, b, . . . , z}, defined by f (1) = a, f (2) = a and f (3) = b.
Technically, f = {(1, a), (2, a), 3, b)} and the ordered tuple it gives is (a, a, b) and the word related
to it is aab. Because of this natural one-one correspondence, people use them interchangeably.

Theorem 5.2.2. Let n, r ∈ N be fixed. Then |Map([n], [r])| = rn.

Proof. Forming such a function is a task with n compulsory parts, where each part can be done in r
many ways. So, by the product rule, the number of such functions is rn.

Example 5.2.3. 1. How many functions are there from [9] to [12]?
Ans: 129. This task has 9 compulsory parts, where is each part can be done in 12 ways.
2. Determine the number of words of length 9 made with alphabets from {a, b, . . . , z}?
Ans: 269. This task has 9 compulsory parts, where each part can be done in 26 many ways.
3. Suppose 3 distinct coins are tossed and the possible outcomes, namely H and T , are recorded.
For example, the word TTH means that the first two coins have shown T and the third coin has
shown H. Determine the number of possible outcomes.
Ans: It is the same as the number of words of length 3 made using T and H. So, it is 23.
5.2. PERMUTATIONS AND COMBINATIONS 74

PRACTICE 5.2.4. 1. Let n, r ∈ N. In how many ways can r distinct balls be placed into n distinct
boxes?

2. How many ways are there to make 5-letter words (words of length 5) using the ENGLISH alphabet
such that the vowels do not appear at even positions?

3. Determine the number of possible outcomes if three distinct coins and five distinct dice are tossed?

Discussion 5.2.5. [Use of complements] A simple technique which is used very frequently is counting
the complement of a set, when we know the size of the whole set. For example, consider the following
question.
How many 5-letter words can be made using the letters A, B, C, D that do not contain the string
“ADC”? For example, ADCDD, BADCB are not counted but DACAD is counted.
Ans: Let X be the set of all 5-letter words that can be made using A, B, C, D. Then |X| = 45.
Consider the sets A = {words in X of the form ADC ∗ ∗}, B = {words in X of the form ∗ ADC∗}, and
C = {words in X of the form ∗ ∗ADC}. We see that |A| = |B| = |C| = 42 . As the sets A, B, C are
disjoint, we see that |A ∪ B ∪ C| = 3 × 42. Hence our answer to the original question is 45 − 3 × 42.
PRACTICE 5.2.6. 1. Determine the number of functions f : [6] → [5] satisfying f (i) ƒ= i for at least
two values of i?
2. How many 5 digit natural numbers are there that do not have the digit 9 appearing exactly 4
times?

5.2.2 Counting words with distinct letters made with elements of a set S

We now discuss the next combinatorial object namely the one-one functions. For n ∈ N, the term
n-set is used for ‘a set of size n’. Further, n! = 1 · 2 ········ n and by convention, 0! = 1.

Discussion 5.2.7. [Injections] Let n, r ∈ N and X be a non-empty set.

1. An injection f : [r] → X can be viewed as an ordered r-tuple of elements of X with distinct
entries. It can also viewed as a word of length r with distinct letters made with elements of X.
The set of all injections from A to B will be denoted by Inj(A, B).
2. If |X| = r, then a bijection f : X → X is called a permutation of X. If X = {x1, ..... , xr},
then f (x1), ..... , f (xr) is just a rearrangement of elements of X.
3. We define P(n, r) := |Inj([r], [n])|. As a convention, P (n, 0) = 1 for n ≥ 0.

Example 5.2.8. How many one-one maps f : [4] → {A, B, .... , Z} are there?
Ans: The task of forming such a one-one map has 4 compulsory parts: selecting f (1), f (2), f (3)
and f (4). Further, f (2) ƒ= f (1), f (3) ƒ= f (1), f (2) and so on. So, by the product rule, the number of
one-one map equals 26 · 25 · 24 · 23
22! = .
26!

Theorem 5.2.9. [Number of injections f : [r] → S] Let n, r ∈ N and |S| = n. Then the number
P (n, r) = n! .
(n−r)!

Proof. The task is to from an r-tuple (f (1), . . . , f (r)) of distinct elements. It has r compulsory parts,
namely selecting f (1), f (2), . . ., f (r) with the condition that f (k) ƒ∈ {f (1), f (2), . . . , f (k − 1)}, for
2 ≤ k ≤ r. So, using the product rule, P (n, r) = |Inj([r], [n])| = n(n − 1) · · · (n − r + 1) = (n−r)!
n!
.

PRACTICE 5.2.10. 1. How many ways are there to make 5 letter words using the ENGLISH alpha-
bet if the letters must be different?
5.2. PERMUTATIONS AND COMBINATIONS 75

2. How many ways are there to arrange the 5 letters of the word ROY AL?

3. How many bijections f : [12] → [12] are there if a multiple of 3 is mapped to a multiple of 3?

5.2.3 Counting words where letters may repeat

Consider the word AABAB. We want to give subscripts 1, 2, 3 to the A’s and subscripts 1, 2 to
the B’s so that we create words made with A1, A2, A3, B1, and B2. For example, one such word is
A2A3B2A1B1. How many such words can we create? Fill the following table to get all such words.
Notice that each of these words become AABAB when we erase the subscripts.
A1A2B1A3B2 A1A2B2A3B1
A1A3B1A2B2 A1A3B2A2B1

A3A2B1A1B2 A3A2B2A1B1
The following is another useful principle. It is a special case of Exercise [Link].

Proposition 5.2.11. [Principle of disjoint pre-images of equal size] Let A, B be nonempty finite sets
and f : A → B be a function satisfying |f −1 (i)| = k = |f −1 (j)|, for each i, j ∈ B. Then, |A| = k|B|.
In particular, for k = 1 this principle is also called the principle of bijection.

Let n1, . . . , nk ∈ N. Suppose, we are given ni copies of the symbol A i, for i = 1, . . . , k. Then, by
an arrangement of these n1 + · · · + nk symbols, we mean a way of placing them in a row. It is a
word made with the symbols A 1, . . . , Ak containing the symbol Ai exactly ni times, i = 1, . . . , k. For
example, ABBAA is an arrangement of 3 copies of A and 2 copies of B.
Example 5.2.12. 1. How many words of size 5 can be formed using three A’s and two B’s?
Ans: Let A = {arrangements of A 1, A 2, A3, B 1, B 2} and B = {words of size 5 which use three
A’s and two B’s}. For each arrangement a ∈ A, define Er(a) to be the word in B obtained by
erasing the subscripts. Then, the function Er : A → B satisfies:

‘for each b, c ∈ B, b ƒ= c, we have |Er−1(b)| = |Er−1(c)| = 3!2!’.

Thus, by Proposition 5.2.11, |B| = |A3!2!

| = 3!2! .
5!

2. Determine the number of ways to place 4 couples in a row if each couple sits together.
Ans: Let X be the set of all arrangements of A, B, C, D. Let Y be the set of all arrangements
of A, A, B, B, C, C, D, D in which both the copies of each letter are together. For example
AACCDDBB ∈ Y but ABBCCDDA ƒ∈ Y . Let Z be the set of all arrangements of A h, A w,
B h, B w, Ch, Cw, Dh, Dw in which A h, Aw are together, B h, Bw are together, Ch, Cw are together,
and Dh, Dw are together.
In this setting, we need to find the size of Z. So, define Er : Z → Y by Er(z) equals the
arrangement obtained by erasing the subscripts, namely h and w, that appear in z. Notice
that each y ∈ Y has 24 pre-images in Z. Now, define Mrg : Y → X by Mrg(y) equals
the arrangement obtained by merging the two copies of the same letters into one single letter.
For example, Mrg(BBAADDCC) = BADC. Notice that each x in X has exactly one pre-
image in Y . By applying the principle of disjoint pre-images of equal size twice, we see that
|Z| = 24|Y | = 24|X| = 244!, as |X| = 4!.
5.2. PERMUTATIONS AND COMBINATIONS 76

Alternate. Instead of writing it in such a laborious way as the above, let us adopt a more reader
friendly way of writing the same. A couple can be thought of as one cohesive group (they are
to be seated together). So, the 4 cohesive groups can be arranged in 4! ways. But a couple can
sit either as “wife and husband” or “husband and wife”. So, the total number of arrangements
is 24 4!.

Theorem 5.2.13. [Arrangements] Let n, n1, n2, . . . , nk ∈ N and suppose that we have ni copies of
the symbol (object) Ai, for i = 1, . . . , k and that n = n1 + · · · + nk. Then the number of arrangements
of these n symbols is
n!
.
n1!n2! · · · nk!
The formula remains valid even if we take some of the ni’s to be 0.

Proof. Let S be set of all arrangements of the n1 + n2 + · · · + nk symbols and let T be the set of
all arrangements of the symbols A1,1, . . . , A1,n1 , A2,1, . . . , A2,n2 , . . . , Ak,1, . . . , Ak,nk . Define a function
Er : T → S by Er(t) equals the arrangement obtained by erasing the second subscripts that appear
in t. Notice that each s ∈ S has n1!n2! · · · nk! many pre-images. Hence, by the principle of disjoint
pre-images of equal size, we have |T | = n1! · · · nk!|S|. As |T | = (n1 + n2 + · · · + nk)!, we obtain the
desired result.
Assume that some ni’s are 0 (all cannot be 0 as n ∈ N). Then our arrangements do not involve the
corresponding Ai’s. Hence we can use the argument in the previous paragraph and get the number of
arrangements. As 0! = 1, we can insert some 0! in the denominator.
We have an immediate special case.

Corollary 5.2.14. Let m, n ∈ N. Then the number of arrangements of m copies of A and n copies
of B is (m+n)!
m!n!
.

5.2.4 Counting subsets

As an immediate application of Corollary 5.2.14, we have the following result which counts the number
of subsets of size k of a given set S.

Theorem 5.2.15. Let n ∈ N and k ∈ {0, 1, . . . , n}. Then the number of subsets of [n] of size k is
n! .
k!(n−k)!

Proof. If k = 0 or n, then we know that there is only one subset of size k and the formula also gives
us the same value. So, let 1 ≤ k ≤ n − 1 and let X be the set of all arrangements of k copies of T ’s
and n − k copies of F ’s. For an arrangement x = x1x2 . . . xn ∈ X, define f (x1 . . . xn) = {i | xi = T },
i.e., the set of positions where a T appears in x. Then, f is a bijection between X and the set of all
k-subsets of [n]. Hence, the number of k-subsets of [n]|= X | =|X| = , by Corollary 5.2.14.
n!
k!(n−k)!

Discussion 5.2.16. 1. For n ∈ N and r ∈ {0, 1, . . . , n}, the symbol C(n, r) is used to denote the
number of r-subsets of [n]. The value of C(0, 0) is taken to be 1. Many texts use the word ‘r-
combination’ for an r-subset.
N and r = 0, 1, . . . , n, C(n, r) = n! . Also it
2. Using Theorem 5.2.15, we see that for n ∈
0 r!(n−r)!
follows from the definition that C(n, r) = 0 if n < r, and C(n, r) = 1 if n = r.
3. Let n ∈ N and n1, n2, . . . , nk ∈ N0 such that n = n1 + · · · + nk. Then by C(n; n1, . . . , nk) we
denote the number n!
. By Theorem 5.2.13, it is the number of arrangements of n objects
n1 !n2 !···nk !
where ni are of type i, i = 1, . . . , k. By convention, C(0; 0, . . . , 0) = 1.
5.2. PERMUTATIONS AND COMBINATIONS 77

4. If n ∈ N and n1 , . . . , nk−1 ∈ N0 with n1 + · · · + nk−1 < n, we also use C(n; n1 , . . . , nk−1 ) to mean
C(n; n1, . . . , nk−1, n − n1 − · · · − nk−1).

5.2.5 Pascal’s identity and its combinatorial proof

We aim to supply a combinatorial proof of a very well known identity called the Pascal’s identity.

Theorem 5.2.17. [Pascal] Let n and r be non-negative integers. Then

C(n, r) + C(n, r + 1) = C(n + 1, r + 1).

Proof. (This is not the combinatorial proof.) If r > n, then by definition all the three terms are zero.
So, we have the identity. If r = n, then the first and the third terms are 1 and the second term is 0. So,
again we have the identity. So, let us take r < n. Now we can use the formulas for C(n, r), C(n, r + 1)
and C(n + 1, r + 1) to verify the identity.

Sometimes, we want to supply a combinatorial proof of an identity, i.e., by associating the terms
on the left hand side (LHS) and the right hand side (RHS) with some objects and by showing a one
to one correspondence between them. Before we supply a combinatorial proof of Pascal’s identify, the
reader is advised to go through the following experiment to discover that proof on their own.

Experiment
Complete the following list by filling the left list with all 3-subsets of {1, 2, 3, 4, 5} and the right
list with 3-subsets of {1, 2, 3, 4} as well as with 2-subsets of {1, 2, 3, 4} as shown below. Can you
match the sets in the left with the sets in the right in some natural way?

C(4, 3)

C(5, 3)

We now present the combinatorial proof of Theorem 5.2.17.

Proof. If r > n, then by definition all the three terms are zero. So we have the identity. If r = n,
then the first and the third terms are 1 and the second term is 0. So, again we have the identity. So,
assume that r < n.
Let S = {1, 2, . . . , n, n + 1} and A be an (r + 1)-subset of S. Then, by definition, there are
C(n + 1, r + 1) such sets with either n + 1 ∈ A or n + 1 ƒ∈ A.
Note that n + 1 ∈ A if and only if A \ {n + 1} is an r-subset of {1, 2, . . . , n}. So, the number of
(r + 1)-subsets of {1, 2, . . . , n, n + 1} which contain the element n + 1 is, by definition, C(n, r).
Also, n + 1 ∈ / A if and only if A is an (r + 1)-subset of {1, 2, . . . , n}. So, a set A which does not
contain n + 1 can be formed in C(n, r + 1) ways.
Therefore, using the above two cases, an (r + 1)-subset of S can be formed, by definition, in
C(n, r) + C(n, r + 1) ways. Thus, the required result follows.
5.2. PERMUTATIONS AND COMBINATIONS 78

5.2.6 Counting in two ways

Let R and C be two nonempty finite sets and take a function f : R × C → R. View the function
written as a matrix of real numbers with rows indexed by R and columns indexed by C. Then the
total sum of the entries of that matrix can be obtained either ‘by first taking the sum of entries in
each row and then summing them’ or ‘by first taking the sum of the entries in each column and then
summing them’, i.e.,
. Σ
Σ Σ Σ Σ Σ
f (x, y) = f (x, y) = f (x, y) .
(x,y)∈R×C x∈R y∈C y∈C x∈R

This is known as ‘counting in two ways’ and it is a very useful tool to prove some combinatorial
identities. Let us see some examples.
Example 5.2.18. 1. [Newton’s Identity] Let n ≥ r ≥ k be natural numbers. Then

C(n, r)C(r, k) = C(n, k)C(n − k, r − k).

In particular, for k = 1, the identity becomes rC(n, r) = nC(n − 1, r − 1). Ans: Let us use the
method of ‘counting in two ways’. So, we take two appropriate sets R = {all r-subsets of [n]}
and C = {all k-subsets of [n]} and define f on R × C by f (A, B) = 1 if B ⊆ A, and f (A, B) = 0
if B ƒ⊆ A.
Then given a set A ∈ R, it has C(r, k) many subsets of A. Thus,
. Σ
Σ Σ Σ
f (A, B) = C(r, k) = C(n, r)C(r, k).
A∈R B∈C A∈R

Similarly, given a set B ∈ C, there are C(n − k, r − k) subsets of [n] that contains B. Hence,
. Σ
Σ Σ Σ
f (A, B) = C(n − k, r − k) = C(n, k)C(n − k, r − k).
B∈C A∈R B∈C

Hence, the identity is established.

Alternate. We now present the same argument in a more reader friendly manner.
Select a team of size r from n students (in C(n, r) ways) and then from that team select k leaders
(in C(r, k) ways). So, there are C(n, r)C(r, k) ways of selecting a team and it’s leaders from the
team itself. Alternately, select the leaders first in C(n, k) ways and out of the rest select another
r − k to form the team in C(n − k, r − k) ways. So, using this argument, the number of ways of
doing this is C(n, k)C(n − k, r − k).
2. [Important] Let n, r ∈ N, n ≥ r. Then

C(1, r) + C(2, r) + · · · + C(n, r) = C(n + 1, r + 1). (5.1)

The RHS stands for the class F of all the subsets of [n + 1] of size r + 1. Let S ∈ F. Note
that S has a maximum element. A moments thought tells us that the maximum element of
such a set can vary from r + 1 to n + 1. If the maximum of S is r + 1, then the remaining
elements of S have to be chosen in C(r, r) ways. If the maximum of S is r + 2, then the
remaining elements of S has to be chosen in C(r + 1, r) ways and so on. If the maximum
of S is n + 1, then the remaining elements of S has to be chosen in C(n, r) ways. Thus,
C(n + 1, r + 1) = C(r, r) + C(r + 1, r) + · · · + C(n + 1, r) = C(1, r) + C(2, r) + · · · + C(n, r).
Observe that for r = 1, it gives us 1 + 2 + · · · + n = n(n+1)
2 .
5.2. PERMUTATIONS AND COMBINATIONS 79

EXERCISE 5.2.19. 1. In a school there are 17 girls and 20 boys. A committee of 5 students is to
be formed to represent the class.

(a) Determine the number of ways of forming a committee consisting of 5 students.

(b) Suppose the committee also needs to choose two different people from among themselves,
who will act as “spokesperson” and “treasurer”. In this case, determine the number of ways
of forming a committee consisting of 5 students and selecting a treasurer and a spokesperson
among them. Note that two committees are different if
i. either the members are different, or
ii. even if the members are the same, they have different students as spokesperson and/or
treasurer.
(c) Due to certain restrictions, it was felt that the committee should have at least 3 girls. In
this case, determine the number of ways of forming the committee consisting of 5 students.

2. Prove that C(pn, pn − n) is a multiple of p directly from its expression.

3. Determine the number of arrangements of the letters of the word ABRACADABARAARCADA.
4. Prove the following identities using combinatorial arguments.
(a) C(n, r) = C(n, n − r), for non-negative integers n and r.
(b) C(n, r) = C(r, r)C(n − r, 0) + C(r, r − 1)C(n − r, 1) + · · · + C(r, 0)C(n − r, r) for natural
numbers n ≥ r.
(c) C(n, 0)2 + C(n, 1)2 + · · · + C(n, n)2 = C(2n, n) for all n ∈ N.

5. Determine the number of ways of selecting a committee of m people from a group consisting of
n1 women and n2 men, with n1 + n2 ≥ m.

6. How many anagrams (rearrangements of letters) of MISSISSIPPI are there so that no two S
are adjacent?
7. How many rectangles are there in an n × n square? How many squares are there?
8. Supply combinatorial proofs of the following statements.
(a) For each n ∈ N, prove that n! divides the product of n consecutive natural numbers.
(b) For m, n ∈ N, the number (m!)n divides (mn)!.
(c) For n, p ∈ N, the number C(pn, pn − n) is a multiple of p.
(d) Prove combinatorially that 2n|(n + 1) · · · (2n).

9. If n points are placed on the circumference of a circle and all the lines connecting them are
joined, what is the largest number of points of intersection of these lines inside the circle that
can be obtained?
10. How many ways are there to form the word MATHEMATICIAN starting from any side and
moving only in horizontal or vertical directions?
M
M A M
M A T A M
M A T H T A M
M A T H E H T A M
M A T H E M E H T A M
M A T H E M A M E H T A M
M A T H E M A T A M E H T A M
M A T H E M A T I T A M E H T A M
M A T H E M A T I C I T A M E H T A M
M A T H E M A T I C I C I T A M E H T A M
M A T H E M A T I C I A I C I T A M E H T A M
M A T H E M A T I C I A N A I C I T A M E H T A M
5.2. PERMUTATIONS AND COMBINATIONS 80

5.3 Solutions in non-negative integers

There are 3 types of ice-creams available in the market: A, B, C. We want to buy 5 ice-creams in
total. In how many ways can we do that? For example, we can buy 5 of type A or we can buy 3 of A
and 2 of C. In general, suppose we are buying n1 of type A, n2 of type B and n3 of type C. Then, we
must have n1 + n2 + n3 = 5. So, we want to know the number of different possible tuples (n1, n2, n3)
satisfying certain condition(s).
Let us discuss it in a general setup. Recall that N0 := N ∪ {0}. A point p = (p1, . . . , pk) ∈ Nk 0with
p1 +· · · + pk = n is called a solution of x1 +· · · + xk = n in non-negative integers or a solution of
x1 + · · · + xk = n in N0. Two solutions (p1, . . . , pk) and (q1, . . . , qk) are said to be the same if pi = qi,
for each i = 1, . . . , k. Thus, (5, 0, 0, 5) and (0, 0, 5, 5) are two different solutions of x + y + z + t = 10
in N0.

Theorem 5.3.1. [Solutions in N0 ] The number of solutions of x1 +· · ·+xr = n in N0 is C(n+r−1, n).

Proof. Each solution (x1, . . . , xr) may be viewed as an arrangement of n dots and r − 1 bars.
‘Put x1 many dots; put a bar; put x2 many dots; put another bar; continue; and end by putting
xr many dots.’
For example, (0, 2, 1, 0, 0) is associated to | • •| • || and vice-versa. As there are C(n + r − 1, r − 1)
arrangements of n dots and r − 1 bars, we see that the number of solutions of x1 + · · · + xr = n in N0
is C(n + r − 1, n).

Example 5.3.2. Determine the number of words that can be made using all of 3 copies of A and 6
copies of B.
Ans: Note that this number equals the number of arrangements of 3 copies of A and 6 copies of
B. Hence, this number is C(9, 3).
Alternate. First put the three A’s in row. Now put x1 B’s to the left of the first A, x2 B’s between
the first and the second A, x3 B’s between the second and the third A and x4 B’s after the third A.
Thus, we need to find number of solutions of x1 + x2 + x3 + x4 = 6 in N0. By Theorem 5.3.1, the
number is C(6 + 4 − 1, 6) = C(9, 6).

Discussion 5.3.3. The question of finding non-negative integers solutions can also be asked in some
other styles.

1. In how many ways can we place 6 indistinguishable balls into 4 distinguishable boxes?
Taking ni as the number of balls to be put in the i-th box, it is asking us to find number of
solutions of n1 + n2 + n3 + n4 = 6 in N0.
2. A multiset is a generalization of a set where elements are allowed to repeat. For example,
{a, b, a} and {a, a, b} mean the same multisets (imagine carrying all of them in a bag). A set is
also a multiset. How many multisets of size 6 can be made using the symbols a, b, c, d?
Taking na as the number of a’s to be put in the multiset and so on, it is asking us to find
solutions of na + nb + nc + nd = 6 in N0.

Example 5.3.4. 1. Suppose there are 5 kinds of ice-creams available in our market complex. In
how many ways can we buy 15 of them for a party?
Ans: Suppose we buy xi ice-creams of the i-th type. Then, the problem reduces to finding the
number of solutions of x1 + · · · + x5 = 15 in non-negative integers.
5.3. SOLUTIONS IN NON-NEGATIVE INTEGERS 81

2. [Variables are bounded below by other numbers] How many solutions in N0 are there to
x + y + z = 60 such that x ≥ 3, y ≥ 4, z ≥ 5?
Ans: Note that (x, y, z) is such a solution if and only if (x − 3, y − 4, z − 5) is a solution to
x + y + z = 48 in N0. So, the answer is C(50, 2).
3. [Reducing a related problem] In how many ways can we pick integers x1 < x2 < x3 < x4 <
x5, from {1, 2, . . . , 20} so that xi − xi−1 ≥ 3, i = 2, 3, 4, 5? For example, one such choice is
(1, 5, 8, 11, 19).
Ans: For each choice of (x1, x2, x3, x4, x5), note that

(x1 − 1) + (x2 − x1) + · · · + (x5 − x4) + (20 − x5) = 19 i.e., d1 + d2 + d3 + d4 + d5 + d6 = 19

where d1 ≥ 0, d2 ≥ 3, . . ., d5 ≥ 3 and d6 ≥ 0. So, the problem reduces to finding the number of

solutions of n1 + n2 + + n6 = 7 in N0. Hence, the answer is C(12, 5).

Alternate. Take an arrangement of fifteen dots (•’s) and five bars (|’s) such that between two
consecutive bars, there are at least two dots. The position of the bars in each such arrangement
gives us one solution. For example,

• • | • • • | • • • | • •| • • • •|• → (3, 7, 11, 14, 19).

Conversely, each solution can be converted into such an arrangement by the following method:
let n1 be the number of dots present to the left of the first bar; n2 be the number of dots present
between the first bar and the second bar and so on. The problem now has been converted to
count integer solutions of n1 + n2 + n3 + n4 + n5 + n6 = 15, where n1, n6 ≥ 0, n2, n3, n4, n5 ≥ 2.
This is the same as the number of solutions of n1 + n2 + n3 + n4 + n5 + n6 = 7 in N0.

Alternate. Notice that x1, x2 − 3, x3 − 6, x4 − 9, x5 − 12 is a increasing sequence of numbers from

1. . . . , 8. For example, (1, 5, 8, 12, 17) → (1, 2, 2, 3, 5). And from any increasing sequence
of numbers from 1..... , 8 we can get back our original sequence.
So, the problem reduces to counting the number of increasing sequences of length 5 with digits
1, 2, . . . , 8. But, this is the same as the number of 5-multisets of [8], as each multiset can be
sorted to give a unique increasing sequence. Ans: C(12, 5).
4. [Variables are bounded above] In this case problems become harder. How many solutions in
N0 are there to x + y + z = 60 such that 20 ≥ x ≥ 3, 30 ≥ y ≥ 4, 40 ≥ z ≥ 5?
Ans: We are looking for the number of solutions in N0 of x+y +z = 48 such that x ≤ 17, y ≤ 26
and z ≤ 35. So, let A = {(x, y, z) ∈ N30 : x + y + z = 48},
(a) Ax = {(x, y, z) ∈ N03 : x + y + z = 48, x ≥ 18},
(b) Ay = {(x, y, z) ∈ N30 : x + y + z = 48, y ≥ 27}, and
(c) Az = {(x, y, z) ∈ N30 : x + y + z = 48, z ≥ 36}.

We know |A| = C(50, 2). So, the answer equals C(50, 2) − |Ax ∪ Ay ∪ Az|. The calculation of
|Ax ∪ Ay ∪ Az| is left to the reader. A more general formula appears in the next chapter.
EXERCISE 5.3.5. 1. Determine the number of solutions of x + y + z = 7 with x, y, z ∈ N?
2. Find the number of ways to keep n identical objects in r distinct locations, so that location i gets
at least pi ≥ 0 elements, i = 1, 2, , r.
3. Find the number of solutions in non-negative integers of a + b + c + d + e < 11.
5.4. BINOMIAL AND MULTINOMIAL THEOREMS 82

4. How many 4-letter words (with repetition) are there with the letters in alphabetical order?
5. Determine the number of increasing sequences of length r using the numbers 1, 2, . . . , n.
6. How many ways are there to select 10 integers from the set {1, 2, . . . , 100} such that the positive
difference between any two of the 10 integers is at least 3.
7. There are 10 types of ice-creams available in the market. We want to buy 3 ice-creams for each
of 40 students. For example, we may buy 2 of first type and 1 of second type for a student. In
how many ways can this be done?
8. (a) In how many ways can one arrange n different books in m different boxes kept in a row, if
books inside the boxes are also kept in a row?
(b) What if no box can be empty?

9. In a room, there are 2 distinct book racks with 5 shelves each. Each shelf is capable of holding
up to 10 books. In how many ways can we place 10 distinct books in these two racks?
10. How many permutations of a, b, . . . , z have no 2 vowels together?
11. How many rearrangements of 5 copies of a, 5 copies of b, . . . , 5 copies of z have at least two
consonants between any two vowels?
12. How many 10-subsets of {a, b, . . . , z} have a pair of consecutive letters?
13. How many ways (write an expression) are there to distribute 60 identical balls to 5 persons if
Ram and Shyam together get no more than 30 and Mohan gets at least 10?
14. In how many ways can we pick 20 letters from 10 A’s, 15 B’s and 15 C’s?
n Σ
Σ i Σ
i 1 2 ik−1
Σ
15. Evaluate ··· 1.
i1=1 i2=1 i3=1 ik=1

Σ
9 Σ
i Σ
i 1 2 Σ
i 8

16. Evaluate ··· i29.

i1=1 i2=1 i3=1 i9=1
17. There are 10 persons to be seated on chairs with numbers 1 to 10. The first person first comes
and can seat on any chair. Then for i = 2, 3, . . . , 10, the i-th person enters and takes the seat i
if it is available, otherwise any other seat. In how many ways can they be seated?
18. Fix n ∈ N. Then, a composition of n is an expression of n as a sum of positive integers. For
example, if n = 4, then the distinct compositions are

4, 3 + 1, 1 + 3, 2 + 2, 2 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 1 + 1 + 1 + 1.

Let Sk(n) denote the number of compositions of n into k parts. Then, S1(4) = 1, S2(4) =
Σ
3, S3(4) = 3 and S4(4) = 1. Determine Sk(n), for 1 ≤ k ≤ n and Sk(n).
k≥1
19. Let n ≥ 2 be a natural number. Supply a bijection between the set of all compositions of n and
P([n − 1]).
20. How many rearrangements of the letters in ABRACADABARAARCADA such that the first

(a) A precedes the first B?

(b) B precedes the first A and the first D precedes the first C?
(c) B precedes the first A and the first A precedes the first C?
(d) B and A both precede the first C?
(e) B or A precede the first C?
5.4. BINOMIAL AND MULTINOMIAL THEOREMS 83

5.4 Binomial and multinomial theorems

Discussion 5.4.1. 1. By an algebraic expansion of (x+y +z)n let us mean, an expansion where
each term is of the form αxiyjzk, so that two terms differ in the degree of at least one of x, y, z.
For example, x3 + 3x2y + 3xy2 + y3 is an algebraic expansion of (x + y)3.

2. By a word expansion of (x + y + z)n we mean an expansion where each term is a word of

length n using letters x, y, z. For example, xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy is
a word expansion of (x + y)3.

3. Algebraic and word expansions for (x1 + · · · + xr)n are defined similarly.

4. Take the word expansion of (X + Y + Z)4. It contains 34 words each of length 4 made with
X, Y, Z. Imagine a list the words in the order

XXXX, XXXY, XXXZ, XXY X, . . . , ZZZY, ZZZZ.

5. Do you think the word ZXY Z appears in the list? At which position? It is not difficult to
see that it appears in the position 1 + (2012)3, where (2012)3 is the value computed in base 3.
(Prove this by induction!)

6. In fact, each possible word of length 4 that can be made with X, Y, Z, appears somewhere in
the word expansion of (X + Y + Z)4 .

7. How many words in the list have two Z’s, one X and one Y ? The answer must be all possible
arrangements of Z, Z, X, Y which is 4!2!1!1!
.

8. Hence, the coefficient of XY Z2 in the algebraic expansion of (X + Y + Z)4 must be 4! = 2!1!1!

C(4; 2, 1, 1). We express this by writing
Σ Σ
cf XY Z 2 , (X + Y + Z)4 = C(4; 2, 1, 1).

Theorem 5.4.2. [Multinomial Theorem] Let n, k ∈ N and n1, . . . , nk ∈ N0 with n = n1 + · · · + nk.

Then
Σ Σ
cf x1n 1 x2n2 · · · xknk , (x1 + · · · + xk )n = C(n; n1 , · · · , nk ).
So Σn
(x1 + · · · + xk) n = C(n; n 1, · · · , nk)xn1 · · · xnk .
1 k
n1, · · · , nk ≥ 0
n1 + · · · + nk = n
Proof. It is clear that the word expansion of (x1 + · · · + xk)n contains all possible words of length n
made with letters x1, . . . , xk. The coefficient of xn11 xn2 2· · · xnkk is given by the words of length n that
are made with n1 copies of x1, n2 copies of x2, . . ., nk copies of xk. As we already know, there are
n!
such words. Hence, the first identity follows. The second identity follows from the first one.
n1 !n2 !···nk !

Theorem 5.4.3. [Binomial Theorem] Let n ∈ N and 0 ≤ i ≤ n be an integer. Then

Σ Σ
Σn
cf xi yn −i, (x + y) n = C(n, i) or (x + y) = n
C(n, k)xn −k yk.
k=0

Proof. Follows from Theorem 5.4.2.

5.4. BINOMIAL AND MULTINOMIAL THEOREMS 84

Remark 5.4.4. Let n ∈ N and n1, . . . , nk ∈ Z such that n = n1 + · · · + nk. Then, as the term
xn1 xn2 · · · xnk does not appear in the expression of (x1 + · · · + xk)n, we can think that the coefficient
1
Σ 2 k Σ
cf xn11 xn22 · · · xnkk , (x1 + · · · + xk )n = 0. Defining C(n; n1 , · · · , nk ) = 0 if any of the ni ’s is negative,
we now see that the multinomial theorem remains valid even for n1, . . . , nk ∈ Z. A similar comment
is true for the binomial theorem too.
The numbers C(n, r) and C(n; r1, . . . , rk) are thus known as ‘binomial coefficients’ and ‘multinomial
coefficients’, respectively. An immediate and important corollary to the binomial theorem is the
following.

Corollary 5.4.5. Let n ∈ N. Then the total number of subsets of [n] is 2n. (We can also prove this
statement using some other arguments. See the exercises.)

Proof. The number of subsets of size k is C(n, k). Thus the total number of subsets is C(n, 0) +
C(n, 1) + · · · + C(n, n) which is (1 + 1)n by the binomial theorem.
The example below show how the multinomial coefficients can be seen as an additional tool in our
study.
Σ
k
Example 5.4.6. 1. Fix m, n, k ∈ N. Then show that C(m + n, k) = C(m, i) C(n, k − i).
i=0
Ans: First, we give an argument using counting in two ways. We can form a committee of size
k from a group consisting of m men and n women in C(m + n, k) ways. On the other hand, such
a committee can be formed by taking i many men and n − i many women, where 0 ≤ i ≤ k. In
Σ
k
this way our answer is C(m, i) C(n, k − i). Hence, they are the same.
i=0
Alternate. We now give an argument using the binomial coefficients. We have C(m + n, k) =
Σ Σ Σ Σ
cf xk y m+n −k , (x + y)m+n = cf xk y m+n−k , (x + y)m (x + y)n
Σ Σ Σ k−i n−k+i Σ C(m, i)C(n, k − i).
Σ k cf xi y m−i , (x + y) m
cf x y , (x + y) n = k
= Σ
i=0 Σ
n
2. Let n > m be natural numbers. Prove that C(k, m)C(n, k) =i=0C(n, m)2 n−m .
k=m
Ans: Recall that C(k, m)C(n, k) = C(n, m)C(n − m, k − m). Hence,
n n n
Σ Σ Σ
C(k, m)C(n, k) = C(n, m)C(n − m, k − m) = C(n, m) C(n − m, k − m)
k=m k=m k=m
Σ
n−m
= C(n, m) C(n − m, s) = C(n, m)2n−m.
s=0

Alternate. Noticing a combinatorial proof is relatively harder. The RHS stands for (A, B)
where A ⊆ [n] of size m and B ⊆ [n] \ A. For each fixed A, we have 2n−m choices of B, and
this is why we have the RHS. On the other hand, we can first select a big set C of size |C| ≥ m.
From this set C, we will take a subset A of size m and we will treat the remaining as B. The
LHS expresses the number of ways in which this task can be done.

Alternate. Yet another way to see it is to notice that C(n, k)C(k, m) = C(n; m, k − m, n − k),
Σ
which is cf x y − z − , (x + y + z) Σ. Since, m is fixed (and x’s can appear in any m of the
m
n places) this coefficient equals
k m n k n
Σ
n−m Σ Σ
C(n, m) cf yk−m zn−k, (y + z)n−m = C(n, m)2n−m.
k−m=0
5.4. BINOMIAL AND MULTINOMIAL THEOREMS 85

3. Determine the number of words of size 5 using letters from ‘MATHEMATICIAN’ (including
multiplicity, i.e., you may use M at most twice).
Ans: Note that to form such a word, suppose we have selected xm many M ’s, xa many A’s,
and so on. Then, the problem reduces to finding the number of solutions in non-negative
numbers to xm + xa + xt + xh + xe + xi + xc + xn = 5, with 0 ≤ xm, xt, xi ≤ 2, 0 ≤ xa ≤ 3,
0 ≤ xh, xc, xn, xe ≤ 1. In that case the number of words that can be formed from them is
C(5; xm, xt, xi, xa, xh, xc, xn, xe). Hence, the total number of such words is
Σ
C(5; k1, · · · , k8).
k1+···+k8=5
k1≤2,k2≤3,k3≤2,k4≤1,k5≤1,k6≤2,k7≤1,k8≤1

EXERCISE 5.4.7. 1. Show that |P({1, 2, . . . , n})| = 2n in the following ways.

(a) By using ‘select a subset is a task with n compulsory parts’.
(b) By associating a subset with a 0-1 string of length n and evaluating their values in base-2.
(c) Arguing in the line of ‘a subset of {1, 2, . . . , n, n + 1} either contains n + 1 or not’ and using
induction.

2. Let S be a set of size n. Then, prove in two different ways that the number of subsets of S of
odd size is the same as the number of subsets of S of even size. That is,
Σ Σ
C(n, 2k) = C(n, 2k + 1) = 2n−1.
k≥0 k≥0

Σ
t Σ
n
3. Show that C(n, A) = C(t, k) C(n − t, A − k) = C(t, k) C(n − t, A − k), for any t, 0 ≤ t ≤ n.
k=0 k=0
Σ
r
4. Show that C(n + r + 1, r) = C(n + A, A).
A=0
Σ
n
5. We already have seen a combinatorial proof of C(n + 1, r + 1) = C(A, r). Supply a different
A=r
proof by manipulating the binomial coefficients.

6. We know that rC(n, r) = nC(n − 1, r − 1). Use it to evaluate the following sums.
Σ
n
(a) Evaluate rC(n, r) for n ≥ 3.
r=0
Σ
n
(b) Evaluate (2k + 1) C(n, 2k + 1) for n ≥ 3.
k=0
Σn
(c) Evaluate (5k + 3) C(n, 2k + 1) for n ≥ 3.
k=0
Σn
(d) Evaluate r2C(n, r) for n ≥ 3.
k=0

Σ
n n(n + 1)
7. For each i, n ∈ N, define Si(n) = k i. Then, we know that S1(n) = , S2(n) =
k=1 2
n(n + 1)(2n + 1) Σ2
.
n(n + 1) . Determine S4(n). Also, find a recursive method
and S3(n) =
6 2
to find closed form expression for Si(n), for i ≥ 5.
8. For n ∈ N, k1, . . . , km ∈ N such that k1 + · · · + km = n, show that

C(n; k1, . . . , km) = C(n − 1; k1 − 1, . . . , km) + · · · + C(n − 1; k1, . . . , km − 1).

This is called the generalized Pascal’s identity.

5.4. BINOMIAL AND MULTINOMIAL THEOREMS 86

9. For n, m ∈ N, evaluate
Σ
C(n; k1, . . . , km).
k1,...,k m∈N0
k1+...+km=n

10. Let m, n ∈ N. How many terms are there in the (algebraic) expansion of (x1 + x2 + · · · + xm)n?
How many terms involve at least one of each xi, i = 1, . . . , n? How many terms involve at least
two x1 and at most five x1?
Σr
11. Let n, r ∈ N. By the binomial theorem, we know that (n + 1)r = C(r, k)nk . Supply a
k=0
combinatorial proof by using Map([r], [n]).
12. For n, m ∈ N and r = | m ∫2 (greatest integer function) evaluate
Σ
(−1)k2 +k4 +···+k2r C(n; k1 , . . . , km ).
k1,...,km∈N0
k1+...+km=n

5.5 Circular arrangements

Let S be a nonempty finite multiset. By a circular arrangement of elements of S, we mean an
arrangement of the elements of S on a circle. Two circular arrangements are the same if each element
has the same ‘clockwise adjacent’ element, i.e., one can be obtained as a rotation of the other. By
[x1, x2, . . . , xn, x1], we shall denote a circular arrangement, keeping the anticlockwise direction in a
picture. We use the word circular permutation if elements of S are distinct. Thus, exactly two of
the following pictures represent the same circular permutation.

[A1, A2, A3, A4, A5, A1] [A1, A5, A4, A3, A2, A1]

Figure 5.1: Circular permutations

Example 5.5.1. Determine the number of circular permutations of X = {A1, A2, A3, A4, A5}.
Ans: 4!. Let B = {circular permutations of X} and A = {permutations of X}. Now, define
f : A → B as f (a) = b if a is obtained by breaking the cycle b at some gap and then following in
the anticlockwise direction. For example, if we break the leftmost circular permutation in Figure 5.1
at the gap between A1 and A2 , we get [A2 , A3 , A4 , A5 , A1 ]. Notice that |f −1 (b)| = 5, for each b ∈ B.
Further if b, c ∈ B, then f −1(b) ∩ f −1(c) = ∅ (why?1). Thus, by the principle of disjoint pre-images
of equal size, the number of circular permutations is 5!/5.

Theorem 5.5.2. [Circular permutations] The number of circular permutations of {1, 2, . . . , n} is

(n − 1)!.

Proof. A proof may be obtained on the line of the previous example. Here we give an alternate proof.
Put A = {circular permutations of {1, 2, . . . , n − 1, n}}. Put B = {permutations of {1, 2, . . . , n −
Think of creating the circular permutation from a given permutation.
1
5.5. CIRCULAR ARRANGEMENTS 87

1}}. Define f : A → B as f ([n, x1, x2, . . . , xn−1, n]) = [x1, x2, . . . , xn−1]. Define g : B → A as
g([x1, x2, . . . , xn−1]) = [n, x1, x2, . . . , xn−1, n]. Then, g ◦ f (a) = a, for each a ∈ A and f ◦ g(b) = b, for
each b ∈ B. Hence, by the bijection principle (see Theorem 1.5.5) f is a bijection.

Example 5.5.3. Find the number of circular arrangements of {A, B, B, C, C, D, D, E, E}.

Ans: There is only one A. Cutting A out from a circular arrangement we get a unique arrangement
of {B, B, C, C, D, D, E, E}. So, the required answer is 8! .2!4
Definition 5.5.4. 1. Given an arrangement (not a circular arrangement) [X1, . . . , Xn] by a rota-
tion R1([X1, . . . , Xn]), in short R1(X1, . . . , Xn), we mean the arrangement [X2, . . . , Xn, X1] and
by R2(X1, . . . , Xn) we mean the arrangement [X3, . . . , Xn, X1, X2]. On similar lines, we define Ri,
i ∈ N and put R0(X1, . . . , Xn) = [X1, . . . , Xn]. Thus, for each k ∈ N,

R0(X1, . . . , Xn) = Rkn(X1, . . . , Xn) = [X1, . . . , Xn].

2. The orbit size of an arrangement [X1, . . . , Xn] is the smallest positive integer i which satisfies
Ri(X1, . . . , Xn) = [X1, . . . , Xn]. In that case, we call
, ,
R0 (X1 , . . . , Xn ), R1 (X1 , . . . , Xn ), . . . , Ri−1 (X1 , . . . , Xn )

the orbit of [X1, . . . , Xn].

Discussion 5.5.5. 1. We have R 1(ABCABCABC) = [BCABCABCA], R2(ABCABCABC) =
[CABCABCAB] and R3(ABCABCABC) = [ABCABCABC]. Thus, the orbit size of [ABCABCABC]
is 3.
2. An arrangement of S = {A, A, B, B, C, C} with orbit size 6 is [AABCBC]. An arrangement of
S with orbit size 3 is [ACBACB].
3. There is no arrangement of S = {A, A, B, B, C, C} with orbit size 2. In fact, if there is an
arrangement with orbit size 2 then it’s form, by definition, must be [X1X2X1X2X1X2]. Thus
the element X1 repeats at least 3 times in S, which is not possible.
4. There is no arrangement of {A, A, B, B, C, C} with orbit size 1 or 2 or 4 or 5.
5. There are 3! arrangements of {A, A, B, B, C, C} with orbit size 3.
6. Take an arrangement of {A, A, B, B, C, C} with orbit size 3. Make a circular arrangement by
joining the ends. How many distinct arrangements can we generate by breaking the circular
arrangement at gaps?
Ans: 3. They are the elements of the same orbit.
7. Take an arrangement of {A, A, B, B, C, C} with orbit size 6. Make a circular arrangement by
joining the ends. How many distinct arrangements can we generate by breaking the circular
arrangement at gaps?
Ans: 6. They are the elements of the same orbit.
8. Take an arrangement of n elements with orbit size k. Make a circular arrangement by joining the
ends. How many distinct arrangements can we generate by breaking the circular arrangement
at gaps?
Ans: k. They are the elements of the same orbit.
9. If we take the set of all arrangements of a finite multiset and group them into orbits (notice that
each orbit gives us exactly one circular arrangement), then the number of orbits is the number
of circular arrangements.
5.5. CIRCULAR ARRANGEMENTS 88

Proposition 5.5.6. The orbit size of an arrangement of an n-multiset is a divisor of n.

Proof. Suppose, the orbit size of [X1, . . . , Xn] is k and n = kp + r, for some r, 0 < r < k. Then,

Rk(X1, . . . , Xn) = R2k(X1, . . . , Xn) = · · · = Rkp(X1, . . . , Xn) = Rk−r(X1, . . . , Xn)

as (p+1)k = pk+k = n−r+k ≡ k−r (mod n). Thus, Rk−r(X1, . . . , Xn) = [X1, . . . , Xn], contradicting
the minimality of k. Hence, r = 0. Equivalently, k divides n.

Example 5.5.7. Find the number of circular arrangements of S = {A, A, B, B, C, C, D, D, E, E}.

Ans: How many arrangements are there of orbit size 1? 0.
How many arrangements are there of orbit size 2? 0.
How many arrangements are there of orbit size 3? 0.
How many arrangements are there of orbit size 4? 0.
How many arrangements are there of orbit size 5? 5!.
How many arrangements are there of orbit size 6, 7, 8, 9? 0.
How many arrangements are there of orbit size 10? 2!2!2!2!2!
10!
− 5!.
The number of circular arrangements generated by those of orbit size 5 is 5!/5. The number of
circular arrangements generated by those of orbit size 10 is 10!
− 5! . Thus the total number of
2!2!2!2!2!10 10
circular arrangements is 4! +2!2!2!2!2!10
10!
− 10.
5!

Discussion 5.5.8. [Binary operations] We want to provide another way to count the number of
circular arrangements. Let [X 1, . . . , X n] and [Y1, . . . , Yn] be two arrangements of an n-multiset. Then,
in the remainder of this section, we shall consider expressions like [X 1, . . . , X n] + [Y1, . . . , Yn]. By
[R i+R j](X 1, . . . , Xn), we mean the expression R i(X 1, . . . , X n)+R j(X 1, . . . , Xn). By Ri([X 1, . . . , X n]+
[Y1, . . . , Yn]) we denote the expression R i(X 1, . . . , X n) + R i(Y1, . . . , Yn).

Example 5.5.9. Think of all arrangements P1, . . . , Pn, of two A’s, two B’s and two C’s, where
. How many copies of [ABCABC] are there in [R0 + · · · + R5](P1 + · · · + Pn)?
n = 6!2!2!2!
Ans: Of course 6. To see this, note that R0, R3 take [ABCABC] to itself; R1, R4 will take
[CABCAB] to [ABCABC]; R2, R5 will take [BCABCA] to [ABCABC]; and no other arrangement
after rotation will give [ABCABC].

Proposition 5.5.10. Let P1, . . . , Pn be all the arrangements of an m-multiset. Then,

[R0 + · · · + Rm−1](P1 + · · · + Pn) = m(P1 + · · · + Pn).

Proof. In fact, [R0 + · · · + Rm−1](P1 + · · · + Pn) means, take all arrangements and apply all rotations
(R0, . . . , Rm−1), and collect all resulting arrangements.
Note that, if we apply R0 on (P1 + · · · + Pn ), we get one copy of each arrangement. Similarly, if we
apply Ri on (P1 + · · · + Pn ), we get one copy of each arrangement. So, [R0 + · · · + R m−1 ](P1 + · · · + Pn )
will contain m copies of each arrangement.

Proposition 5.5.11. Let P be an arrangement of an m-multiset which has orbit size k. Then the
number of rotations Ri, i = 0, 1, . . . , m−1 which fix P (that is, satisfy Ri(P ) = P ) is mk. Furthermore,
m
[R0 + R1 + · · · + Rm−1](P ) = orbit(P ).
k
Proof. As k is the orbit size of P , we already know that k divides m. Put p = m/k. Then
R0, Rk, . . . , R(p−1)k fix P . If there is any other s such that Rs fixes P , then noting that s is not
5.5. CIRCULAR ARRANGEMENTS 89

a multiple of k, let s = kj + r, where 0 < r < k. It now follows that Rr(P ) = P . This is a
contradiction to the fact that k is the orbit size of P .
The next assertion follows from the fact that

[R0 + · · · + Rk−1](P ) = [Rk + · · · + R2k−1](P ) = · · · = [R(p−1)k + · · · + Rpk−1](P )

is the orbit(P ).

Discussion 5.5.12. Let P be an arrangement of an m-multiset S which has orbit size k. Recall that
each orbit accounts for one circular arrangement of objects in S. Thus [R0 + · · · + Rm−1](P ) accounts
for m/k counts of the same circular arrangement.
Now, let P1, . . . , Pn be all the arrangements of objects in S. Then,

Σ Σ
(the number of rotations fixing Pi ) orbit(Pi ) = [R0 + · · · + R m−1 ](Pi )
Pi Pi
= m(P1 + · · · + Pn)
= m(all circular arrangements).

The number of circular arrangements contained in the LHS being the same as that of the RHS, we
Σ
get that the total number of all circular arrangements is 1m the number of rotations fixing Pi. But,
Pi
notice that

Σ Σ
the number of rotations fixing Pi = |{Rj|Rj(Pi) = Pi}|
Pi Pi
= |{(Pi, Rj)|Rj(Pi) = Pi}|
Σ
= |{P i|R j(P i) = P i}|
Rj
Σ
= the number of P i’s fixed by R j.
Rj

Hence, the total number of circular arrangements is

1 Σ
the number of Pi ’s fixed by R .j
m
Rj a rotation

Example 5.5.13. 1. How many circular arrangements of {A, A, A, B, B, B, C, C, C} are there?

Ans: First way:

orbit size no of arrangements no of circular arrangements
1 0 0
2 0 0
3 3! 3!
3 =2
4, 5, 6, 7, 8 0 0
9!
9! −3!
9 3!3!3! − 3! 3!3!3!
9 = 186
Total 188

Second way:
5.5. CIRCULAR ARRANGEMENTS 90

Rotations no of arrangements fixed by it

9!
R0 3!3!3!
R1 0
R2 0
R3 3!
R 4, R 5, R 7 , R 8 0
R6 3!
Total [Link] + 3! + 3!
Thus, the number of circular arrangements is

[Link] + 12 ([Link] + 4) 564

= = = 188.
9 3 3

2. Determine the number of circular arrangements of size 5 using the alphabets A, B and C.

Ans: First way:

orbit size no of arrangements no of circular arrangements
1 3 3
2, 3, 4 0 0
5−3
5 35 − 3 3
5 = 48
Total 51
Second way:
Rotations no of arrangements fixed by it
R0 35
R1 3
R2 3
R3 3
R4 3
Total 3 +3+3+3+3
5

35 +4·3
Hence, the number of circular arrangements is 5 = 51.

Verify that the answer will be 8 if we have just two alphabets A and B.

EXERCISE 5.5.14. 1. If there are n girls and n boys then what is the number of ways of making
them sit around a circular table in such a way that no two girls are adjacent and no two boys
are adjacent?

2. Let us assume that any two garlands are same if one can be obtained from the other by rotation.
Then, determine the number of distinct garlands that can be formed using 6 flowers, in the
following cases.

(a) The flowers can have colors ‘red’ or ‘blue’.

(b) The flowers can have the colors ‘red’, ‘blue’ or ‘green’.

3. Let us assume that any two garlands are same if one can be obtained from the other by rotation.
Then, determine the number of distinct garlands that can be formed using 6 flowers, 4 of which
are blue and 2 are red.

4. Find the number of circular permutations of {A, A, B, B, C, C, C, C}.

5.6. SET PARTITIONS 91

5. Let us assume that any two garlands are same if one can be obtained from the other by rotation.
Then, determine the number of distinct garlands that can be formed using 6 flowers which can
have colors, R1, . . . , Rk.

6. Persons P1, . . . , P100 are seating on a circle facing the center and talking. With this situation
find answers to the following questions.

(a) If Pi tells lies, then the person to his right tells truths. What is the minimum possible
number of persons telling truths? Give a circular arrangement of L and T showing that the
minimum is attainable. What is the orbit size of this circular arrangement?
(b) What if we change the condition to ‘if Pi tells lies, then the second person to his right tells
truths’? Give a circular arrangement of L and T showing that the minimum is attainable.
What is the orbit size of such a circular arrangement?
(c) What if we change the condition: ‘if Pi talks lie, then the next two persons to his right talk
truth’? Give a circular arrangement of L and T showing that the minimum is attainable.
What is the orbit size of this circular arrangement?

5.6 Set partitions

Discussion 5.6.1. There are 9 balls with numbers 1, 2, . . . , 9 written on them. Imagine that we have
to carry them in two identical polythene bags, without having a bag empty. In how many ways, can
we do that? Well, we can carry them like
{1}, {2, 3, 4, 5, 6, 7, 8, 9} or
{1, 2, 9}, {3, 4, 5, 6, 7, 8} and other ways.
Notice that {1, 2, 9}, {3, 4, 5, 6, 7, 8} and {3, 4, 5, 6, 7, 8}, {1, 2, 9} do not give us different ways of
carrying as the bags are identical.

Let S be a nonempty set and k ∈ N. A partition of S into k subsets means a collection of k

pairwise disjoint nonempty subsets of S whose union is S. For brevity, a partition of S into k subsets
is called a k-partition of S.
. Σ . Σ
Example 5.6.2. 1. (a) Each of the collections 1, 2 , 3{, 4, 5, } {6 ,}1,{3 , 2 , 4,
} 5, 6{ and
} { } { }
. Σ
{1, 2, 3, 4}, {5}, {6} is a 3-partition of [6], whereas the collection {{1, 2, 3}, {3, 4, 5, 6}} is not
a partition of any set.

2. There are 2n−1 − 1 ways to obtain a 2-partition of [n]. To see this, observe that, if n = 1, then
we cannot have a 2-partition of [1] and the formula also gives the value 0. So let n ≥ 2. For each
non-trivial A ⊆ [n] (that is, A ƒ= ∅, [n]), the set {A, A c} is a 2-partition of [n]. Since {A, A c} and
{Ac, A} are regarded as the same 2-partition and since, the total number of non-trivial subsets
of [n] equals 2n − 2, the required number is 2n−1 − 1.

3. Number of allocations of 7 students into 7 different project groups so that each group has one
student, is 7! = C(7; 1, 1, 1, 1, 1, 1, 1) but the number of partitions of a set of 7 students into 7
subsets is 1.
, ,
Discussion 5.6.3. 1. In how many ways can we write {1, 2}, {3, 4}, {5, 6}, {7, 8, 9}, {10, 11, 12}
on a piece of paper, with the condition that sets have to be written in a row in increasing size?
5.6. SET PARTITIONS 92

Ans: Let us write a few first.

, ,
{1, 2}, {3, 4}, {5, 6}, {7, 8, 9}, {10, 11, 12} correct
, ,
{2, 1}, {3, 4}, {5, 6}, {7, 8, 9}, {10, 11, 12} correct
, ,
{5, 6}, {3, 4}, {1, 2}, {10, 11, 12}, {9, 7, 8} correct
, ,
{2, 3}, {1, 4}, {5, 6}, {7, 8, 9}, {10, 11, 12} incorrect, not the same partition
, ,
{2, 1}, {3, 4}, {7, 8, 9}, {5, 6}, {10, 11, 12} incorrect, not satisfying the condition

There are 3!(2!)3 × 2!(3!)2 ways. Notice that from each written partition, if we remove the
brackets, then we get an arrangement of elements of {1, 2, . . . , 12}.
2. How many arrangements do we generate from a partition which has pi subsets of size ni, where
n1 < · · · < n k?
k
Y
Ans: p1 !(n1 !) · · · pk !(nk !)
p1 pk
= [pi !(ni !)pi ].
i=1

Theorem 5.6.4. [Set partition] The number of partitions of [n] consisting of pi subsets of size ni,
i = 1, 2, . . . , k where n1 < · · · < nk, is
n!
.
(n !)1p1 p ! 1· · · (nk !)pk pk!
Proof. Let X be the set of all arrangements of elements of [n] and Y be the set partitions of [n] of
the given type. Take any x = x1 . . . xn be arrangement of elements of [n]. Since we know that the
sets in the partition have to be in the increasing order of their sizes, this arrangement naturally gives
us a way to construct the partition. To do this take the first n1 letters of this arrangement and make
a set. Take the next n1 letters and make a set. Do this p1 times. Then take the next n2 letters and
make a set. Continue similarly to finish the job. In fact, once an arrangement x is given, there is only
a unique partition of the above type that we will get in this way. Call the resulting partition f (x).
Thus we have defined a function f : X → Y .
Qk
Note that each partition y ∈ Y generates [pi !(ni !)pi ] arrangements of elements of [n]. This
i=1
k
Q
−1
means |f (y)| = [pi!(ni!) ]. Hence, by the principle of disjoint pre-images of equal size, we have
pi
i=1
|Y | =
n!
(n1 !)p1 p1 !···(nk !)pk pk ! .
Let n, r ∈ N. Then the number of r-subsets of [n] is called the Stirling numbers of the second
kind and is denoted by S(n, r). By convention, S(0, 0) = 1 and S(n, 0) = 0 for n ∈ N.

Example 5.6.5. We have S(5, 5) = 1, as the only way to make a 5-partition of [5] is to consider
{{1}, {2}, . . . , {5}}.
We have S(5, 1) = 1, as the only way to make a 1-partition of [5] is to consider {[5]}.
We have S(5, 10) = 0, as there is no way we can make a 10-partition of [5].
We have S(5, 2) = 15, as the formula is 2n−1 − 1.
We have S(50, 49) = C(50, 2), as we will have exactly one doubleton set in our partition and rest
will be singletons and a subset of size of [50] can be chosen in C(50, 2) ways.

Theorem 5.6.6. [Recurrence for S(n, r)] Let n, r ∈ N. Then S(n + 1, r) = S(n, r − 1) + rS(n, r).

Proof. If r = 1, then the verification is trivial. So let r > 1. Take an r-partition F of [n + 1]. If
{n + 1} is an element of F , then removing that element from F we get an (r − 1)-partition of [n].
5.6. SET PARTITIONS 93

If {n + 1} is not present in F , then n + 1 is present in some part with some other elements. Now,
if we remove n + 1 from that part, we get an r-partition of [n]. Note that, given any r-partition of
[n], by inserting n + 1 into any of these r parts, we can create r many r-partitions of [n + 1]. Hence,
S(n + 1, r) = S(n, r − 1) + rS(n, r).

Example 5.6.7. Determine the number of ways of putting n distinct balls into r identical boxes with
the restriction that no box is empty.
Ans: Make an r-partition of the set of these balls in S(n, r) ways. One part goes to one box.
Since boxes are identical, this can be done in one way. So the answer is S(n, r).

To proceed further, consider the following example.

Example 5.6.8. Let A = {a, b, c, d, e} and define an onto function f : A → S by f (a) = f (b) =
f (c) = 1, f (d) = 2 and f (e) = 3. Then, the collection {f −1 = {a, b, c}, f −1(2) = {d}, f −1(3) = {e}}
gives a 3-partition of A.
. Σ
Conversely, take a 3-partition of A, say, A1 = {a, d}, A2 = {b, e}, A3 = {c} . Then, this par-
tition gives 3! onto functions fi from A into [3]. Each of them is related to a one-one function gi
: {A 1, A 2, A 3} → [3]. We list them below. Notice that fi(p) = gi(A r) if p ∈ A r.

A1 A2 A3 a b c d e
g1 1 2 3 f1 1 2 3 1 2
g2 1 3 2 f2 1 3 2 1 3
g3 2 1 3 → f3 2 1 3 2 1
g4 2 3 1 f4 2 3 1 2 3
g5 3 1 2 f5 3 1 2 3 1
g6 3 2 1 f6 3 2 1 3 2

Lemma 5.6.9. Let n, k ∈ N. Then the number of onto functions from [n] to [k] is S(n, k)k!.

Proof. Let X be the set of all onto functions from [n] to [k] and Y be the set of all k-partitions of [n].
Observe that, when f : [n] → [k] is an onto function, then {f − 1(1), ...,f −1(k)} is a unique
k-partition of [n]. Keeping that in mind, we define F : X → Y as F (f ) = {{f −1(1),
. . . , f −1(k)}.
On the other hand, given a k-partition α = {S1, . . . , S k} of [n], we can define k! onto functions
f : [n] → [k] by taking a one-one function σ : {S1, . . . , S k} → [k] and then defining f (p) = σ(Si) if
p ∈ Si, i = 1, . . . , k. This means |F −1(α)| = n!, for each α ∈ Y .
Hence, by the principle of disjoint pre-images of equal size, we have |X| = k!S(n, k).

Lemma 5.6.10. Let n, m ∈ N. Then,

Σ
n
nm = C(n, k)k!S(m, k). (5.2)
k=1

Proof. The LHS is the number of all functions f : [m] → [n].

On the other hand, any function f : [m] → [n] is an onto function from [m] to rng f , and rng f
can only be a nonempty subset of [n]. So, we can first select a subset A ⊆ [n] of size k ≥ 1 and then
consider all onto functions f : [m] → A. This has to be done for each subset A of size k and for each
k = 1, . . . , n. Choosing a subset A of size k can be done in C(n, k) many ways and there are k!S(m, k)
many onto functions from [m] to A. So the total number of functions becomes the expression in the
RHS.
5.6. SET PARTITIONS 94

Σ
n Σ
n
Proposition 5.6.11. Let n, k ∈ N. Then S(n + 1, k + 1) = C(n, i)S(n − i, k) = C(n, i)S(i, k).
i=0 i=0

Proof. Imagine forming a (k + 1)-partition of [n + 1]. The number n + 1 must belong to some part.
Suppose there are i other elements in this part. They can be chosen in C(n, i) ways. The rest of the
elements of the set [n + 1] must get divided into k parts in S(n − i, k) ways. Since i varies from 0 to
n, we have the identity. As C(n, i) = C(n, n − i), we get the second equality.

Remark 5.6.12. 1. Recall that the number of onto functions f : [n] → [m] is the same as the
number of ways to put n distinct objects 1, 2, . . . , n into m distinct boxes 1, 2, . . . , m. In fact,
this is how, we counted the total number of such functions to be mn.

2. The number of onto functions f : [n] → [m] is the same as the number of ways to put n distinct
balls into m distinct boxes, so that no box is empty.

3. The numbers S(r, k) can be recursively calculated using Equation (5.2). For example, S(5, 3) =
S(4, 2) + 3S(4, 3) = 24−1 − 1 + 3C(4, 2) = 7 + 18 = 25.

Summary of some work done till now

1. In how many ways can we distribute n distinct books to r students, if there is no restriction
at all? All functions : rn.
2. In how many ways can we distribute n distinct books to r students, if each student gets at
most one book? All injections : C(r, n)n!.
3. In how many ways can we distribute n distinct books to r students, if each student gets at
least one book? All onto functions : S(n, r)r!.
4. In how many ways can we carry n distinct books in r identical bags, if there is no restriction
Σ
r
at all? All partitions : S(n, i).
i=0
5. In how many ways can we carry n distinct books in r identical bags, if each bag contains at
most one book? Partition into singletons : 1.
6. In how many ways can we carry n distinct books in r identical bags, if each bag contains at
least one book? All r-partitions : S(n, r).
7. In how many ways can we distribute n identical books to r students, if there is no restriction
at all? All non-negative integer solutions : C(n + r − 1, r − 1).
8. In how many ways can we distribute n identical books to r students, if each student gets at
most one book? All n-subset of [r] : C(r, n).
9. In how many ways can we distribute n identical books to r students, if each student gets at
least one book? All positive integer solutions : C(n − 1, r − 1).
EXERCISE 5.6.13. 1. Determine the number of ways of carrying 20 distinct heavy books with 4
identical bags if each bag contains 5 books?
2. Determine the number of ways of distributing 20 distinct toys among 4 children if each children
gets 5 toys?
3. We know that S(n, 1) = 1 and S(n, 2) = 2n−1 − 1. Give a formula for S(n, 3).
5.7. NUMBER PARTITIONS 95

Σ
n
4. For n ∈ N, let Bell(n) denote the number of partitions of the set [n], i.e., Bell(n) = S(n, r).
r=0
It is called the nth Bell number. By definition, Bell(0) = 1 = Bell(1). Determine Bell(n), for
Σn
2 ≤ n ≤ 5. Prove combinatorially that Bell(n + 1) = C(n, k)Bell(k).
k=0
5. Suppose 13 people get on the lift at level 0. If all the people get down at some level, say 1, 2, 3, 4
and 5 then, calculate the number of ways of getting down if at least one person gets down at each
level.
6. How many functions are there from [10] to [4] such that each i ∈ [4] has at least two pre-images?
Σ
7. Let n ≥ k be natural numbers. Show that S(n, k) = 1a1−12a2−1 · · · kak −1, where the summation
is over all solutions of a1 + · · · + ak = n in N, by showing that the RHS has the same initial
values and satisfies the same recurrence relation.

5.7 Number partitions

Let n, k ∈ N. A partition of n into k parts is a tuple (x1, · · · , xk) ∈ Nk written in decreasing order
such that x1 + · · · + xk = n. By πn(k), we denote the number of partitions of n into exactly k parts
and by πn we denote the number of all partitions of n. Conventionally we take π0 = 1. By definition
πn(k) = 0, whenever k > n.
Example 5.7.1. 1. Notice that (1, 1, 1, 1), (2, 2), (2, 1, 1) are some partitions of 4.
2. Notice that π7(4) = 3 as the partitions of 7 into 4-parts are (4, 1, 1, 1), (3, 2, 1, 1) and (2, 2, 2, 1).
Verify that π7(2) = 3 and π7(3) = 4.

Discussion 5.7.2. We give here two instances where number partitions occur naturally.

1. Determine the number of ways of carrying n copies of the same book in r identical bags with
the restriction that no bag goes empty.
Ans: As the books are indistinguishable, we need to count the number of books in each bag.
As the bags are indistinguishable, arrange them so that the number of books inside the bags are
in decreasing order. Also, each bag is nonempty and hence the answer is πn(r).

2. Determine the number of ways of carrying n copies of the same book in r identical bags with
with no restriction.
Ans: As the books are indistinguishable, we need to count the number of books in each bag. As
the bags are indistinguishable, arrange them so that the number of books inside the bags are in
decreasing order. Also, as empty bags are allowed the resulting sequence (of numbers of books
in the bags in increasing order) may have some 0’s. Truncating the 0’s we obtain a partition of
n with at most r parts, that is, πn(1) + · · · + πn(r).

At times ‘a partition of n into k parts’ is written in short as ‘a k-partition of n’.

Proposition 5.7.3. Let n, r ∈ N. Then the number of partitions of n into at most r parts is equal to
the number of partitions of n + r into r parts.

Proof. Given a partition of n into at most r parts, extend it to an r-tuple by adding some 0’s at the
right end. For example, if n = 7, r = 4, we change the partition (6, 1) which has at most four parts
into (6, 1, 0, 0) which is a four tuple. This can be done uniquely. Next, add 1 to each component of
5.7. NUMBER PARTITIONS 96

the r-tuple. We get an r-partition of n + r. For example, our previous four tuple would now change
to (7, 2, 1, 1) which is a partition of 11 into four parts.
Conversely, given an r-partition of n+r, subtract 1 from each component. Some of the components
might become 0. Truncating them we get a partition of n into at most r parts.

Remark 5.7.4. [Recurrence for πn(k)] Another way of writing the previous result is

πn(k) = πn−k(0) + πn−k(1) + · · · + πn−k(k)

and so
π n(k) = πn−1(k − 1) + π n−k(k).

We can also prove the second one directly using the fact that a k-partition can have the last part 1 or
more than 1 and then derive the first one.

PRACTICE 5.7.5. Calculate π(n) for n = 1, 2, 3, . . . , 8.

PRACTICE 5.7.6. Prove that π2r (r) = πr for any r ∈ N.

Definition 5.7.7. Let n, k ∈ N and λ = (n1, n2, · · · , nk) be a k-partition of n.

1. Then, the Ferrer’s Diagram of λ is a pictorial representation of the partition created in the
following way. The i-th part of the partition is represented by putting ni equally spaced dots in
a row. The first row is on the top. The leftmost dots of each row lies in the same column.
2. The (i, j)-hook of the partition consists of the (i, j)-dot along with the dots (of i-th row) to the
right of it and the dots (of j-th column) below it. The hook length is the number of dots in
that particular hook.

Example 5.7.8. Ferrer’s diagram for the partitions λ1 = (5, 3, 3, 2, 1, 1), λ2 = (6, 4, 3, 1, 1) and
λ3 = (5, 5, 4, 3, 2) of 15, 15 and 19 are given below.

••••• •••••• •••••

••• •••• •••••
••• ••• ••••
•• • •••
• • ••
•
(5, 3, 3, 2, 1, 1) (6, 4, 3, 1, 1) (5, 5, 4, 3, 2)

Figure 5.2: Ferrer’s diagram of λ1, λ2, λ3

Suppose that we have a Ferrer’s diagram of some partition λ of n. Observe that the number of
dots in the first column of the Ferrer’s diagram is greater than or equal to the number of dots in the
second column. In general, the number of dots in the i-th column is always greater than or equal
to the number of dots in the (i + 1)-th column. Thus, if we interchange the rows and columns of
the Ferrer’s diagram (transposing), then the result is another Ferrer’s diagram of some partition of n.
This new partition is called the conjugate of λ and is denoted by λJ . A partition λ of n is called self
conjugate if λ = λJ .
For instance, if λ = (5, 3, 3, 2, 1, 1) is a partition of 15, then its conjugate is λJ = (6, 4, 3, 1, 1). The
partition (5, 4, 3, 2, 1) is a self-conjugate partition of 15.
5.7. NUMBER PARTITIONS 97

Remark 5.7.9. Let λ = (n1 , . . . , nk ) be a partition (of some number). One can write the conjugate
without drawing the Ferrer’s diagram. It’s conjugate λJ = (p1 , . . . , pn1 ) has n1 components and p i =
the number of components in λ that are at least i. For example, the conjugate of (5, 3, 1, 1) is a
partition with 5 components (p1 , . . . , p5 ), where p1 = the number of components in λ that are at least
1. So p1 = 4. Now, p2 = the number of components in λ that are at least 2. So p2 = 2. Similarly,
p3 = 2, p4 = 1, and p5 = 1. So λJ = (4, 2, 2, 1, 1).

Proposition 5.7.10. Let n ∈ N. Then the number of self conjugate partitions of n is the same as the
number of partitions of n whose parts are distinct odd numbers.

Proof. Let λ be a self conjugate partition of n with k diagonal dots. For 1 ≤ i ≤ k, define li = length
of the (i, i)-th hook. Since λ is self-conjugate, each li is odd and (l1, . . . , lk) is a strictly decreasing
sequence of positive integers with l1 + l2 + . . . + lk = n. Hence, from a self conjugate partition λ of n
we have got a partition of n whose parts are distinct and odd.
Conversely, given any partition, say l = (l1, . . . , lk) where parts are distinct and odd, we can get
a self conjugate partition by putting l1 dots in the (1, 1)-th hook, l2 dots in the (2, 2)-th hook and so
on. Since each li is odd, the hook is symmetric and as the hook lengths decrease at least by 2, we see
that the corresponding diagram of dots is indeed a Ferrer’s diagram. (Try to give a formula for the
resulting partition in terms of li’s.) Hence the result follows.

Proposition 5.7.11. Let n ∈ N and f (n) be the number of partitions of n in which no part is 1.
Then f (n) = πn − πn−1.

Proof. For n = 1, both the sides of the equality are 0. So assume that n > 1.
We shall count the complement. Let λ = (n1, . . . , nk) be a partition of n with nk = 1. (Since
n > 1, there are at least two parts.) Then, λ gives rise to a partition of n − 1, namely (n1, . . . , nk−1 ).
Conversely, if µ = (t1, . . . , tk) is a partition of n − 1, then (t1, . . . , tk, 1) is a partition of n with last
part 1. Hence, the number of partitions of n with last part 1 is πn−1(k − 1).
Thus, using Remark 5.7.4, the number of partitions of n in which no part is 1 is πn − πn−1.

EXERCISE 5.7.12. 1. Let n ∈ N. Find an expression for the number of k-partitions of n in which
each part is at least 3.
2. Let n, k, m ∈ N. Prove the following.
(a) The number of k-partitions of n with the first (largest) part m = the number of m-partitions
of n with the first part k.
(b) The number of k-partitions of n with the first part at most m = the number of partitions
of n into at most m parts with the first part k.
(c) The number of partitions of n into at most k parts with the first part at most m = the
number of partitions of n into at most m parts with the first part at most k.

3. For n, r ∈ N, prove that πn(r) is the number of partitions of n + C(r, 2) into r unequal parts.
4. Recall that a composition of n is an ordered tuple of positive integers whose sum is n. They are
also called ordered partitions. Express the following quantities in terms of Fibonacci numbers
(F1 = F2 = 1).
(a) The number of ordered partitions of n into parts > 1.
(b) The number of ordered partitions of n into parts equal to 1 or 2.
5.7. NUMBER PARTITIONS 98

(c) The number of ordered partitions of n into odd parts.

5. Let f (n, r) be the number of partitions of n where each part repeats less than r times. Let g(n, r)
be the number of partitions of n where no part is divisible by r. Show that f (n, r) = g(n, r).

5.8 Lattice paths and Catalan numbers

Let A = (a1, a2) and B = (b1, b2), a1 ≤ b1, a2 ≤ b2, be two points on Z × Z. By a lattice path
from A to B we mean a sequence of points (A = P1, . . . , Pk = B) of S such that if Pi = (x, y) then
Pi+1 is either (x + 1, y) or (x, y + 1), for 1 ≤ i ≤ k − 1. Thus, at each step we move either one unit
right, denoted R, or one unit up, denoted U . For example, from (2, 3) if we take the sequence of steps
UURRURRRUR, then we reach (8, 7). This lattice path is shown in the Figure 5.3.

(8, 7)

(0, 0)

Figure 5.3: A lattice with a lattice path from (2, 3) to (8, 7)

Discussion 5.8.1. How many lattice paths are there from (0, 0) to (m, n)?
Ans: As at each step, either the step has to be R or it has to be U . We have to take m many
steps of type R in total in order to reach a point with x-coordinate m. Similarly, we have to take n
many steps of type U in total in order to reach a point with y-coordinate n. So, any arrangement of
m many R’s and n many U ’s will give such a path uniquely. Hence, the answer is C(m + n, m).
Σ
m
Discussion 5.8.2. Use lattice paths to give a combinatorial proof of C(n+A, A) = C(n+m+1, m).
A=0
Ans: Observe that C(n + m + 1, m) is the number of lattice paths from (0, 0) to (m, n + 1). A
lattice path from (0, 0) to (m, n + 1) must touch a point F of the form (i, n + 1), i = 0, 1, . . . , m for
the first time. For i ƒ= j, we see that the lattice paths for which F = (i, n + 1) are disjoint from the
the lattice path for which F = (j, n + 1).
Hence, the total number of lattice paths is the sum of the number of lattice paths from (0, 0) to
(i, n + 1). The number of lattice paths for which F = (i, n + 1), is nothing but the number of lattice
paths from (0, 0) to (i, n), which is C(n + i, i). Our proof is complete.

Discussion 5.8.3. As observed earlier, the number of lattice paths from (0, 0 to (n, n) is C(2n, n).
Suppose, we wish to take paths so that at no step the number of U ’s exceeds the number of R’s. Then,
what is the number of such paths?
Ans: Call an arrangement of n many U ’s and n many R’s a ‘bad path’ if the number of U ’s exceeds
the number of R’s at least once. For example, the path RRUUURRU is a ‘bad path’. To each such
arrangement, we correspond another arrangement of n+1 many U ’s and n−1 many R’s in the following
5.8. LATTICE PATHS AND CATALAN NUMBERS 99

way: spot the first place where the number of U ’s exceeds that of R’s in the ‘bad path’. Then, from the
next letter onwards change R to U and U to R. For example, the bad path RRUUURRU corresponds
to the path RRUUUUUR. Notice that this is a one-one correspondence. Thus, the number of bad
C(2n, n)
paths is C(2n, n − 1). So, the answer to the question is C(2n, n) − C(2n, n − 1) = .
n+1
Discussion 5.8.4. A rectangular grid with m units on x-axis and n units on y-axis is called an
(m, n)-lattice. By a standard (m, n)-lattice, we mean the rectangular grid with opposite corners at
(0, 0) and (m, n).
Consider the standard (n, n)-lattice. Recall that a lattice path from (0, 0) to (n, n) can be viewed
an arrangement of n many R’s and n many U ’s. An arrangement in which at some position the
number of U ’s is more than that of the R’s corresponds to a lattice path which enters the region y > x
in that grid.
From the previous discussion, it follows that the number of lattice paths from (0, 0) to (n, n) that
do not enter the region above the line y = x is C(2n, n)/(n + 1).

Definition 5.8.5. The n-th Catalan number, denoted Cn, is the number of different representations
of the product A1 · · · An+1 of n + 1 square matrices of the same size using n pairs of brackets. By
convention C0 = 1.

Example 5.8.6. The different representations of the product A1 · · · A4 by using 3 pairs of brackets
are (((A1A2)A3)A4), ((A1A2)(A3A4)), ((A1(A2A3))A4), (A1((A2A3)A4)), (A1(A2(A3A4))). Hence
C3 = 5.

Theorem 5.8.7. [Catalan number] Let n ∈ N. Then Cn = C(2n,n)

n+1.

Proof. Consider a meaningful representation X of the product of n + 1 matrices with n pairs of

brackets. First we erase, the subscripts, with the understanding that the i-th A from left is Ai.
Claim: After the (n − k)-th ‘(’, there are at least k + 2 many A’s.
Proof of the claim. It is true for n = 1, that is when there are only two matrices. Assume it is
true for n = 2, 3, . . . , p − 1 Consider a meaningful representation X of the product of p + 1 matrices
with p pairs of brackets.
Observe that the last ( is followed by AA), as the product is meaningful.
Now, treat this (AA) as a single matrix, A. Then our original meaningful representation of the
product of p + 1 matrices changes into a meaningful representation X ∗ of p matrices with p − 1 pairs of
brackets.
Hence, by induction, in X∗, after the p−k = ((p−1)−(k−1))-th ‘(’, there are at least k+1 = k−1+2
many matrices. This means, in X, after the (p − k)-th ‘(’, there are at least k + 2 matrices. So the
claim is justified.
Drop the right brackets and one A from the right end, to have a sequence of n many ‘(’s and n
many A’s, where the number of A’s used till the (n − k)-th ‘(’ is at most n − (k + 1) = n − k − 1. So,
the number of A’s never exceeds the number of ‘(’.
Conversely, given such an arrangement, we can put back the ‘)’s: first add one more A at the right
end; find two consecutive letters from the last ‘(’; put a right bracket after them; treat (AA) as a
letter; repeat the process. For example,

((A((AAA → ((A((AAAA → ((A((AA)AA → ((A((AA)A)A → ((A((AA)A))A = ((A((AA)A))A)

By previous discussions, the number of such arrangements is C(2n,n)

n+1 .
5.8. LATTICE PATHS AND CATALAN NUMBERS 100

Σ
n Σ
n−1
Theorem 5.8.8. [Recurrence relation for Cn] Let n ∈ N. Then Cn = Ci−1Cn−i = CiCn−1−i.
i=1 i=0

Proof. As Cn is number of ways to multiply n + 1 pairs of A’s with n pairs of brackets, removing the
outer pair of brackets, we get two expressions written, one is a meaningful multiplication of k many
A’s with k − 1 pairs of brackets and the other is a meaningful multiplication of n + 1 − k many A’s
with n − k pairs of brackets, where k can vary from 1, . . . , n. These two expressions for a k = i differ
from the two expressions for a k ƒ= i. Hence,
n n−1
Σ Σ
Cn = Ci−1Cn−i = CiCn−1−i.
i=1 i=0

Example 5.8.9. A full binary tree is a rooted binary tree in which every node either has exactly two
offsprings or has no offspring, see Figure 5.4. Show that Cn is equal to the number of full binary trees
on 2n + 1 vertices.

♥ ♥ ♥ ♥
♥ ♥ ♥ ♥ ♥ ♥ ♥ ♥
♥ ♥ ♥ ♥ ♥ ♥ ♥ ♥

Figure 5.4: Full binary trees on 7 vertices (or 4 leaves)

Let f (n) be the number of full binary trees on 2n + 1 vertices. The idea is to show that f (n)
satisfies the same recurrence relation as that of Cn and has the same initial values. We see that
f (0) = 1 = C0.
Now take any full binary trees on 2n + 1 vertices and delete the root. We two trees, one on the
left, say Tl and one on the right, say Tr. Notice that Tl and Tr are full binary trees and their sizes
are 2k + 1 and 2n − 2k − 1, respectively, where k can be 0, 1, . . . , n − 1. And these cases are mutually
disjoint, that is, a full binary tree with Tl having k vertices is different from that of one with Tl having
−1
nΣ
different number of vertices. Hence, f(n) = f (k)f (n − k − 1). So f (n) = Cn .
k=0

Remark 5.8.10. The book titled “enumerative combinatorics” by Stanley [13] gives a comprehensive
list of places in combinatorics where Catalan numbers appear. The interested reader may have a look
at those.
Σ
n
EXERCISE 5.8.11. 1. Take C0 = 1. Use the recurrence relation Cn = Ci−1Cn−i to show that
i=1
Cn = C(2n, n)/(n + 1).
2. Give a bijection between ‘the solution set of x0 + x1 + x2 + · · · + xk = n in non-negative integers’
and ‘the number of lattice paths from (0, 0) to (n, k)’.
Σn
3. Use lattice paths to give a combinatorial proof of C(n, k) = 2n.
k=0

4. Use lattice paths to give a combinatorial proof of Σ C(n, k) 2 = C(2n, n). [Hint: C(n, k) is the
n

k=0
number of lattice paths from (0, 0) to (n − k, k) as well as from (n − k, k) to (n, n). ]
5.8. LATTICE PATHS AND CATALAN NUMBERS 101

5. As Cn = C(2n, n)/(n + 1) is the number of ways of expressing a product of n + 1 many A’s

using n pairs of brackets meaningfully, it is an integer and so n + 1 divides C(2n, n). Give an
arithmetic proof of this fact.
6. A man is standing on the edge of a swimming pool (facing it) holding a bag containing n blue
and n red balls. He randomly picks up one ball at a time and discards it. If the ball is blue he
takes a step back and if the ball is red, he takes a step forward. What is the probability of his
falling into the swimming pool?
7. Let n ≥ 4 and consider a regular polygon with vertices 1, 2, · · · , n. In how many ways can we
divide the polygon into triangles using (n − 3) non-crossing diagonals?
8. How many lattice paths are there from (0, 0) to (9, 9) which does not cross the dotted line, that
is they stay in lower part of the lattice?

(9, 9)

(0, 0)

9. How many arrangements of n blue and n red balls are there such that at any position in the
arrangement the number of blue balls (till that position) is at most one more than the number of
red balls (till that position)?
10. We want to write a matrix of size 10 × 2 using numbers 1, . . . , 20 with each number appearing
exactly once. Then, determine the number of such matrices in which the numbers
(a) increase from left to right?
(b) increase from up to down?
(c) increase from left to right and up to down?

11. Show that Cn also equals the number of integer sequences that satisfy 1 ≤ a1 ≤ a2 ≤ · · · ≤ an
and ai ≤ i, for all i, 1 ≤ i ≤ n.

EXERCISE 5.8.12. [Additional exercises] :

1. Prove that there exists a bijection between any two of the following sets.

(a) The set of words of length n on an alphabet consisting of m letters.

(b) The set of maps of an n-set into an m-set.
(c) The set of distributions of n distinct objects into m distinct boxes.
(d) The set of n-tuples on m letters.

2. Prove that there exists a bijection between any two of the following sets.
5.8. LATTICE PATHS AND CATALAN NUMBERS 102

(a) The set of n letter words with distinct letters out of an alphabet consisting
of m letters.
(b) The set of one-one functions from an n-set into an m-set.
(c) The set of distributions of n distinct objects into m distinct boxes, subject
to ‘if an object is put in a box, no other object can be put in the same
box’.
(d) The set of n-tuples on m letters, without repetition.
(e) The set of permutations of m symbols taken n at a time.

3. Prove that there exists a bijection between any two of the following sets.

(a) The set of increasing words of length n on m ordered letters.

(b) The set of distributions on n non-distinct objects into m distinct boxes.
(c) The set of combinations of m symbols taken n at a time with repetitions
permitted.

Need to put somewhere

1. For n ≥ 1, let an = (n − 1)n(n + 1). Write a generating function for an and hence
Σ
n
evaluate
− (k 1)k(k + 1).
k=1
2. Let an = −3an−1 + 10an+2 + 3 × 2n, for n ≥ 2 with a0 = 0 and a1 = 6. Use
generating function to evaluate an.