Conbinatorial Analysis by Chen PDF
Conbinatorial Analysis by Chen PDF
Conbinatorial Analysis by Chen PDF
Combinatorics has its roots in mathematical recreations and games; it dates back to
ancient Chinese He Luo Tu. Many problems that were studied in the past, either
for amusement or for aesthetic appeal, are of great importance today in pure and
applied science. Now combinatorics is an important branch of mathematics, and its
influence continues to expand. Part of the reason for the tremendous growth of com-
binatorics since the sixties has been the major impact that computers have had and
continue to have in our society. Another reason for the recent growth of combinatorics
is its applicability to disciplines that had previously had little serious contact with
mathematics. It is often found that the ideas and techniques of combinatorics are
being used not only in the traditional areas of mathematical application, namely, the
physical sciences, but also in the social sciences, the biological sciences, information
theory, and so on.
This course is intended for undergraduates who have taken Math132 or elementary
course of linear algebra. For students who did not take the above courses or similar
ones, they are assumed to have reached certain level of mathematical maturity.
Advanced books
R. Stanley, Enumerative combinatorics, Cambridge University Press,
1991.
Jr. M. Hall, Combinatorial theory, John Wiley & Sons, 1986.
M. Aigner, Combinatorial theory, Springer, 1979.
Grading policy: Homework counts 25%; there are 3 exams (quizzes), each counts 25%.
Week 1: What is combinatorics?
1 What is combinatorics?
The question that “what is combinatorics” is similar to the question that “what is mathematics”. If we
say that mathematics is about the study of numbers and figures, then combinatorics is about the counting
(enumeration) of objects (figures).
Examples of combinatorial problems:
(1) Finding the number of games that n teams would play if each team played with every other team
exactly once.
(2) Constructing a magic square.
(3) Attempting to trace through a network without removing your pencil from the paper and without
tracing any part of the network more than once.
(4) Counting the number of poker hands which are full houses.
Historically, combinatorics has its roots in mathematical recreations and games. Many problems that
were studied in the past, either for amusement or for aesthetic appeal, are today of great importance in
pure and applied sciences. Now combinatorics is an important branch of mathematics, and its influence
continues to expand. Part of the reason for the tremendous growth of combinatorics since the sixties has
been the major impact that computers have had and continue to have in our society. Another reason for
the recent growth of combinatorics is its applicability to disciplines that had previously had little serious
contact with mathematics. It is often found that the ideas and techniques of combinatorics are being used
not only in the traditional areas of mathematical application, namely, the physical sciences, but also in the
social sciences, the biological sciences, information theory, and so on.
Combinatorics is concerned with arrangements of the objects of a set into patterns satisfying specified
rules.
Combinatorial problems can be classified into following categories:
Existence of the arrangement.
Enumeration of the arrangements.
Classification of the arrangements.
Study of a known arrangement.
Construction of an optimal arrangement.
In other words, combinatorics is concerned with the existence, enumeration, analysis, and optimization of
discrete structures.
There are very few general methods in combinatorics that can apply to solve large number of combi-
natorial problems. The typical general methods in combinatorics: Induction; inclusion-exclusion principle,
pigeonhole principle; bijective counting; methods of recurrence relations and generating function; Burnside’s
theorem and Pólya counting; and Möbius inversion formula.
1
2 Examples
2.1 Perfect Cover of Chessboards
It is obvious that the chessboard can be covered by 32 dominoes so that no two dominoes overlap. Such
a cover is called a perfect cover. However, the chessboard with two diagonal corners removed cannot be
perfectly covered by 31 dominoes since
31BW 6= 32B + 30W.
The following board cannot be perfectly covered by dominoes.
A b-omino is a (1, b)- or (b, 1)-board, where b ≥ 2. A perfect cover of an m-by-n board by b-ominoes is
an arrangement of b-ominoes on the board so that no two b-ominoes overlap. When does an m × n-board
have a perfect cover by b-ominoes? The answer is given by the following theorem.
Theorem 2.1. An m-by-n-board have a perfect cover by b-ominoes if and only if b divides either m or n.
Proof. “⇐:” The condition is obviously sufficient.
“⇒:” Let m and n be divided by b to have remainders r and s respectively; i.e.,
m = pb + r, 0≤r<b
n = qb + s, 0 ≤ s < b.
Without loss of generality we may assume r ≤ s. We claim that r = 0. Let the m × n-board be cyclicly
colored (or labeled) by b colors as follows:
1 2 3 ··· b − 1 b
b 1 2 ··· b − 2 b − 1
b−1 b 1 ··· b − 3 b − 2
.. .... .. ..
. . . . .
3 4 5 ··· 1 2
2 3 4 ··· b 1
2
For example, for m = 10, n = 15, and b = 4, the 10-by-15 board can be colored as
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
3 4 1 2 3 4 1 2 3 4 1 2 3 4 1
2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
3 4 1 2 3 4 1 2 3 4 1 2 3 4 1
2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3
4 1 2 3 4 1 2 3 4 1 2 3 4 1 2
Note that each b-omino of a perfect covering covers exactly one square of each of the b colors, no matter
how the b-omino is placed. It follows that there are must be the same number of squares of each color of
the board. Let the m-by-n board be divided into three parts as follows:
pb
qb s
Obviously, the upper part is perfectly covered by b-ominoes; the lower left part is also perfectly covered by
b-ominoes. It follows that the number of squares of each color in the r-by-s board is the same as the number
of squares having the color 1. Since the number of squares of the color 1 in the r-by-s board is r, there are
rb squares in the r-by-s board. Thus have rs = rb. If r > 0, then s = b, a contradiction. Hence, r = 0.
This means that b|m.
We only prove the theorem for 4-by-4 board. Suppose the 4 × 4-board has a perfect cover which has no
fault-line. Let a, b, c, x, y, z be the number of dominoes cut by the three vertical lines and the three horizontal
3
x
y
z
a b c
lines, respectively. Since there is no fault line, the numbers a, b, c, x, y, z are positive. By try-and-error, we
see that a, b, c, x, y, z ≥ 2. It is clear that no domino can be cut by more than two lines. Then there are at
least
a + b + c + x + y + z ≥ 2 · 6 = 12
dominoes in the perfect cover. However, the number of dominoes must be 8. This is a contradiction.
are the magic squares of order 3 and 4 with magic sums 15 and 34, respectively.
Necessary condition:
n2 (n2 + 1)
1 + 2 + · · · + n2 = .
2
n(n2 + 1)
s= .
2
de la Loubère Method: This is only for constructing magic square of odd order n. The integer 1 is placed
in the middle square of the top row. The successive integers are then placed in their natural order along a
diagonal line which slopes upwards and to the right, with the following modifications:
1. When the top row is reached, the next integer is put in the bottom row as if it came immediately
above the top row.
2. When the rightmost column is reached, the next integer is put in the leftmost column as if it imme-
diately succeeded the rightmost column.
3. When a square is reached which has already been filled or when the top rightmost square is reached,
the next integer is placed in the square immediately below the last square which was filled.
4
For instance, the magic squares of order 5 and 7 are constructed as follows:
30 39 48 1 10 19 28
17 24 1 8 15
38 47 7 9 18 27 29
23 5 7 14 16 46 6 8 17 26 35 37
4 6 13 20 22 , 5 14 16 25 34 36 45
10 12 19 21 3 13 15 24 33 42 44 4
11 18 25 2 9 21 23 32 41 43 3 12
22 31 40 49 2 11 20
The number s is called the magic sum of the magic cube and has the value
n3 (n3 + 1) 1 n(n3 + 1)
s= · 2 = .
2 n 2
There is no magic cube of order 3.
3
Suppose there is a magic cube of order 3. Its magic sum should be 3(3 2+1) = 42.
For a magic cube of order 3, 1 ≤ i, j, k ≤ 3, consider any 3 × 3 plane cross section
a b c
u v w
x y z
Then
a+b+c = 42 (1)
x+y+z = 42 (2)
a+v+z = 42 (3)
b+v+y = 42 (4)
c+v+x = 42 (5)
Do operation (3) + (4) + (5) − (1) − (2), we have 3v = 42 and v = 14. This means that 14 has to be the
center for any plane cross section of the magic cube. However, there are more than one such plane centers,
and 14 can only occupy one place. This is a contradiction.
It is much more difficult to show that there is no magic cube of order 4. A magic cube of order 8 is given
in an article by Gardner, “Mathematical games,” Scientific American, January (1976), 118–123.
5
2.4 The Four-Color Problem
2.5 The Problem of 36 Officers
Given 36 officers of 6 ranks and from 6 regiments, no two have both the same rank and from the same
regiments, can they be arranged in a 6 × 6 formation so that in each row and column there is one officer of
each rank and one officer from each regiment? This problem can be stated as follows:
Can the 36 ordered pairs (i, j) (i = 1, 2, . . . , 6; j = 1, 2, . . . , 6) be arranged in a 6 × 6 array so that in
each row and each column, the numbers in the first position form a permutation of {1, 2, . . . , 6} and the
numbers in the second position form a permutation of {1, 2, . . . , 6}?
Such an array can be split into two 6 × 6 arrays, one corresponding to the first positions of the ordered
pairs (the rank array) and the other to the second positions (the regiment array). Thus the problem can be
stated:
Do there exist two 6 × 6 arrays whose entries are taken from the integers 1, 2, . . . , 6 such that (1) in each
row and in each column of these arrays the integers 1, 2, . . . , 6 occur in some order, and (2) when the two
arrays are juxtaposed all of the 36 ordered pairs (i, j) (1 ≤ i, j ≤ 6) occur?
To make the problem concrete and easy, suppose instead that there are 9 officers of 3 ranks and from 3
different regiments. Then a solution for the problem in this case is
1 2 3 1 2 3 (1, 1) (2, 2) (3, 3)
3 1 2 , 2 3 1 −→ (3, 2) (1, 3) (2, 1)
2 3 1 3 1 2 (2, 3) (3, 1) (1, 2)
A Latin square of rank n is an array of integers such that each row and each column of the array the integers
1, 2, . . . , n occur in some order. The rank and regiment arrays above are Latin squares of order 3. The
following are Latin squares of order 2 and 4:
· ¸ 1 2 3 4
1 2 4 1 2 3
and 3 4 1 2 .
2 1
2 3 4 1
Two Latin squares of order n are called orthogonal if, when they are juxtaposed, all ordered pairs (i, j)
(1 ≤ i ≤ n and 1 ≤ j ≤ n) occur.
Euler investigated the existence of orthogonal Latin squares of order n. It is easy to see that there is no
pair of Latin squares of order 2.
Euler showed that how to construct a pair of orthogonal Latin squares of order n when n is odd or
divisible by 4. Notice that this does not include n = 6. On the basis of many trials he concluded, but did
not prove, that there is no pair of orthogonal Latin squares of order 6, and he conjectured that there is no
such pair existed for any of integers 4k + 2 with k ≥ 1.
By exhaustive enumeration Terry in 1901 proved that Euler’s conjecture is true for n = 6. Around 1960
Bose, Parker, and Shrikhande succeeded in proving that Euler’s conjecture was false for all n > 6, i.e., for
4k + 2 with k ≥ 2.
6
2.6 Shortest Path Problem
2.7 The Game of Nim
Nim is a game played by two players with heaps of coins. Suppose there are k ≥ 1 heaps of coins which
contain, respectively, n1 , . . . , nk coins. The object of the game is to select the last coin. The rule of the
game are as follows:
1. The players alternate turns (let us call the player who makes the first move I and then call the other
player II)
2. Each player, when it is their turn, selects one of the heaps and removes one or more coins from the
selected heap. (The player may take all of the coins from the selected heap, thereby leaving an empty
heap, which is now “out of play.”)
The game ends when all the heaps are empty. The last player to make a move, that is, the player who takes
the last coin(s), is the winner.
When k = 1, obviously, player I wins the game.
When k = 2, if n1 6= n2 , say, n1 > n2 , player I may remove n1 − n2 coins from the fist heap to make
the two heaps having the same amount of coins; such a move is called balancing. No matter how player
II moves, the player I may adopt the winning strategy to remove the same amount of coins that player II
moves. This guarantees that player I wins the game. If n1 = n2 , the game is already balanced, no matter
how player I moves at beginning, player II can take the winning strategy to win the game.
For instance,
I II I II I II I II I
(9, 7) → (7, 7) → (4, 7) → (4, 4) → (3, 4) → (3, 3) → (3, 2) → (2, 2) → (0, 2) → (0, 0).
When there are k heaps of coins, say (n1 , n2 , . . . , nk ), we write the numbers n1 , n2 , . . . , nk as base 2
numerals:
n1 = as as−1 · · · a2 a1 a0 ,
n2 = bs bs−1 · · · b2 b1 b0 ,
..
.
nk = cs cs−1 · · · c2 c1 c0 .
Dividing each heap into s + 1 sub-heaps (some of them may be zero), the the game becomes a game having
total k(s + 1) sub-heaps as the following:
(as , . . . , a1 , a0 ; bs , . . . , b1 , b0 ; . . . ; cs , . . . , c1 , c0 ).
as + b s + · · · + c s , ..., a 1 + b1 + · · · + c 1 , a 0 + b0 + · · · + c 0
7
Theorem 2.3. If the game of Nim is unbalanced, then the player I can always take certain number of coins
from one of the heaps to balance the game. More specifically, if s is the largest digit whose sum as +bs +· · ·+cs
is odd, then one of the summand is 1, say as = 1; the player I can move
s
X
d= εi 2i
i=0
Proof. In the case of unbalanced, say s is the largest digit such that as + bs + · · · + c1 is odd and as = 1, we
have
n01 := n1 − d = a0s a0s−1 . . . a02 a01 a00 , where a0i = ai − εi .
If ai + bi + · · · + ci is even, then a0i + bi + · · · + ci = ai + bi + · · · + ci is even. If ai + bi + · · · + ci is odd, then
a0i + bi + · · · + ci = (ai − εi ) + bi + · · · + ci = ai + bi + · · · + ci ∓ 1
Size of heaps 23 = 8 22 = 4 21 = 2 20 = 1
6 0 1 1 0
4 0 1 0 0
13 1 1 0 1
15 1 1 1 1
The game can be also balanced by removing 10 coins from the heap 3 or removing 14 coins from the heap 4.
3 Gambler’s Ruin
Two persons A and B gamble dollars on the toss of a fair coin; A has $70 and B has $30. In each play either
A wins $1 from B or loss $1 to B; and the game is played without stop until one wins all the money of the
other or goes forever. Find the odds of the following possibilities:
8
(b) A loses all his money to B.
The characteristic equation is r2 − 2r + 1 = 0; it has only one root r = 1. The general solutions is
pn = c1 + c2 n.
1
Apply the boundary conditions p0 = 0 and p100 = 1; we have c1 = 0 and c2 = 100
. Thus
n
pn = , 0 ≤ n ≤ 100.
100
n
Of course, pn = 100 for n > 100 is nonsense to the original problem. The probabilities for (a), (b), and (c)
are 70%, 30%, and 0, respectively.
The recurrence relation pn = 12 pn+1 + 12 pn−1 can be directly solved. In fact, the recurrence relation can
be written as
pn+1 − pn = pn − pn−1 .
Then pn+1 − pn = pn − pn−1 = · · · = p1 − p0 is constant. Since p0 = 0, we have pn = pn−1 + p1 . Apply the
recurrence relation again and again, we obtain
pn = p0 + np1 .
1 n
Apply the boundary conditions p0 = 0, p100 = 1; we see that p1 = 100
. Hence pn = 100
.
4 Hanoi Tower
The game of Hanoi Tower is to play with a set of disks of graduated size with holes in their centers and a
playing board having three spokes for holding the disks; see Figure 4. The object of the game is to transfer
all the disks from spoke A to spoke C by moving one disk at a time without placing a larger disk on top of
a smaller one. What is the minimal number of moves required when there are n disks?
1111111111111111
0000000000000000
0000000000000000 1111111111111111
1111111111111111 0000000000000000
0000000000000000 1111111111111111
1111111111111111 0000000000000000
0000000000000000
1111111111111111
A B C
9
Solution. Let an be the minimum number of moves to transfer n disks from one spoke to another. Then
{an | n ≥ 1} defines an infinite sequence. The first few terms of the sequence {an } can be listed as
1, 3, 7, 15, . . .
Given a recurrence relation for a sequence with initial conditions, solving the recurrence relation means
to find a formula to express the general term an of the sequence.
For the sequence {an | n ≥ 0} defined by the recurrence relation (6), if we apply the recurrence relation
again and again, we have
a1 = 2a0 + 1
a2 = 2a1 + 1 = 2(2a0 + 1) + 1 = 22 a0 + 2 + 1
a3 = 2a2 + 1 = 2(22 a0 + 2 + 1) = 23 a0 + 22 + 2 + 1
a4 = 2a3 + 1 = 2(23 a0 + 22 + 2 + 1) = 24 a0 + 23 + 22 + 2 + 1
..
.
an = 2n a0 + 2n−1 + 2n−2 + · · · + 2 + 1 = 2n a0 + 2n − 1.
an = 2n − 1, n ≥ 1.
5 Marriage Problem
10
Week 2: The Pigeonhole Principle
Proof. Trivial.
Example 1.1. Among 13 people there are two who have their birthdays in the same month.
Example 1.2. There are n married couples. How many of the 2n people must be selected in order to guarantee
that a married couple is selected?
• If n objects are put into n boxes and no box is empty, then each box contains exactly one object.
• If n objects are put into n boxes and no box gets more than one object, then each box has an object.
The abstract formulation of the three principles: Let X and Y be finite sets and let f : X −→ Y be a function.
• If X and Y have the same number of elements and f is onto, then f is one-to-one.
• If X and Y have the same number of elements and f is one-to-one, then f is onto.
Example 1.3. In any group of n people there are at least two persons having the same number friends. (It is
assumed that if a person x is a friend of y then y is also a friend of x.)
Proof. The number of friends of a person x is an integer k with 0 ≤ k ≤ n − 1. If there is a person y whose number
of friends is n − 1, then everyone is a friend of y, that is, no one has 0 friend. This means that 0 and n − 1 can not
be simultaneously the numbers of friends of some people in the group. The pigeonhole principle tells us that there
are at least two people having the same number of friends.
Example 1.4. Given n integers a1 , a2 , . . . , an , not necessarily distinct, there exist integers k and l with 0 ≤ k < l ≤ n
such that the sum ak+1 + ak+2 + · · · + al is a multiple of n.
a1 , a1 + a2 , a1 + a2 + a3 , ..., a1 + a2 + · · · + an .
a1 + a2 + · · · + ai = qi n + ri , 0 ≤ ri ≤ n − 1, i = 1, 2, . . . , n.
1
Example 1.5. A chess master who has 11 weeks to prepare for a tournament decides to play at least one game
every day but, in order not to tire himself, he decides not to play more than 12 games during any calendar week.
Show that there exists a succession of consecutive days during which the chess master will have played exactly 21
games.
Proof. Let a1 be the number of games played on the first day, a2 the total number of games played on the first and
second days, a3 the total number games played on the first, second, and third days, and so on. Since at least one
game is played each day, the sequence of numbers a1 , a2 , . . . , a77 is strictly increasing, that is, a1 < a2 < · · · < a77 .
Moreover, a1 ≥ 1; and since at most 12 games are played during any one week, a77 ≤ 12 × 11 = 132. Thus
Note that the sequence a1 + 21, a2 + 21, . . . , a77 + 21 is also strictly increasing, and
each of them is between 1 and 153. It follows that two of them must be equal. Since a1 , a2 , . . . , a77 are distinct and
a1 + 21, a2 + 21, . . . , a77 + 21 are also distinct, then the two equal numbers must be of the forms ai and aj + 21.
Since the number of games played up to the ith day is ai = aj + 21, we conclude that on the days j + 1, j + 2, . . .,
i the chess master played a total of 21 games.
Example 1.6. Given 101 integers from 1, 2, . . . , 200, there are at least two integers such that one of them is divisible
by the other.
Proof. By factoring out as many 2’s as possible, we see that any integer can be written in the form 2k · a, where
k ≥ 0 and a is odd. The number a can be one of the 100 numbers 1, 3, 5, . . . , 199. Thus among the 101 integers
chosen, two of them must have the same a’s when they are written in the form, say, 2r · a and 2s · a with r 6= s. if
r < s, then the first one divides the second. If r > s, then the second one divides the first.
Example 1.7 (Chines Remainder Theorem). Let m and n be relatively prime positive integers. Then the system
½
x ≡ a (mod m)
x ≡ b (mod n)
has a solution.
Proof. We may assume that 0 ≤ a < m and 0 ≤ b < n. Let us consider the n integers
a, m + a, 2m + a, ..., (n − 1)m + a.
Each of these integers has remainder a when divided by m. Suppose that two of them had the same remainder r
when divided by n. Let the two numbers be im + a and jm + a, where 0 ≤ i < j ≤ n − 1. Then there are integers
qi and qj such that
im + a = qi n + r and jm + a = qj n + r.
Subtracting the first equation from the second, we have
Since gcd(m, n) = 1, we conclude that n|(j − i). Note that 0 < j − i ≤ n − 1. This is a contradiction. Thus
the n integers a, m + a, 2m + a, . . . , (n − 1)m + a have distinct remainders when divided by n. That is, each of
the n numbers 0, 1, 2, . . . , n − 1 occur as a remainder. In particular, the number b does. Let p be the integer with
0 ≤ p ≤ n − 1 such that the number x = pm + a has remainder b when divided by n. Then for some integer q,
x = qn + b. So
x = pm + a = qn + b,
and x has the required property.
2
2 Pigeonhole Principle: Strong Form
Theorem 2.1. Let q1 , q2 , . . . , qn be positive integers. If
q1 + q2 + · · · + qn − n + 1
objects are put into n boxes, then either the 1st box contains at least q1 objects, or the 2nd box contains at least q2
objects, . . ., the nth box contains at least qn objects.
Proof. Suppose it is not true, that is, the ith box contains at most qi − 1 objects, i = 1, 2, . . . , n. Then the total
number of objects contained in the n boxes can be at most
which is one less than the number of objects distributed. This is a contradiction.
The simple form of the pigeonhole principle is obtained from the strong form by taking q1 = q2 = · · · = qn = 2.
Then
q1 + q2 + · · · + qn − n + 1 = 2n − n + 1 = n + 1.
In elementary mathematics the strong form of the pigeonhole principle is most often applied in the special case
when q1 = q2 = · · · = qn = r. In this case the principle becomes:
• If n(r − 1) + 1 objects are put into n boxes, then at least one of the boxes contains r or more of the objects.
Equivalently,
Example 2.1. A basket of fruit is being arranged out of apples, bananas, and oranges. What is the smallest number
of pieces of fruit that should be put in the basket in order to guarantee that either there are at least 8 apples or at
least 6 bananas or at least 9 oranges?
Answer: 8 + 6 + 9 − 3 + 1 = 21.
Example 2.2. Given two disks, one smaller than the other. Each disk is divided into 200 congruent sectors. In the
larger disk 100 sectors are chosen arbitrarily and painted red; the other 100 sectors are painted blue. In the smaller
disk each sector is painted either red or blue with no stipulation on the number of red and blue sectors. The smaller
disk is placed on the larger disk so that the centers and sectors coincide. Show that it is possible to align the two
disks so that the number of sectors of the smaller disk whose color matches the corresponding sector of the larger
disk is at least 100.
Proof. We fix the larger disk first, then place the smaller disk on the top of the larger disk so that the centers and
sectors coincide. There 200 ways to place the smaller disk in such a manner. For each such alignment, some sectors
of the two disks may have the same color. Since each sector of the smaller disk will match the same color sector of
the larger disk 100 times among all the 200 ways and there are 200 sectors in the smaller disk, the total number of
matched color sectors among the 200 ways is 100 × 200 = 20, 000. Note that there are only 200 ways. Then there
is at least one way that the number of matched color sectors is 20,000
200 = 100 or more.
Example 2.3. Show that every sequence a1 , a2 , . . . , an2 +1 of n2 + 1 real numbers contains either an increasing
subsequence of length n + 1 or a decreasing subsequence of length n + 1.
3
Proof. Suppose there is no increasing subsequence of length n + 1. We suffices to show that there must be a
decreasing subsequence of length n + 1.
Let `k be the length of the longest increasing subsequence which begins with ak , 1 ≤ k ≤ n2 + 1. Since it is
assumed that there is no increasing subsequence of length n + 1, we have 1 ≤ `k ≤ n for all k. By the strong form
of the pigeonhole principle, n + 1 of the n2 + 1 integers `1 , `2 , . . . , `n2 +1 must be equal, say,
where 1 ≤ k1 < k2 < · · · < kn+1 ≤ n2 + 1. If there is one ki (1 ≤ i ≤ n) such that aki < aki+1 , then any increasing
subsequence of length `ki+1 beginning with aki+1 will result a subsequence of length `ki+1 + 1 beginning with aki by
adding aki in the front; so `ki > `ki+1 , which is contradictory to `ki = `ki+1 . Thus we must have
3 Ramsey Theory
Theorem 3.1 (Ramsey Theorem). Let S be a finite set with n elements. Let Pt (S) be the collection of all t-subsets
of S with t ≥ 1, i.e.,
Pt (S) = {A ⊆ S : |A| = t}.
Then for any integers p, q ≥ t there exists a smallest integer rt (p, q) such that, if n ≥ rt (p, q) and Pt (S) is 2-colored
with two color classes C and D, then there is either a p-subset X of S such that Pt (X) is contained in C, or a
q-subset Y of S such that Pt (Y ) is contained in D.
Proof. We proceed by induction on p, q, and t. For t = 1 and arbitrary p, q, we have r1 (p, q) = p + q − 1. Note that
every element of P1S(S) is a singleton set and |P1 (S)| = |S|. For the n-set S with n ≥ p + q − 1, if |C| ≥ p, we take
any p-subset
S X of A∈C A, then obviously P1 (X) is contained in C. If |C| < p, then |D| ≥ q; we take any q-subset
Y of A∈D A and obviously have P1 (Y ) is contained in D. Thus r1 (p, q) ≤ p + q − 1. For n = p + q − 2, let C be
the set of p − 1 singleton sets and D the set of the other q − 1 singleton sets. Then it is impossible to have either a
p-subset X ⊆ S such that P1 (X) ⊆ C or a q-subset Y such that P1 (Y ) ⊆ D. Thus r1 (p, q) ≥ p + q − 1.
Moreover, for any integer t ≥ 1 it can be easily verified that
rt (t, q) = q, rt (p, t) = p.
In fact, for p = t, let S be a q-set. For a 2-coloring {C, D} of Pt (S), if C = ∅, then D = Pt (S) and obviously Pt (Y )
is contained in D when Y = S. If C 6= ∅, take any element X ∈ C; obviously, X is a p-subset of S (for p = t) and
Pt (X) = {X} which is contained in C. Thus rt (t, q) ≤ q. Let |S| ≤ q − 1. For the particular 2-coloring {C, D} with
C = ∅ and D = Pt (S), it is clear that there is neither a t-subset (i.e. p-subset for p = t) X of S such that Pt (X) is
contained in C nor a q-subset Y of S such that Pt (Y ) is contained in D. This means that rt (t, q) ≥ q. It is analogous
that rt (p, t) = p.
Now for integers p, q, t such that p, q ≥ t and t ≥ 2, we show that rt (p, q) exists under the existence of rt (p − 1, q),
rt (p, q − 1), and the existence of rt−1 (a, b) for arbitrary integers a, b ≥ t − 1. This is achieved by establishing the
following recurrence relation:
Let integer n ≥ rt−1 (p1 , q1 ) + 1 and |S| = n. Take an element x ∈ S and let S1 = S\{x}. Then |S1 | = n − 1 and
|S1 | ≥ rt−1 (p1 , q1 ). Let {C, D} be a 2-coloring of Pt (S) and let
C1 = {A ∈ C : x 6∈ A}, D1 = {A ∈ D : x 6∈ A}.
C1 (x) = {A ∈ Pt−1 (S1 ) : A ∪ {x} ∈ C}, D1 (x) = {A ∈ Pt−1 (S1 ) : A ∪ {x} ∈ D}.
4
It is clear that C1 (x) and D1 (x) are disjoint. For any element A ∈ Pt−1 (S1 ), it is obvious that either A ∪ {x} ∈ C
or A ∪ {x} ∈ D; then either A ∈ C1 (x) or A ∈ D1 (x). So {C1 (x), D1 (x)} is a 2-coloring of Pt−1 (S1 ). Since
|S1 | ≥ rt−1 (p1 , q1 ) and by the induction hypothesis on t, we have either (i) there exists a p1 -subset X1 ⊆ S1 such
that Pt−1 (X1 ) ⊆ C1 (x), or (ii) there exists a q1 -subset Y1 ⊆ S1 such that Pt−1 (Y1 ) ⊆ D1 (x).
Case (i): |X1 | = p1 = rt (p − 1, q). Since {C, D} is a 2-coloring of Pt (S), then {C|X1 , D|X1 } is a 2-coloring of
Pt (X1 ), where
C|X1 = {A ∈ C : A ⊆ X1 }, D|X1 = {A ∈ D : A ⊆ X1 }.
By induction hypothesis on p (when t is fixed) there exists either a (p − 1)-subset X 0 ⊆ X1 such that Pt (X 0 ) ⊆ C|X1
(⊆ C) or a q-subset Y 0 ⊆ X1 such that Pt (Y 0 ) ⊆ D|X1 (⊆ D). In the former case, consider the p-subset X :=
X 0 ∪ {x} ⊆ S. For any t-subset A ⊆ X, if x 6∈ A, obviously A ⊆ X 0 , so A ∈ C; if x ∈ A, obviously A\{x} is a
(t − 1)-subset of X 0 (⊆ X1 ), then A\{x} ∈ C1 (x), thus A = (A\{x}) ∪ {x} ∈ C. This means that X is a p-subset of
S and Pt (X) ⊆ C. In the latter case, we already have a q-subset Y := Y 0 ⊆ S such that Pt (Y ) ⊆ D.
Case (ii): |Y1 | = q1 = rt (p, q − 1). Since {C1 , D1 } is a 2-coloring of Pt (S1 ), then {C1 |Y1 , D1 |Y1 } is a 2-coloring of
Pt (Y1 ), where
C1 |Y1 = {A ∈ C1 : A ⊆ Y1 }, D1 |Y1 = {A ∈ D1 : A ⊆ Y1 }.
By induction hypothesis on q (when t is fixed) there exists either a p-subset X 0 ⊆ Y1 such that Pt (X 0 ) ⊆ C1 (⊆ C) or
a (q − 1)-subset Y 0 ⊆ Y1 such that Pt (Y 0 ) ⊆ D1 (⊆ D). In the former case, we already have a p-subset X := X 0 ⊆ S
such that Pt (X) ⊆ C. In the latter case, we have a q-subset Y := Y 0 ∪ {x} ⊆ S and Pt (Y ) ⊆ D.
Now we have obtained a recurrence relation:
Theorem 3.2. Let S be an n-set. Let q1 , q2 , . . . , qk , t be positive integers such that q1 , q2 , . . . , qk ≥ t. Then there
exists a smallest integer rt (q1 , q2 , . . . , qk ) such that, if n ≥ rt (q1 , q2 , . . . , qk ) and for any k-coloring {C1 , C2 , . . . , Ck }
of Pt (S) there is at least one i (1 ≤ i ≤ k) and a qi -subset Si ⊆ S such that Pt (Si ) ⊆ Ci .
Proof. We proceed induction on k. For k = 1, then Pr (S) is a 1-coloring of Pt (S) itself; the theorem is obviously
true. For k = 2, it is Theorem 3.1. For k ≥ 3, let Di = Ci for 1 ≤ i ≤ k − 2 and Dk−1 = Ck−1 ∪ Ck . By the induction
hypothesis there exists the integer qk−1 0 0
= rt (qk−1 , qk ) and subsequently the integer rt (q1 , . . . , qk−2 , qk−1 ).
0
Now for |S| = n ≥ rt (q1 , . . . , qk−2 , qk−1 ), since {D1 , . . . , Dk−1 } is a (k − 1)-coloring of Pt (S), there exists either
at least one qi -subset Si ⊆ S such that Pt (Si ) ⊆ Di = Ci with 1 ≤ i ≤ k − 2 or a qk−1 0 -subset Sk−1 0 ⊆ S
0
such that Pt (Sk−1 ) ⊆ Dk−1 . In the former case, nothing is to be proved. In the latter case, let Dk−1 = {A ∈ 0
0
Pt (Sk−1 ) : A ∈ Ck−1 } and Dk0 = {A ∈ Pt (Sk−1 0 ) : A ∈ Ck }, then {Dk−1 0 , Dk0 } is a 2-coloring of Pt (Sk−10 ). Since
0 0 0
|Sk−1 | = qk−1 = rt (qk−1 , qk ), there exists either a qk−1 -subset Sk−1 ⊆ Sk−1 such that Pt (Sk−1 ) ⊆ Dk−1 or a qk - 0
subset Sk ⊆ S such that Pt (Sk ) ⊆ Dk0 . Note that Dk−1 0 ⊆ Ck−1 and Dk0 ⊆ Ck . Then there exists either a qk−1 -subset
Sk−1 ⊆ S such that Pt (Sk−1 ) ⊆ Ck−1 or a qk -subset Sk ⊆ S such that Pt (Sk ) ⊆ Ck .
Summarizing the above argument we obtain the recurrence relation:
0
rt (q1 , q2 , . . . , qk ) ≤ rt (q1 , q2 , . . . , qk−2 , qk−1 ).
For positive integers q1 , q2 , . . . , qk , t such that q1 , q2 , . . . , qk ≥ t, rt (q1 , q2 , . . . , qk ) are called Ramsey numbers. For
any permutation (σ1 , σ2 , . . . , σk ) of (1, 2, . . . , k), we have
r1 (q1 , q2 , . . . , qk ) = q1 + q2 + · · · + qk − k + 1.
5
4 Applications of the Ramsey Theorem
Theorem 4.1. For positive integers q1 , . . . , qk there exists a smallest positive integer r(q1 , . . . , qk ) such that, if
n ≥ r(q1 , . . . , qk ) and for any edge coloring of the complete graph Kn with k colors c1 , . . . , ck , there is at least one i
(1 ≤ i ≤ k) such that Kn contains a complete subgraph Kqi of the color ci .
Theorem 4.2 (Erdös-Szekeres). For any integer k ≥ 3 there exists a smallest integer N (k) such that, if n ≥ N (k)
and for any n points on a plane having no three points through a line, then there is a convex k-gon whose vertices
are among the given n points.
Before proving the theorem we prove the following two lemmas first.
Lemma 4.3. Among any 5 points on a plane, no three points through a line, 4 of them must form a convex
quadrangle.
Proof. Join every pair of two points by a segment to have a configuration of 10 segments. The circumference of the
configuration forms a convex polygon. If the convex polygon is a pentagon or a quadrangle, the problem is solved.
Otherwise the polygon must be a triangle, and the other two points must be located inside the triangle. Draw a
straight line through the two points; two of the three vertices must be located in one side of the straight line. The
two vertices on the same side and the two points inside the triangle form a quadrangle.
Lemma 4.4. Given k ≥ 4 points on a plane, no 3 points through a line. If any 4 points are vertices of a convex
quadrangle, then the k points are actually the vertices of a convex k-gon.
Proof. Join every pair of two points by a segment to have a configuration of k(k − 1)/2 segments. The circumference
of the configuration forms a convex l-polygon. If l = k, the problem is solved. If l < k, there must be at least one
point inside the l-polygon. Let v1 , v2 , . . . , vl be the vertices of the convex l-polygon, and draw segments between
v1 and v3 , v4 , . . . , vl−1 respectively. The point inside the convex l-polygon must be located in one of the triangles
4v1 v2 v3 , 4v1 v3 v4 , . . . , 4v1 vl−1 vl . Obviously, the three vertices of the triangle with a given point inside together
with the point do not form a convex quadrangle. This is a contradiction.
Proof of Theorem 4.2. We apply the Ramsey theorem to prove Theorem 4.2. For k = 3, it is obviously true. Now for
k ≥ 4, if n ≥ R(k, 5; 4), we divide the 4-subsets of the n points into a class C of 4-subsets whose points are vertices
of a convex quadrangle, and another class D of 4-subsets whose points are not vertices of any convex quadrangle.
By the Ramsey theorem, there is either k points whose any 4-subset belongs to C, or 5 points whose any 4-subset
belongs to D. In the formal case, the problem is solved by Lemma 4.4. In the latter case, it is impossible by
Lemma 4.3. ¤
Theorem 4.5 (Schur). For any positive integer k there exists a smallest integer Nk such that,P if n ≥ Nk and for
any k-coloring of [1, n], there is a monochromatic sequence x1 , x2 , . . . , xl (l ≥ 2) such that xl = l−1
i=1 xi .
Proof. Let n ≥ R(l, . . . , l; 2) and let {A1 , . . . , Ak } be a k-coloring of [1, n]. Let {C1 , . . . , Ck } be a k-coloring of
P2 ([1, n]) defined by
{a, b} ∈ Ci if and only if |a − b| ∈ Ai , where 1 ≤ i ≤ k.
By the Ramsey theorem, there is one r (1 ≤ r ≤ k) and an l-subset A = {a1 , a2 , . . . , al } ⊂ [1, n] such that
P2 (A) ⊆ Cr . We may assume a1 < a2 < · · · < al . Then
6
5 Van der Waerden Theorem
The Van der Waerden theorem states that for any k-coloring of the set Z of integers there always exists a monochro-
matic progression series.
Let [a, b] denote the set of integers x such that a ≤ x ≤ b. Two tuples (x1 , . . . , xm ) and (y1 , . . . , ym ) of [1, l]m
are said l-equivalent, written (x1 , . . . , xm ) ∼ (y1 , . . . , ym ), if all entries before the last l in each tuple are the same.
For instance, for l = 5, m = 4,
(3, 5, 2, 5) ∼ (3, 5, 2, 5), (2, 4, 5, 2) ∼ (2, 4, 5, 4), (4, 3, 1, 4) ∼ (2, 3, 2, 1), (3, 5, 5, 1) 6∼ (3, 5, 2, 4).
Obviously, l-equivalence is an equivalence relation on [0, l]m . All tuples of [0, l − 1]m are l-equivalent.
Definition 5.1. For integers l, m ≥ 1, let A(l, m) denote the statement: For any integer k ≥ 1 there exists a smallest
integer N (l, m, P
k) such that, if n ≥ N (l, m, k) and [1, n] is k-colored, then there are integers a, d1 , d2 , . . . , dm ≥ 1
such that a + l m i=1 di ≤ n and for each l-equivalence class E of [0, l] ,
m
( m
)
X
a+ xi di : (x1 , . . . , xm ) ∈ E
i=1
When m = 1, there are only two l-equivalence classes for [0, l]m , i.e.,
The statement A(l, 1) means that for any integer k ≥ 1 there exists a smallest integer N (l, 1, k) such that, if
n ≥ N (l, 1, k) and [1, n] is k-colored, then there are integers a, d ≥ 1 such that a + ld ≤ n and the sequence,
a, a + d, a + 2d, . . . , a + (l − 1)d, is monochromatic.
Theorem 5.2 (Graham-Rothschild). The statement A(l, m) is true for all integers l, m ≥ 1.
Proof. We proceed induction on l and m. For l = m = 1, the 1-equivalence classes of [0, 1] are {0} and {1};
the statement A(1, 1) states that for any integer k ≥ 1 there exists a smallest integer N (1, 1; k) such that, if
n ≥ N (1, 1; k) and [1, n] is k-colored, then there are integers a, d ≥ 1 such that a + d ≤ n, and both {a} and
{a + d} are monochromatic. This is obviously true and N (1, 1; k) = 2. We divide the induction argument into two
statements:
The induction goes as follows: The truth of A(1, 1) implies the truth of A(1, m) for all m ≥ 1 by (I). Then by (II)
the statement A(2, 1) is true. Again by (I) the statement A(2, m) is true for all m ≥ 1. Continuing this procedure
we obtain that A(l, m) is true for all l, m ≥ 1.
Proof of (I): Let the integer k ≥ 1 be fixed. Since A(l, m) is true, the integer N (l, m, k) exists and set p =
N (l, m, k). Since A(l, 1) is true, the integer N (l, 1, k p ) exists and we set q = N (l, 1, k p ), N = pq. Let φ : [1, N ] −→
[1, k] be a k-coloring of [1, N ]. Let ψ : [1, q] −→ [1, k]p be a k p -coloring of [1, q] defined by
³ ´
ψ(i) = φ((i − 1)p + 1), φ((i − 1)p + 2), . . . , φ((i − 1)p + p) , 1 ≤ i ≤ q. (1)
Since A(l, 1) is true, then for the k p -coloring ψ of [1, q] there are integers a, d ≥ 1 such that
a + ld ≤ q
and
{a + xd : x = 0, 1, 2, . . . , l − 1}
7
is monochromatic, i.e.,
ψ(a + xd) = constant, x = 0, 1, 2, . . . , l − 1. (2)
Note that [(a − 1)p + 1, ap] ⊆ [1, pq] because a ≤ q. Since A(l, m) is true, then when φ is restricted to the p-set
[(a − 1)p + 1, ap] there are integers b, d1 , d2 , . . . , dm ≥ 1 such that
m
X
(a − 1)p + 1 ≤ b, b+l di ≤ ap,
i=1
is monochromatic, i.e., Ã !
m
X
φ b+ xi di = constant, (x1 , . . . , xm ) ∈ E. (3)
i=1
Recall that our job is to prove that A(l, m + 1) is true. For the k-coloring φ of [1, N ], we have had the integers
Now for any two l-equivalent tuples (x1 , . . . , xm+1 ) and (y1 , . . . , ym+1 ) of [0, l]m+1 , consider the numbers
Pm+1 Pm+1
α=b+ i=1 xi di , β = b + i=1 yi d i ,
Pm Pm
α0 = b + i=1 xi di , β0 = b + i=1 yi di .
Notice that our job is to show that α and β have the same color, i.e., φ(α) = φ(β). We divide the job into three
cases:
Case 1. xm+1 = ym+1 = l. Then xi = yi for all 1 ≤ i ≤ m. Thus α = β, and obviously, φ(α) = φ(β).
Case 2. xm+1 = l and ym+1 ≤ l − 1, or, xm+1 ≤ l − 1 and ym+1 = l. This implies that (x1 , . . . , xm+1 ) and
(y1 , . . . , ym+1 ) are not l-equivalent. This is a contradiction.
Case 3. xm+1 , ym+1 ∈ [0, l − 1]. Then (x1 , . . . , xm ) and (y1 , . . . , ym ) are l-equivalent. It follows from (2) that
ψ(a) = ψ(a + xm+1 d), and by definition (1) of ψ, the corresponding coordinates of ψ(a) and ψ(a + xm+1 d) are equal,
i.e., ³ ´ ³ ´
φ (a − 1)p + i = φ (a + xm+1 d − 1)p + i , i = 1, 2, . . . , p.
P
Since (a − 1)p + 1 ≤ b ≤ α0 ≤ b + l m i=1 di ≤ ap = (a − 1)p + p, there exists j ∈ [1, p] such that α0 = (a − 1)p + j.
We then have
α = α0 + xm+1 dp = (a − 1)p + j + xm+1 dp = (a + xm+1 d − 1)p + j.
Thus ³ ´ ³ ´
φ(α) = φ (a + xm+1 d − 1)p + j = φ (a − 1)p + j = φ(α0 ).
Similarly, φ(β) = φ(β0 ). Since (x1 , . . . , xm ) and (y1 , . . . , ym ) are l-equivalent, it follows from (3) that φ(α0 ) = φ(β0 ).
Therefore φ(α) = φ(β). This means that A(l, m + 1) is true and
³ ´
N (l, m + 1, k) ≤ N (l, m, k) · N l, 1, k N (l,m,k) .
8
Proof of (II): Fix an integer k ≥ 1. Since A(l, m) is true for all m ≥ 1, the statement A(l, k) is true and N (l, k, k)
exists. Let N = 2N (l, k, k) and let φ be a k-coloring of [1, N ]. Notice that the restriction of φ on [1, N (l, k, k)] is a
k-coloring. Then there are integers a, d1 , d2 , . . . , dk ≥ 1 such that
k
X
a+l di ≤ N (l, k, k),
i=1
At least two of them, say a + l(d1 + · · · + dλ ) and a + l(d1 + · · · + dµ ) with λ < µ, must have the same color, i.e.,
à λ
! Ã µ
!
X X
φ a+l di =φ a+l di . (4)
i=1 i=1
P P
of [0, l]k are l-equivalent. Thus the numbers a + l λi=1 di + x µi=λ+1 di for x ∈ [0, l − 1] have the same color by φ,
i.e., Ã !
Xλ Xµ
φ a+l di + x di = constant, x = 0, 1, 2, . . . , l − 1.
i=1 i=λ+1
Pλ Pµ
Recall that our job is to prove the truth of A(l + 1, 1). Let b = a + l i=1 di and d = i=λ+1 di . Then we have had
the integers b, d ≥ 1 such that
λ
X µ
X µ
X µ
X
b + (l + 1)d = a + l di + (l + 1) di = a + l di + di ≤ N (l, k, k) + N (l, k, k) = N
i=1 i=λ+1 i=1 i=λ+1
and for the k-coloring φ of [1, N ], the l-equivalence class {0, 1, 2, . . . , l} of [0, l + 1]1 have the same color, i.e.,
The truth of A(l, m) for m = 1 is called the Van der Waerden theorem.
9
Corollary 5.3 (Van der Waerden Theorem). For any positive integers k and l there exists a smallest integer N (l, k)
such that, if n ≥ N (l, k) and [1, n] is k-colored, then there is a monochromatic arithmetic sequence of length l in
[1, n].
Supplementary Exercises
1. For the game of Nim, let us restrict that each player can move one or two coins. Find the winning strategy
for each player.
2. Let n be a positive integer. In the game of Nim let us restrict that each player can move only i ∈ {1, 2, . . . , n}
coins each time from one heap. Find the winning strategy for each player.
3. Given m(m − 1)2 + 1 integral points on a plane, where m is odd. Show that there exists m points whose center
is also an integral point.
10
Homework 1
1. Consider an m-by-n chessboard with m and n both odd. To fix the notation, suppose that the square in the
upper left-hand corner is colored white. Show that if a white square is cut out anywhere on the board, the
resulting pruned board has a perfect cover by dominoes.
2. (a) Let f (n) count the number of different perfect covers of a 2-by-n chessboard by dominoes. Evaluate f (1),
f (2), f (3), f (4), and f (5). Try to find (and verify) a simple relation that the counting function f satisfies.
use this relation to compute f (12).
*(b) Let g(n) be the number of different perfect covers of a 3-by-n chessboard by dominoes. Evaluate
g(1), g(2), . . . , g(6).
3. Let a and b be positive integers with a a factor of b. Show that an m-by-n board has a perfect cover by a-by-b
pieces if and only if (i) a is a factor of both m and n, and (ii) b is a factor of either m or n. (Hint: Partition
the a-by-b pieces into a 1-by-b pieces.)
5. Is 4-pile Nim game with heaps of sizes 22, 19, 14, and 11 balanced or unbalanced? Player I’s first move is to
remove 6 coins from the heap of size 19. What should Play II’s first move be?
6. Show that in an unbalanced game of Nim in which the largest unbalanced bit is the jth bit, Player I can
always balance the game by removing coins from any heap that the base 2 numeral of whose number has a 1
in the jth bit.
7. A game is played between two players, alternating turns as follows: The game starts with an empty pile.
When it is his turn a play may add either 1, 2, 3, or 4 to the pile. The prson who adds the 100th coin to the
pile is the winner. Determine whether it is the first or second player who can guarantee a win in this game.
What is the winning strategy to follow?
1. Show that n + 1 integers are chosen from the set {1, 2, . . . , 2n}, then there are always two which differ by at
most 2.
2. In a room there are 10 people, none of whom are older than 60 (ages are given in whole numbers only) but
each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common
person) the sum of whose ages is the same. Can 10 be replaced by a smaller number?
3. A bag contains 100 apples, 100 bananas, 100 oranges, and 100 pears. If I pick one piece of fruit out f the bag
every minute, how long will it be before I am assured of having picked at least a dozen pieces of fruit of the
same kind?
4. Prove that, for any n + 1 integers a1 , a2 , . . . , an+1 , there exist two of the integers ai and aj with i 6= j such
that ai − aj is divisible by n.
5. There are 100 people at a party. Each person has an even number (possibly zero) of acquaintances. Prove
that there are three people at the party with the same number of acquaintances.
1
Supplementary Exercises
1. Let r, s, and b be positive integers such that r ≤ s < b. Then in any b-cyclic coloring of an r-by-s board, there
are at least two colors, say c1 and c2 , such that the number of squares of color c1 is not equal to the number
of squares of color c2 .
2. For the game of Nim, let us restrict that each player can move one or two coins. Find the winning strategy
for each player.
3. Let n be a positive integer. In the game of Nim let us restrict that each player can move only i ∈ {1, 2, . . . , n}
coins each time from one heap. Find the winning strategy for each player. (Hint: Use modulo integers and
write them as base 2 numerals.)
4. Given m(m − 1)2 + 1 integral points on a plane, where m is odd. Show that there exists m points whose center
is also an integral point.
1 Partial Solutions
No. 4 (p.20) f (n) = f (n − 1) + f (n − 2).
.
No. 8 (p.22)
Since a|b, we write b = ak. It is clear that if the m × n-board can be covered by a × b-ominoes then it must be
covered by a × a-squares. Thus it is necessary that a|m and a|n. We divide the m × n-board into m n
a × a -board so
2
that each big square consists of a small squares. Now the original covering problem becomes the problem to tile
the m n m n
a × a -board by k-ominoes. It is known that the necessary and sufficient condition is that k| a or k| a . Thus an
m × n-board can be tiled by a × b-ominoes if and only if
Example 2.1. The game of Nim can be further generalized to that each player can move any amount of coins from
the set {1, 2, . . . , n}, where n ≥ 1.
2
The case of one heap:
− (x) : x ≡ 0(mod n + 1)
+ (x) : x 6≡ 0(mod n + 1)
The case of two heaps:
− (x, y) : x ≡ y(mod n + 1)
+ (x, y) : x 6≡ y(mod n + 1)
The case of k heaps: (x1 , . . . , xk )
Let xi = qi (n + 1) + ri , where 0 ≤ ri ≤ n and 1 ≤ i ≤ k. Write r1 , r2 , . . . , rk as base 2 numerals:
r1 = as as−1 · · · a2 a1 a0 ,
r2 = bs bs−1 · · · b2 b1 b0 ,
..
.
rk = cs cs−1 · · · c2 c1 c0 .
Dividing each heap into s subheaps, the the game becomes a game having total ks subheaps:
(as , . . . , a1 , a0 ; bs , . . . , b1 , b0 ; . . . ; cs , . . . , c1 , c0 ).
as + bs + · · · + cs , ..., a1 + b1 + · · · + c1 , a0 + b0 + · · · + c0
Size of heaps 22 = 4 21 = 2 20 = 1
10 ≡ 3(mod 7) 0 1 1
8 ≡ 1(mod 7) 0 0 1
14 ≡ 0(mod 7) 0 0 0
16 ≡ 2(mod 7) 0 1 0
3
Week 3-4: Permutations and Combinations
Example 1.1. Determine the number of positive integers which are factors of the number 53 × 79 × 13 × 338 .
The number 33 can be factored into 3 × 11. By the unique factorization theorem of positive integers, each factor
of the given number is of the form 3i × 5j × 7k × 11l × 13m , where 0 ≤ i ≤ 8, 0 ≤ j ≤ 3, 0 ≤ k ≤ 9, 0 ≤ l ≤ 8, and
0 ≤ m ≤ 1. Thus the number of factors is
9 × 4 × 10 × 9 × 2 = 7280.
Example 1.2. How many two-digit numbers have distinct and nonzero digits?
A two-digit number ab can be regarded as an ordered pair (a, b) where a is the tens digit and b is the units digit.
The digits in the problem are required to satisfy
a 6= 0, b 6= 0, a 6= b.
The digit a has 9 choices, and for each fixed a the digit b has 8 choices. So the answer is 9 × 8 = 72.
The answer can be obtained in another way: There are 90 two-digit numbers, i.e., 10, 11, 12, . . . , 99. However,
the 9 numbers 10, 20, . . . , 90 should be excluded; another 9 numbers 11, 22, . . . , 99 should be also excluded. So the
answer is 90 − 9 − 9 = 72.
Example 1.3. How many odd numbers between 1000 and 9999 have distinct digits?
A number a1 a2 a3 a4 between 1000 and 9999 can be viewed as an ordered tuple (a1 , a2 , a3 , a4 ). Since a1 a2 a3 a4 ≥
1000 and a1 a2 a3 a4 is odd, then a1 = 1, 2, . . . , 9 and a4 = 1, 3, 5, 7, 9. Since a1 , a2 , a3 , a4 are distinct, we conclude:
a4 has 5 choices; when a4 is fixed, a1 has 8(= 9 − 1) choices; when a1 and a4 are fixed, a2 has 8(= 10 − 2) choices;
and when a1 , a2 , a4 are fixed, a3 has 7(= 10 − 3) choices. Thus the answer is 8 × 8 × 7 × 5 = 2240.
Example 1.4. In how many ways to make a basket of fruit from 6 oranges, 7 apples, and 8 bananas so that the
basket contains at least two apples and one banana?
Let a1 , a2 , a3 be the number of oranges, apples, and bananas in the basket respectively. Then 0 ≤ a1 ≤ 6,
2 ≤ a2 ≤ 7, and 1 ≤ a3 ≤ 8, i.e., a1 has 7 choices, a2 has 6 choices, and a3 has 8 choices. Thus the answer is
7 × 6 × 8 = 336.
1
(a) without repetition,
(b) with repetition allowed.
A multiset M is a collection whose members need not be distinct. For instance, the collection
M = {a, a, b, b, c, d, d, d, 1, 2, 2, 2, 3, 3, 3, 3}
A multiset M over a set S can be viewed as a function v : S −→ N from S to the set N of nonnegative integers;
each element x ∈ S is repeated v(x) times in M ; we write M = (S, v).
Example 1.5. How many integers between 0 and 10,000 have exactly one digit equal to 5?
First Method: Let S be the set of all such numbers, and let Si be the set of such numbers having exactly i digits,
1 ≤ i ≤ 4. Clearly, S1 | = 1. For S2 , if the tens is 5, then the units has 9 choices; if the units is 5, then the tens has
8 choices; thus |S2 | = 9 + 8 = 17.
For S3 , if the tends is 5, then the units has 9 choices and the hundreds has 8 choices; if the hundreds is 5, then
both tens and the units have 9 choices; if the units is 5, then the tens has 9 choices and hundreds has 8 choices;
thus |S3 | = 9 × 9 + 8 × 9 + 8 × 9 = 225.
For S4 , if the thousands is 5, then each of the other three digits has 9 choices; if the hundreds or tens or units is 5,
then the thousands has 8 choices, each of the other two digits has 9 choices; thus |S4 | = 9×9×9+3×8×9×9 = 2, 673.
Therefore
|S| = |S1 | + |S2 | + |S3 | + |S4 | = 1 + 17 + 225 + 2, 673 = 2, 916.
Second Method: Let us write any integer with less than 5 digits in a formal 5-digit form by adding zeros in the front.
For instance, we write 35 as 00035, 836 as 00836. Let Si be the set of integers of S whose ith digit is 5, 1 ≤ i ≤ 4.
Then |Si | = 9 × 9 × 9 = 729. Thus |S| = 4 × 729 = 2, 916.
Example 1.6. How many distinct 5-digit numerals can be constructed out of the digits 1, 1, 1, 6, 8?
The digit 6 can be located in any of the 5 positions; then 8 can be located in in 4 positions. Thus the answer is
5 × 4 = 20.
2 Permutation of Sets
Definition 2.1. An r-permutation of n objects is a linearly ordered selection of r objects from a set of n objects.
The number of r-permutations of n objects is denoted by
P (n, r).
2
Example 2.1. Find the number of ways to put the numbers 1, 2, . . . , 8 into the squares of 6-by-6 grid so that each
square contains at most one number.
There are 36 squares in the 6-by-6 grid. We label the squares by the numbers 1, 2, ..., 36 as follows:
1 2 3 4 5 6 5
7 8 9 10 11 12 3 7
13 14 15 16 17 18 4
19 20 21 22 23 24 6 2
25 26 27 28 29 30 8
31 32 33 34 35 36 1
The filling pattern on the right can be viewed as the 8-permutation (35, 22, 7, 16, 3, 21, 11, 26) of {1, 2, . . . , 36}. Thus
the answer is
36! 36!
P (36, 8) = = .
(36 − 8)! 28!
Example 2.2. What is the number of ways to arrange the 26 alphabets so that no two of the vowels a, e, i, o, and
u occur next to each other?
We first have the 21 consonants arranged arbitrarily and there are 21! ways to do so. For each such 21-
permutation, we arrange the 5 vowels a, e, i, o, u in 22 positions between consonants; there are P (22, 5) ways of such
arrangement. Thus the answer is
22!
21! × P (22, 5) = 21! × .
17!
Example 2.3. Find the number of 7-digit numbers in base 10 such that all digits are nonzero, distinct, and the
digits 8 and 9 do not appear next to each other.
First method: The numbers in question can be viewed as 7-permutations of {1, 2, . . . , 9} with certain restrictions.
Such permutations can be divided into three types: (i) permutations without 8 and 9; (ii) permutations with either
8 or 9 but not both; and (iii) permutations with both 8 and 9, but not next to each other.
(i) There are P (7, 7) = 7! = 5, 040 such permutations.
7!
(ii) There are P (7, 6) 6-permutations of {1, 2, . . . , 7}. Thus there are 2 × 7 × P (7, 6) = 2 × 7 × 1! = 70, 560 such
permutations.
(iii) For each 5-permutation of {1, 2, . . . , 7}, there are 6 ways to insert 8 in it, and then there are 5 ways to insert
9. Thus there are 6 × 5 × P (7, 5) = 75, 600.
Therefore the answer is
5, 040 + 70, 560 + 75, 600 = 151, 200.
Second method: Let S be the set of 7-permutations of {1, 2, . . . , 9}. Let A be the subset of 7-permutations of S in
the problem. Then Ā is the set of 7-permutations of S such that 89 or 98 appears somewhere. We may think of 89
and 98 as a single object in whole, then Ā can be viewed as the set of 6-permutations of {1, 2, 3, 4, 5, 6, 7, 89} and
the 6-permutations of {1, 2, 3, 4, 5, 6, 7, 98}. Thus the answer is
9! 8! 7!
|S| = P (9, 7) − 2P (8, 6) + 2P (7, 7) = − 2 × + 2 × = 151, 200.
2! 2! 0!
A circular r-permutation of a set S is an ordered r objects of S arranged as a circle; there is no the beginning
object and the ending object.
P (n, r) n!
= .
r (n − r)!r
3
Proof. Let S be an n-set. Let X be the set of all r-permutations of S, and let Y be the set of all circular r-
permutations of S. Define a function f : X −→ Y as follows: For each r-permutation a1 a2 · · · ar of S, f (a1 a2 · · · ar )
is the circular r-permutation such that a1 a2 . . . ar a1 a2 . . . is counterclockwise on a circle. Clearly, f is surjective.
Moreover, there are exactly r-permutations sent to one circular r-permutation. In fact, the r permutations
|X| P (n, r)
|Y | = = .
r r
Example 2.4. Twelve people, including two who do no wish to sit next to each other, are to be seated at a round
table. How many circular seating plans can be made?
First method: We may have 11 people (including one of the two unhappy persons but not both) to sit first; there
are 10! such seating plans. Next the second unhappy person can sit anywhere except the left side and right side of
the first unhappy person; there are 9 choices for the second unhappy person. Thus the answer is 9 × 10!.
Second method: There are 11! seating plans for the 12 people with no restriction. We need to exclude those seating
plans that the unhappy persons a and b sit next to each other. Note that a and b can sit next to each other in
two ways: ab and ba. We may view a and b as an inseparable twin; there are 2 × 10! such seating plans. Thus the
answer is given by
11! − 2 × 10! = 9 × 10!.
Example 2.5. How many different patterns of necklaces with 18 beads can be made out of 25 available beads of
the same size but in different colors?
P (25,18) 25!
Answer: 18×2 = 36×7! .
3 Combinations of Sets
A combination is a collection of objects
¡n¢ (order is immaterial) from a given set. An r-combination of an n-set S
is an r-subset of S. We denote by r the number of r-combinations of an n-set, read “n choose r.”
First Proof. Let S be an n-set. Let X be the set of all permutations of S, and let Y be the set of all r-subsets of
S. Consider a map f : X −→ Y defined by
Clearly, f is surjective. Moreover, for any r-subset A = {x1 , x2 , . . . , xr } ∈ Y , there are r! permutations of A and
(n − r)! permutations of the complement Ā. Then
4
Second Method: Let X be the set of all r-permutations of S and let Y be the set of all r-subsets of S. Consider a
map f : X −→ Y defined by
f (x1 x2 . . . xr ) = {x1 , x2 , . . . , xr }, x1 x2 . . . xr ∈ X.
Clearly, f is surjective. Moreover, there are exactly r! permutations of {x1 , x2 , . . . , xr } sent to {x1 , x2 , . . . , xr }. Thus
³n´ |X| P (n, r)
= |Y | = = .
r r! r!
¤
Example 3.1. How many 8-letter words can be constructed from 26 letters of the alphabets if each word contains
3, 4, or 5 vowels? It is understood that there is no restriction on the number of times a letter can be used in a word.
¡ ¢
The number of words with 3 vowels: There are 83 ways to choose 3 vowel positions in a word; each vowel
position
¡ 8 ¢ 3 5can be filled with one of the 5 vowels; the consonant position can be any of 21 consonants. Thus there are
3 5 21 words having exactly 3 vowels. ¡ ¢
The number of words with 4 vowels: 84 54 214 .
¡ ¢
The number of words with 5 vowels: 85 55 213 .
Thus the answer is µ ¶ µ ¶ µ ¶
8 3 5 8 4 4 8
5 21 + 5 21 + 55 213 .
3 4 5
Corollary 3.2. For integers n, r such that n ≥ r ≥ 0,
µ ¶ µ ¶
n n
= .
r n−r
4 Permutations of Multisets
Let M be a multiset. An r-permutation of M is an ordered arrangement of r objects of M . If |M | = n, then an
n-permutation of M is called a permutation of M .
Theorem 4.1. Let M be a multiset of k different types where each type has infinitely many elements. Then the
number of r-permutations of M equals
kr .
Example 4.1. What is the number of ternary numerals with at most 4 digits?
The question is to find the number of 4-permutations of the multiset {∞0, ∞1, ∞2}. Thus the answer is 34 = 81.
Theorem 4.2. Let M be a multiset of k types with repetition numbers n1 , n2 , . . . , nk respectively. Let n = n1 +
n2 + · · · + nk . Then the number of permutations of M equals
n!
.
n1 !n2 ! · · · nk !
Proof. List the elements of M as
a, . . . , a, b, . . . , b, . . . , d, . . . , d .
| {z } | {z } | {z }
n1 n2 nk
Let S be the set consisting of the elements a1 , a2 , . . . , an1 , b1 , b2 , . . . , bn2 , . . ., d1 , d2 , . . . , dnk . Let X be the set of
all permutations of S, and let Y be the set of all permutations of M . There is a map f : X −→ Y , sending each
permutation of S to a permutation of M by removing the subscripts of the elements. Note that for each permutation
5
π of M there are n1 !, n2 !, . . ., and nk ! ways to put the subscripts of the first, the second, ..., and the kth type
elements back, respectively. Thus there are n1 !n2 ! · · · nk ! elements of X sent to π by f . Therefore the answer is
|X| n!
|Y | = = .
n1 !n2 ! · · · nk ! n1 !n2 ! · · · nk !
Corollary 4.3. The number of 0-1 words of length n with exactly r ones and n − r zeros is equal to
n! ³n´
= .
r!(n − r)! r
Example 4.2. How many possibilities are there for 8 non-attacking rooks on an 8-by-8 chessboard? How about
having 8 different color rooks? How about having 1 red (R) rook, 3 blue (B) rooks , and 4 yellow (Y) rooks.
We label each square by an ordered pair (i, j) of coordinates, (1, 1) ≤ (i, j) ≤ (8, 8). Then the rooks must occupy
8 squares with coordinates
(1, a1 ), (2, a2 ), . . . , (8, a8 ),
where a1 , a2 , . . . , a8 must be distinct, i.e., a1 a2 . . . a8 is a permutation of {1, 2, . . . , 8}. Thus the answer is 8!.
When the 8 rooks have different colors, the answer is 8!8! = (8!)2 .
If there are 1 red rook, 2 blue rooks, and 3 yellow rooks, then we have a multiset M = {R, 3B, 4Y } of rooks.
8! 8!
The number of permutations of M equals 1!3!4! , and the answer in question is 8! × 1!3!4! .
Theorem 4.4. Given n rooks of k colors with n1 rooks of the first color, n2 rooks of the second color, ..., and nk
rooks of the kth color. The number of ways to arrange these rooks on an n-by-n board so that no two rooks can
attack another equals
n! (n!)2
n! × = .
n1 !n2 ! · · · nk ! n1 !n2 ! · · · nk !
Example 4.3. Find the number of 8-permutations of the multiset M = {a, a, a, b, b, c, c, c, c} = {3a, 2b, 4c}.
8!
The number of 8-permutations of {2a, 2b, 4c}: 2!2!4! .
8!
The the number of 8-permutations of {3a, b, 4c}: 3!1!4! .
8!
The number of 8-permutations of {3a, 2b, 3c}: 3!2!3! .
Thus the answer is
8! 8! 8!
+ + = 420 + 280 + 560 = 1, 260.
2!2!4! 3!1!4! 3!2!3!
5 Combinations of Multisets
Let M be a multiset. An r-combination of M is an unordered collection of r objects from M . Thus an r-combination
of M is itself an r-submultiset of M . For a multiset M = {∞a1 , ∞a2 , . . . , ∞an }, an r-combination of M is also
called an r-combination with repetition allowed of the n-set S = {a1 , a2 , . . . , an }. The number of r-combinations
with repetition allowed of an n-set is denoted by DnE
.
r
Theorem 5.1. Let M = {∞a1 , ∞a2 , . . . , ∞an } be a multiset of n types. Then the number of r-combinations of M
is given by ¿ À µ ¶ µ ¶
n n+r−1 n+r−1
= = .
r r n−1
Proof. When r objects are taken from the multiset M , we put them into the following boxes
6
so that the ith type objects are contained in the ith box, 1 ≤ i ≤ n. Since the objects of the same type are
indistinguishable, we may use the symbol “O” to denote any object in the boxes, and the objects in different boxes
are separated by a stick “|”. Convert the symbol “O” to zero 0 and the stick “|” to one 1, any such placement is
converted into a 0-1 sequence of length r + n − 1 with exactly r zeros and n − 1 ones. For example, for n = 4 and
r = 7,
OO O OOO O
{a, a, b, c, c, c, d} ←→ ←→ 0010100010
1 2 3 4
OOO OOO
{b, b, b, b, d, d, d} ←→ ←→ 1000011000
1 2 3 4
Now the problem becomes counting the number of 0-1 words of length r + (n − 1) with exactly r zeros and n − 1
ones. Thus the answer is ¿ À µ ¶ µ ¶
n n+r−1 n+r−1
= = .
r r n−1
n®
Corollary 5.2. The number r equals the number of ways to place r identical balls into n distinct boxes.
n®
Corollary 5.3. The number r equals the number of nonnegative integer solutions of the equation
x1 + x2 + · · · + xn = r.
n®
Corollary 5.4. The number r equals the number of nondecreasing sequences of length r whose terms are taken
from the set {1, 2, . . . , n}.
Example 5.1. Find the number of nonnegative integer solutions for the equation
x1 + x2 + x3 + x4 < 19.
The problem is equivalent to finding the number of nonnegative integer solutions of the equation
x1 + x2 + x3 + x4 + x5 = 18.
7
Week 4-5: Generating Permutations and Combinations
1 Generating Permutations
We have learned that there are n! permutations of {1, 2, . . . , n}. It is important in many instances to generate a
list of such permutations. For example, for the permutation 3142 of {1, 2, 3, 4}, we may insert 5 in 3142 to generate
five permutations of {1, 2, 3, 4, 5} as follows:
If we have a complete list of permutations for {1, 2, . . . , n − 1}, then we can obtain a complete list of permutations
for {1, 2, . . . , n} by inserting n in n ways to each permutation of the list for {1, 2, . . . , n − 1}.
For n = 1, the list is just
1
For n = 2, the list is
1 2 1 2
=⇒
2 1 2 1
For n = 3, the list is
1 2 3 1 2 3
1 3 2 1 3 2
3 1 2 3 1 2
=⇒
3 2 1 3 2 1
2 3 1 2 3 1
2 1 3 2 1 3
To generate a complete list of permutations for the set {1, 2, . . . , n}, we assign a direction to each integer
k ∈ {1, 2, . . . , n} by writing an arrow above it pointing to the left or to the right:
← →
k or k .
We consider permutations of {1, 2, . . . , n} in which each integer is given a direction; such permutations are called
directed permutations. An integer k in a directed permutation is called mobile if its arrow points to a smaller
→→←→→→
integer adjacent to it. For example, for 3 2 5 4 6 1 , the integers 3, 5, and 6 are mobile. It follows that 1 can never
be mobile since there is no integer in {1, 2, . . . , n} smaller than 1. The integer n is mobile, except two cases: (i) n
←
is the first integer and its arrow points to the left, i.e., n · · · ; (ii) n is the last integer and its arrow points to the
→
right, i.e., · · · n.
1
For n = 4, we have the list
1 2 3 4 1 2 3 4
1 2 4 3 1 2 4 3
1 4 2 3 1 4 2 3
4 1 2 3 4 1 2 3
4 1 3 2 4 1 3 2
1 4 3 2 1 4 3 2
1 3 4 2 1 3 4 2
1 3 2 4 1 3 2 4
3 1 2 4 3 1 2 4
3 1 4 2 3 1 4 2
3 4 1 2 3 4 1 2
4 3 1 2 4 3 1 2
=⇒
4 3 2 1 4 3 2 1
3 4 2 1 3 4 2 1
3 2 4 1 3 2 4 1
3 2 1 4 3 2 1 4
2 3 1 4 2 3 1 4
2 3 4 1 2 3 4 1
2 4 3 1 2 4 3 1
4 2 3 1 4 2 3 1
4 2 1 3 4 2 1 3
2 4 1 3 2 4 1 3
2 1 4 3 2 1 4 3
2 1 3 4 2 1 3 4
Proof. Observe that when n is not the largest mobile the direction of n must be either like
← →
n ··· or ··· n
2
in the permutation. When the largest mobile m (with m < n) is switched with its target integer to produce a new
permutation, the direction of n will be changed simultaneously, and the permutation with direction becomes
→ ←
n ··· or ··· n .
Now n is the largest mobile. Switching n with its target integer for n−1 times to produce n−1 more permutations, we
obtain exactly n new permutations (including the one before switching n). The algorithm stops at the permutation
←←→→ →
2 1 3 4 ··· n .
2 Inversions of Permutations
Let u1 u2 . . . un be a permutation of S = {1, 2, . . . , n}. We can view u1 u2 . . . un as a bijection π : S −→ S defined by
If ui > uj for some i < j, the ordered pair (ui , uj ) is called an inversion of π. The number of inversions of π is
denoted by inv(π). For example, the permutation 3241765 of {1, 2, . . . , 7} has the inversions:
(2, 1), (3, 1), (4, 1), (3, 2), (6, 5), (7, 5), (7, 6).
For k ∈ {1, 2, . . . , n} and uj = k, let ak be the number of integers that precede k in the permutation u1 u2 . . . un but
greater than k, i.e.,
It measures how much k is out of order by counting the numbers of integers larger than k but located before k. The
tuple (a1 , a2 , . . . , an ) is called the inversion sequence (or inversion table) of the permutation π = u1 u2 . . . un .
The sum a1 + a2 + · · · + an measures the total disorder of a permutation, and is denoted by inv(π).
Example 2.1. The inversion sequence of the permutation 3241765 of {1, 2, . . . , 7} is (3, 1, 0, 0, 2, 1, 0).
It is clear that for any permutation π of {1, 2, . . . , n}, the inversion sequence (a1 , a2 , . . . , an ) of π satisfies
It is easy to see that the number of sequences (a1 , a2 , . . . , an ) satisfying (1) equals n · (n − 1) · · · 2 · 1 = n!. This
suggests that the inversion sequences may be characterized by (1).
Theorem 2.1. Let (a1 , a2 , . . . , an ) be an integer sequence satisfying
0 ≤ a1 ≤ n − 1, 0 ≤ a2 ≤ n − 2, ..., 0 ≤ an−1 ≤ 1, an = 0.
3
..
.
Step n − 1. If a1 = 0, place 1 before all existing numbers; otherwise, place 1 to the right of the a1 th
existing number.
For example, for the inversion sequence (a1 , a2 , . . . , a8 ) = (4, 6, 1, 0, 3, 1, 1, 0), its permutation can be constructed
by Algorithm I as follows:
8 Write down 8.
87 Since a7 = 1, insert 7 to the right of the first number 8.
867 Since a6 = 1, insert 6 to the right of the first number 8.
8675 Since a5 = 3, insert 5 to the right of the third number 7.
48675 Since a4 = 0, insert 4 to the left of the first number 8.
438675 Since a3 = 1, insert 3 to the right of the first number 4.
4386752 Since a2 = 6, insert 2 to the right of the sixth number 5.
43861752 Since a1 = 4, insert 1 to the right of the fifth number 6.
Algorithm II. Construction of a Permutation from Its Inversion Sequence:
Step 0. Mark down n empty spaces ¤¤¤ · · · ¤¤¤.
Step 1. Put 1 into the (a1 + 1)th empty space from left.
Step 2. Put 2 into the (a2 + 1)th empty space from left.
..
.
Step k. Put k into the (ak + 1)th empty space from left.
..
.
Step n. Put n into the (an + 1)th empty space (the last empty box) from left.
For example, the permutation for the inversion sequence (a1 , a2 , . . . , a8 ) = (4, 6, 1, 0, 3, 1, 1, 0) can be constructed
by Algorithm II as follows:
¤¤¤¤¤¤¤¤ Mark down 8 empty spaces.
¤¤¤¤1¤¤¤ Since a1 = 4, put 1 into the 5th empty space.
¤¤¤¤1¤¤2 Since a2 = 6, put 2 into the 7th empty space.
¤3¤¤1¤¤2 Since a3 = 1, put 3 into the 2nd empty space.
43¤¤1¤¤2 Since a4 = 0, put 4 into the 1st empty space.
43¤¤1¤52 Since a5 = 3, put 5 into the 4th empty space.
43¤61¤52 Since a6 = 1, put 6 into the 2nd empty space.
43¤61752 Since a7 = 1, put 7 into the 2nd empty space.
43861752 Since a8 = 0, put 8 into the 1st empty space.
3 Generating Combinations
Let S be an n-set. For convenience of generating combinations of S, we take S to be the set
S = {xn−1 , xn−2 , . . . , x2 , x1 , x0 }.
Each subset A of S can be identified as a function χA : S −→ {0, 1}, called the characteristic function of A,
defined by ½
1 if x ∈ A
χA (x) =
0 if x 6∈ A.
In practice, χA is represented by a 0-1 sequence or a base 2 numeral. For example, for S = {x7 , x6 , x5 , x4 , x3 , x2 , x1 , x0 },
∅ 00000000
{x7 , x5 , x2 , x1 } 10100110
{x6 , x5 , x3 , x1 , x0 } 01101011
{x7 , x6 , x5 , x4 , x3 , x2 , x1 , x0 } 11111111
4
Algorithm 3.1. The algorithm for Generating Combinations of {xn−1 , xn−2 , . . . , x2 , x1 , x0 }:
Step 0. Begin with an−1 · · · a1 a0 = 0 · · · 00.
Step 1. If an−1 · · · a1 a0 = 1 · · · 11, stop.
Step 2. If an−1 · · · a1 a0 6= 1 · · · 11, find the smallest integer j such that aj = 0.
Step 3. Change aj , aj−1 , . . . , a0 (from 0 to 1 or from 1 to 0), write down an−1 · · · a1 a0 , and return
to Sept 1.
For n = 4, the algorithm produces the list
The unit n-cube Qn is a graph whose vertex set is the set of all 0-1 sequences of length n, and two sequences
are adjacent if they differ in only one place. A Gray code of order n is a path of Qn that visits every vertex of
Qn exactly once, i.e., a Hamilton path of Qn . For example,
is a Gray code of order 3. It is obvious that this Gray code can not be a part of any Hamilton cycle since 000 and
111 are not adjacent. A cyclic Gray code of order n is a Hamilton cycle of Qn . For example, the closed path
00 → 01 → 11 → 10.
For n = 3, we use the Gray code (of order 2) 00 → 01 → 11 → 10 to produce the path 000 → 001 → 011 → 010
by adding 0 in the front, and use the Gray code 10 → 11 → 01 → 00 (the reverse of 00 → 01 → 11 → 10) to produce
the path 110 → 111 → 101 → 100. Combine the two paths to produce the Gray code of order 3
The Gray codes obtained in this way are called reflected Gray codes.
Algorithm 3.2. Algorithm to generating a Reflected Gray Code of order n:
Step 0. Begin with an an−1 · · · a2 a1 = 00 · · · 0.
Step 1. If an an−1 · · · a2 a1 = 10 · · · 00, stop.
Step 2. If an + an−1 + · · · + a2 + a1 = even, then change a1 (from 0 to 1 or 1 to 0).
Step 3. If an + an−1 · · · + a2 + a1 = odd, find the smallest index j such that aj = 1 and change aj+1
(from 0 to 1 or 1 to 0).
Step 3. Write down an an−1 · · · a2 a1 and return to Step 1.
We note that if an an−1 · · · a1 6= 10 · · · 0 and an + an−1 + · · · + a1 = odd, then j ≤ n − 1 so that j + 1 ≤ n and
aj+1 is defined. We also note that the smallest number j in Step 3 may be 1, i.e., a1 = 1; if so there is no i < j
such that ai = 0 and we change aj+1 = a2 as instructed in Step 3.
Proof. We proceed by induction on n. For n = 1, it is obviously true. For n = 2, we have 00 → 01 → 11 → 10. Let
n ≥ 3 and assume that it is true for 1, 2, . . . , n − 1.
(1) When the algorithm is applied, by the induction hypothesis the first resulted 2n−1 words form the reflected
Gray code of order n − 1 with a 0 attached to the head of each word; the 2n−1 th word is 010 · · · 0.
(2) Continuing the algorithm, we have
010 · · · 0 → 110 · · · 0.
5
Now for each word of the form 11bn−2 · · · b1 , the parity of 11bn−2 · · · b1 is the same as the parity of bn−2 · · · b1 .
Continuing the algorithm, the next 2n−2 words (including 110 · · · 0) form a reflected Gray code (of order n − 2) with
a 11 attached at the beginning; the last word is 1110 · · · 0.
(3) Continuing the algorithm, we have
1110 · · · 0 → 1010 · · · 0 → · · ·
The next 2n−3 words (including 1010 · · · 0) form a reflected Gray code (of order n − 3) with a 101 attached at the
beginning; the last word is 10110 · · · 0.
(4) 10110 · · · 0 → 10010 · · · 0 →; there are 2n−4 words with 1001 attached at the beginning.
..
.
(n − 2) Continuing the algorithm, we have
10 · · · 01100 → 10 · · · 00100 → .
The next 22 words (including 10 · · · 0100) form a reflected Gray code (of order 2) with 10 · · · 01 attached at the
beginning; the last word is 10 · · · 0110.
(n − 1) 10 · · · 0110 → 10 · · · 0010 → 10 · · · 0011; there are 21 words (of order 1), 10 · · · 0010 → 10 · · · 0011, with
10 · · · 001 attached at the beginning.
(n) 10 · · · 0011 → 10 · · · 0001. The algorithm produces only 1 word 10 · · · 0001.
(n + 1) Finally, the algorithm ends at 10 · · · 0001 → 10 · · · 0000.
Note that all words produced from Step (k) to Step (n + 1) inclusive are distinct from the words produced in
Step (k − 1), where 2 ≤ k ≤ n + 1. Thus the words produced by the algorithm are distinct and the total number of
words is
2n−1 + 2n−2 + · · · + 22 + 21 + 20 + 1 = 2n .
This implies that the sequence of the words produced forms the reflected Gray code of order n.
Next we show that the words resulted in the second half of the algorithm are the words obtained from the
reversing of the reflected Gray codes of order n − 1 with 1 attached in the front. Consider two consecutive words of
length n in the second half of the algorithm, say,
4 Generating r-Combinations
Let S = {1, 2, . . . , n}. When an r-combination or an r-subset A = {a1 , a2 , . . . , ar } of S is given, we always assume
that a1 < a2 < · · · < ar . For two r-combinations A = {a1 , a2 , . . . , ar } and B = {b1 , b2 , . . . , br } of S, if there is an
integer k (1 ≤ k ≤ r) such that
6
we say that A precedes B in the lexicographic order, written A < B. Then the set Pr (S) of all r-subsets of
S is linearly ordered by the lexicographic order. For simplicity, we write an r-combination {a1 , a2 , . . . , ar } as an
r-permutation
a1 a2 · · · ar with a1 < a2 < · · · < ar .
Theorem 4.1. Let a1 a2 · · · ar be an r-combination of {1, 2, . . . , n}. The first r-combination in lexicographic order
is 12 · · · r, and the last r-combination in lexicographic order is
(n − r + 1) · · · (n − 1)n.
If a1 a2 · · · ak · · · ar 6= (n − r + 1) · · · (n − 1)n and k is the largest index such that ak 6= n − r + k, then the successor
of a1 a2 · · · ar is
a1 a2 · · · ak−1 (ak + 1)(ak + 2) · · · (ak + r − k + 1).
Proof. Since ai ≤ (n−r+i) for all 1 ≤ i ≤ r, then ak 6= n−r+k implies ak < n−r+k. Hence ak +r−k+1 < n+1.
Theorem 4.3. Let a1 a2 · · · ar be an r-combination of {1, 2, . . . , n}. Then the number of r-combinations up to the
place a1 a2 · · · ar in lexicographic order equals
µ ¶ µ ¶ µ ¶ µ ¶ µ ¶
n n − a1 n − a2 n − ar−1 n − ar
− − − ··· − − .
r r r−1 2 1
Proof. The r-combinations b1 b2¢· · · br after a1 a2 · · · ar can be classified into r kinds:
¡ n−a
(1) b1 > a1 ; there are r
1
such
³ r-combinations.
´
n−a2
(2) b1 = a1 , b2 > a2 ; there are r−1 such r-combinations.
³ ´
(3) b1 = a1 , b2 = a2 , b3 > a3 ; there are n−a r−2
3
such r-combinations.
..
. ¡ n−ar−1 ¢
(r − 1) b1 = a1 , . . ., br−2 = ar−2 , br−1 > ar−1 ; there
¡ n−aare
¢ 2 such r-combinations.
(r) b1 = a1 , . . ., br−1 = ar−1 , br > ar ; there are 1
r
¡such
¢ r-combinations.
Since the number of r-combinations of {1, 2, . . . , n} is nr , the conclusion follows immediately.
123, 124, 125, 134, 135, 145, 234, 235, 245, 345
The 3-permutations of {1, 2, 3, 4, 5} can be obtained by making 3! permutations for each 3-combination:
123 124 125 134 135 145 234 235 245 345
132 142 152 143 153 154 243 253 254 354
213 214 215 314 315 415 324 325 425 435
231 241 251 341 351 451 342 352 452 453
312 412 512 413 513 514 423 523 524 534
321 421 521 431 531 541 432 532 542 543
7
5 Partially Ordered Sets
Definition 5.1. A relation on a set X is a subset R ⊆ X × X. We say that two elements x and y of X satisfy the
relation R, written xRy, if (x, y) ∈ R. A relation R on X is said to be
1. reflexive if xRx for all x ∈ X;
4. antisymmetric provided that if x 6= y and xRy then y R̄x (equivalently, if xRy and yRx then x = y);
and it is a strict linear order relation. The relation “less than or equal to” in its ordinary meaning is the relation
© ª
R = (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4) ,
8
Proof. We need to show that the elements of X can be listed in some order x1 , x2 , . . . , xn in such a way that if
xi ≤ xj then xi comes before xj in this list, i.e., i ≤ j. The following algorithm does the job.
Algorithm 5.3. Algorithm for a Linear Extension of an n-Poset:
Step 1. Choose a minimal element x1 from X (with respect to the ordering ≤; if such elements are
not unique, choose any one).
Step 2. Delete x1 from X; choose a minimal element x2 from X − {x1 }.
Step 3. Delete x2 from X − {x1 }; choose a minimal element x3 from X − {x1 , x2 }.
..
.
Step n. Delete xn−1 from X − {x1 , . . . , xn−2 } and choose the only element xn in X − {x1 , . . . , xn−1 }.
Let R be an equivalence relation on a set X. For each element x ∈ X, we call the set [x] := {y ∈ X | xRy} an
equivalence class of R and x a representative of the equivalence class [x].
Theorem 5.4. Let R be an equivalence relation on a set X. Then for any x, y ∈ X, the following statements are
logically equivalent: (i) [x] ∩ [y] 6= ∅; (ii) [x] = [y]; and (iii) xRy.
is an equivalence relation on X.
Theorem 5.5. Let R be an equivalence relation on a set X, and let P = {A1 , A2 , . . . , Ak } be a partition of X.
Then
(i) PR is a partition of X;
Proof. Parts (i) and (ii) are trivial. We only prove Part (iii).
Let (x, y) ∈ RPR . Then, by definition of equivalence relation induced from the partition PR , there exists a part
A ∈ PR such that x, y ∈ A. Note that the parts in PR are the equivalence classes [x] of the equivalence relation
R; in particular A is an equivalence class of R. Since A contains both x and y, it follows that A = [x] = [y]. So
(x, y) ∈ R. Hence RPR ⊆ R.
Let (x, y) ∈ R. Then [x] = [y] is a part of PR . Thus [x] × [y] ⊆ RPR . Since (x, y) ∈ [x] × [y], we see that
(x, y) ∈ RPR . Therefore R ⊆ RPR .
A ∈ PRP ⇔ A is an equivalence class of the relation RP ⇔ A is a part of the partition P.
9
Homework 2
1
9. Let (J, ≤) be the partially ordered set with J = {0, 1} and with 0 < 1. By identifying the combinations of a
set X of n elements with the n-tuples of 0’s and 1’s, prove that the partially ordered set X, ⊆) can be identified
with the n-fold direct product (J, ≤) × (J, ≤) × · · · × (J, ≤) (n factors).
Supplementary Exercises
1. Find the number of ways to select m numbers from {1, 2, . . . , n} so that no two numbers are consecutive.
Method 1. Let a1 , a2 , . . . , am be such a selection and a1 < a2 < · · · < am . Let ki be the number of integers
between ai−1 and ai , where 1 ≤ i ≤ m + 1, a0 = 0 and am+1 = n + 1. Then the answer is equal to the number
of integral solutions of
k1 + k2 + · · · + km+1 = n − m
satisfying k1 ≥ 0, ki ≥ 1 for 2 ≤ i ≤ m, and km+1 ≥ 0. This is equivalent to finding the number of nonnegative
integral solutions of the equation
x1 + x2 + · · · + xm+1 = n − m − (m − 1) = n − 2m + 1.
Method 2. Let a1 , a2 , . . . , am be such a selection and a1 < a2 < · · · < am . If am 6= n, we change each pair
{ai , ai + 1} to a domino and any other number in {1, 2, . . . , n} to a square. Then the selection {a1 , a2 , . . . , am }
can be viewed as a permutation of dominoes and squares with exactly m dominoes and n − 2m squares. There
are µ ¶
n−m
m
such permutations.
If am = n, then am−1 6= n − 1. This is equivalent to selecting m − 1 integers from {1, 2, . . . , n − 1} such that
no two numbers are consecutive and the last number n − 1 is not selected. There are
µ ¶ µ ¶
n − 1 − (m − 1) n−m
=
m−1 m−1
2. A move of a permutation of {1, 2, . . . , n} is to take an integer in the permutation and insert it somewhere in
the permutation. For example,
Give an algorithm to compute the minimal number of moves to restore an arbitrary permutation of {1, 2, . . . , n}
back to the form 12 · · · n.
Solution. For any permutation a1 a2 · · · an of {1, 2, . . . , n}, we denote by δ(a1 a2 · · · an ) the minimal number of
moves required to change it back to 12 · · · n. Let n = ak for some k. Notice the following observation: If n
must be moved in order to change the permutation back to 12 · · · n, then
if n is not necessarily moved to change the permutation back to 12 · · · n, then the numbers ak+1 , . . . , an must
be moved in order to make n in the last position.
2
In the latter case, we observe that the moves of the numbers ak+1 , . . . , an do not change the relative positions
of the numbers a1 , a2 , . . . , ak−1 in the permutation a1 a2 · · · ak−1 . Since the minimal number of moves required
to sort a1 a2 · · · ak−1 is δ(a1 a2 · · · ak−1 ), we have
Note that the number 6 should not be moved; otherwise 4 moves are required to sort the permutation.
However, the number 6 must be moved in the permutation 136452 to achieve minimality:
3
Week 6-7: The Binomial Coefficients
•
• • •
• • • • • •
• • • • • • • • • •
¡ ¢ ¡n¢
The numbers n3 = n(n−1)(n−2)
6 (n ≥ 3) are tetrahedral numbers, i.e., 3 is the number of lattice points of
the polytope ∆3 (n) defined by
Theorem 1.2. The number of nondecreasing coordinate paths from (0, 0) to (m, n) with m, n ≥ 0 equals
µ ¶
m+n
.
m
3 Binomial Identities
Definition 3.1. For any real number α and integer k, define the binomial coefficients
µ ¶ 0 if k < 0
α
= 1 if k = 0
k α(α−1)···(α−k+1)
k! if k > 0
Proposition 3.2. 1. For real number α and integer k,
µ ¶ µ ¶ µ ¶
α α−1 α−1
= + .
k k k−1
1
2. For real number α and integer k, µ ¶ µ ¶
α α−1
k =α .
k k−1
Proof.
X µ ¶
n
= xn1 1 xn2 2 · · · xnk k .
n1 +n2 +···+nk =n
n1 , n2 , . . . , nk
n1 ,n2 ,...,nk ≥0
2
5 The Newton Binomial Theorem
Theorem 5.1 (Newton’s Binomial Expansion). Let α be a real number. If 0 ≤ |x| < |y|, then
∞ µ ¶
X α
(x + y)α = xk y α−k ,
k
k=0
where µ ¶
α α(α − 1) · · · (α − k + 1)
= .
k k!
Proof. Apply the Taylor expansion formula for the function (x + y)α of two variables.
The identity µ ¶ µ ¶
−α α+k−1
= (−1)k .
k k
is called the reciprocity law of binomial coefficients.
µX
∞ ¶ µX
∞ ¶
1 k k
= z ··· z
(1 − z)n
k=0 k=0
∞
X X
k
= z 1
k=0 k1 +···+kn =k
X∞ µ ¶
n+k−1 k
= z .
k
k=0
This shows again that the number of nonnegative integer solutions of the equation
x1 + x2 + · · · + xn = k
s0 ≤ s1 ≤ · · · ≤ sk ≥ sk+1 ≥ · · · ≥ sn .
3
Theorem 6.2. Let n be a positive integer. The sequence of binomial coefficients
³n´ ³n´ ³n´ ³n´
, , , ...,
0 1 2 n
is an unimodal sequence. More precisely, if n is even,
µ ¶ µ ¶ µ ¶ µ ¶ µ ¶
n n n n n
< < ··· < > ··· > > ;
0 1 n/2 n−1 n
and if n is odd,
µ ¶ µ ¶ µ ¶ µ ¶ µ ¶ µ ¶
n n n n n n
< < ··· < = > ··· > > .
0 1 (n − 1)/2 (n + 1)/2 n−1 n
A cluster of a set S is a collection A of subsets of S such that no one is contained in another. A chain is a
collection C of subsets of S such that for any two subsets, one subset is always contained in another subset. For
example, for S = {a, b, c, d}, the collection
n o
A = {a, b}, {b, c, d}, {a, c}, {a, d}
Proof. Let S = {1, 2, . . . , n}. We actually prove the following stronger result by induction on n:
³ ´
n
The power set P (S) can be partitioned into m disjoint chains C1 , C2 , . . ., Cm , where m = bn/2c .
If so, then for any cluster A of S,
|A ∩ Ci | ≤ 1 for all 1 ≤ i ≤ m;
and consequently, µ ¶
n
|A | ≤ m = .
bn/2c
³ ´ ¡1¢
n
For n = 1, bn/2c = 0 = 1,
∅ ⊂ {1}.
³ ´ ¡2¢
n
For n = 2, bn/2c = 1 = 2,
∅ ⊂ {1} ⊂ {1, 2},
{2}.
³ ´ ¡3¢
n
For n = 3, bn/2c = 1 = 3,
∅ ⊂ {1} ⊂ {1, 2} ⊂ {1, 2, 3},
{2} ⊂ {2, 3},
{3} ⊂ {1, 3}.
4
³ ´ ¡ ¢
n
For n = 4, bn/2c = 42 = 6; the 6 chains can be obtained in two ways: (i) Attach a new subset at the end
to each chain of the chain partition for n = 3 (this new subset is obtained by appending 4 to the last subset of the
chain); (ii) delete the last subsets in all chains of the partition for n = 3 and append 4 to all the remaining subsets.
Note that the chain partition satisfies the properties: (i) Each chain is saturated in the sense that no subset can be
added in between any two consecutive subsets; (ii) in each chain the size of the beginning subset plus the size of the
ending subset equals n. A chain partition satisfying the two properties is called a symmetric chain partition.
The above chain partitions for n = 1, 2, 3, 4 are symmetric chain partitions.
Given a symmetric chain partition for the case n − 1; we construct a symmetric chain partition for the case n:
For each chain A1 ⊂ A2 ⊂ · · · ⊂ Ak in the chain partition for the case n − 1,
if k ≥ 2, do A1 ⊂ A2 ⊂ · · · ⊂ Ak ⊂ Ak ∪ {n}, and
A1 ∪ {n} ⊂ A2 ∪ {n} ⊂ · · · ⊂ Ak−1 ∪ {n};
if k = 1, do A1 ⊂ A1 ∪ {n}.
It is clear that the chains constructed form a symmetric chain partition. In fact, the chains constructed are obviously
saturated. Since |A1 | + |Ak | = n − 1, then |A1 | + |Ak ∪ {n}| = |A1 | + |Ak | + 1 = n, and when k ≥ 2,
Now for any chain B1 ⊂ B2 ⊂ · · · ⊂ Bl of the symmetric chain partition for the case n, since |B1 | ≤ |Bl |, we
must have |B1 | ≤ n/2 ≤ |Bl | (otherwise, if |Bl | < n/2 then |B1 | + |B2 | < n, or if |B1 | > n/2 then |B1 | + |Bl | > n).
By definition of bn/2c and dn/2e, we have
The proof of the Spencer theorem actually gives the construction of clusters of maximal size. When n = even,
there is only one such cluster,
P n2 (S) : the collection of all n2 -subsets of S;
and when n = odd, there are exactly two such clusters,
n−1
P n−1 (S) : the collection of all 2 -subsets of S, and
2
n+1
P n+1 (S) : the collection of all 2 -subsets of S.
2
5
¡ ¢ ¡ ¢
Example 6.1. (a) Let S = {1}. Then n = 1 and 10 = 11 = 1. There are two clusters: ∅ and {1}.
¡ ¢ © ª
(b) Let S = {1, 2}. Then n = 2 and 21 = 2. There is only one cluster of maximal size: {1}, {2} .
¡3¢ ¡3¢
(c) Let S = {1, 2, 3}. Then n = 3 and 1 = 2 = 3. There are two clusters of maximal size:
© ª © ª
{1}, {2}, {3} and {1, 2}, {1, 3}, {2, 3}
¡ ¢
(d) Let S = {1, 2, 3, 4}. Then n = 4 and 42 = 6. There is only one cluster of maximal size:
© ª
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}
¡ ¢ ¡ ¢
(e) Let S = {1, 2, 3, 4, 5}. Then n = 5 and 52 = 53 = 10. There are two clusters of maximal size:
© ª
{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5} ,
© ª
{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5} .
Example 7.1. Let X = {1, 2, . . . , 10}. The divisibility | makes X into a partially ordered set. The subsets
{2, 3, 5, 7}, {2, 3, 7, 10}, {3, 4, 7, 10}, {3, 5, 7, 8}, {4, 5, 6, 7, 9}, {4, 6, 7, 9, 10}, {5, 6, 7, 8, 9}, {6, 7, 8, 9, 10}
are antichains, they are actually maximal antichains; while the subsets
Let (X, ≤) be a finite poset. We are interested in partitioning X into disjoint union of antichains and partitioning
X into disjoint union of chains. Let A be an antichain partition of X and let C be a chain of X. Since no two
elements of C can be contained in any antichain in A, then
|A| ≥ |C|.
Similarly, for any chain partition C and an antichain A of X, there are no two elements of A belonging to a chain
of C, we then have
|C| ≥ |A|.
Theorem 7.1. Let (X, ≤) be a finite poset, and let r be the largest size of a chain. Then X can be partitioned into
r but no fewer antichains. In other words,
© ª © ª
min |A| : A is an antichain partition = max |C| : C is a chain .
Proof. It is enough to show that X can be partitioned into r antichains. Let X1 = X and let A1 be the set of all
minimal elements of X1 . Let X2 = X1 − A1 and let A2 be the set of all minimal elements of X2 . Let X3 = X2 − A2
and let A3 be the set of all minimal elements of X3 . Continuing this procedure we obtain a decomposition of
X into antichains A1 , A2 , . . . , Ap . By the previous argument we always have p ≥ r. On the other hand, for any
ap ∈ Ap , there is an element ap−1 ∈ Ap−1 such that ap−1 < ap . Similarly, there is an element ap−2 ∈ Ap−2 such that
ap−2 < ap−1 . Continuing this process we obtain a chain a1 < a2 < · · · < ap . Since C is a chain of largest size, we
then have r ≥ p. Thus p = r.
6
The following dual version of the theorem is known as the Dilworth Theorem.
Theorem 7.2 (Dilworth). Let (X, ≤) be a finite poset. Let s be the largest size of an antichain. Then X can be
partitioned into s, but not less than s, chains. In other words,
Proof. It suffices to show that X can be partitioned into s chains. We proceed by induction on the number n of
elements in X. For n = 1, it is trivially true. Assume that n ≥ 2. Note that the set of all minimal elements of X is
an antichain; similarly, the set of all maximal elements of X is an antichain. We cinsider two cases:
Case 1. The set X has only the antichain of minimal elements and the antichain of maximal elements of X.
Take a minimal element x and a maximal element y such that x ≤ y (we may have x = y). Let X 0 = X − {x, y}.
Then |X 0 | ≤ n − 1 and the largest antichains of X 0 is s − 1. Thus by induction, the set X 0 can be partitioned into
s − 1 chains C1 , . . . , Cs−1 . Set Cs = {x ≤ y}. The collection {C1 , . . . , Cs } is a chain partition of X.
Case 2. The set X has an antichain A = {a1 , a2 , . . . , as } of size s that is neither the antichain of all minimal
elements nor the antichain of all maximal elements of X. Let
4. A− ∪ A+ = X. (If there is an element x not in A− ∪ A+ , then A ∪ {x} would be an antichain of larger size
than A.)
Since A− and A+ are smaller posets having antichains of size s, then by induction, A− can be partitioned into
s chains C1− , C2− , . . . , Cs− with the maximal elements a1 , a2 , . . . , as respectively, and A+ can be partitioned into s
chains C1+ , C2+ , . . . , Cs+ with the minimal elements a1 , a2 , . . . , as respectively. Thus we obtain a partition of X into
s chains
C1− ∪ C1+ , C2− ∪ C2+ , . . . , Cs− ∪ Cs+ .
Example 7.2. Let X = {1, 2, . . . , 20} be the poset with the partial order of divisibility. Then the subset
{1, 2, 4, 8, 16} of 5 elements is a chain of maximal size. The set X can be partitioned into 5 antichains
{1}, {2, 3, 5, 7, 11, 13, 17, 19}, {4, 6, 9, 10, 14, 15}, {8, 12, 18, 20}, {16}.
However, the size of the antichain {2, 3, 5, 7, 11, 13, 17, 19} is not maximal. In fact, {4, 6, 7, 9, 10, 11, 13, 15, 17, 19} is
an antichain of 10 elements. The set X can be partitioned into 10 chains
{1, 2, 4, 8, 16}, {3, 6, 12}, {5, 10, 20}, {7, 14}, {9, 18}, {11}, {13}, {15} {17}, {19}.
This means that {4, 6, 7, 9, 10, 11, 13, 15, 17, 19} is an antichain of maximal size.
Example 7.3. Let X = {(i, j) ∈ Z2 : 0 ≤ i, j ≤ 3, }be a poset whose partial order ≤ is defined by (i, j) ≤ (k, l) if
and only if i ≤ k and j ≤ l. The size of the longest chain is 7. For instance,
(0, 0) < (1, 0) < (1, 1) < (1, 2) < (2, 2) < (2, 3) < (3, 3)
{(0, 0)}, {(1, 0), (0, 1)}, {(2, 0), (1, 1), (0, 2)}, {(3, 0), (2, 1), (1, 2), (0, 3)},
7
{(3, 1), (2, 2), (1, 3)}, {(3, 2), (2, 3)}, {(3, 3)}
is an antichain partition of X. The maximal size of antichain is 4 and the poset X can be partitioned into 4 disjoint
chains:
(0, 0) < (0, 1) < (0, 2) < (0, 3) < (1, 3) < (2, 3) < (3, 3), {(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)},
(1, 0) < (1, 1) < (1, 2) < (2, 2) < (3, 2), {(1, 0), (1, 1), (1, 2), (2, 2), (3, 2)},
(2, 0) < (2, 1) < (3, 1), {(2, 0), (2, 1), (3, 1)},
(3, 0). {(3, 0)}.
(3, 3)
. &
(3, 2) (2, 3)
. & . &
(3, 1) (2, 2) (1, 3)
. & . & . &
(3, 0) (2, 1) (1, 2) (0, 3)
& . & . & .
(2, 0) (1, 1) (0, 2)
& . & .
(1, 0) (0, 1)
& .
(0, 0)
Finding an antichain of maximal size for a poset is a difficult problem. So far there is no canonical way to do
this job.
8
Week 8-9: The Inclusion-Exclusion Principle
Corollary 1.2. The number of objects of S which have at least one of the properties P1 , P2 , . . . , Pn is given by
X X X
|A1 ∪ A2 ∪ · · · ∪ An | = |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − · · ·
i i<j i<j<k
n+1
· · · + (−1) |A1 ∩ A2 ∩ · · · ∩ An |. (2)
Proof. Note that the set A1 ∪ A2 ∪ · · · ∪ An consists of all those objects in S which possess at least one of the
properties, and
|A1 ∪ A2 ∪ · · · ∪ An | = |S| − |A1 ∪ A2 ∪ · · · ∪ An |.
Then by the DeMorgan law we have
A1 ∪ A2 ∪ · · · ∪ An = Ā1 ∩ Ā2 ∩ · · · ∩ Ān .
Thus
|A1 ∪ A2 ∪ · · · ∪ An | = |S| − |Ā1 ∩ Ā2 ∩ · · · ∩ Ān |.
Putting this into the identity (1), the identity (2) follows immediately.
1
2 Combinations with Repetition
Let M be a multiset. Let x be an object of M and its repetition number is larger than r. Let M 0 be the multiset
whose objects have the same repetition numbers as those objects in M , except that the repetition number of x in
M 0 is exactly r. Then
#{r-combinations of M } = #{r-combinations of M 0 }.
Example 2.1. Determine the number of 10-combinations of the multiset M = {3a, 4b, 5c}.
Let S be the set of 10-combinations of the multiset M 0 = {∞a, ∞b, ∞c}. Let P1 be the property that a 10-
combination of M 0 has more than 3 a’s, let P2 be the property that a 10-combination of M 0 has more than 4 b’s,
and let P3 be the property that a 10-combination of M 0 has more than 5 c’s. Then the number of 10-combinations
of M is the number of 10-combinations of M 0 which have none of the properties P1 , P2 , and P3 . Let Ai be the
sets consisting of the 10-combinations of M 0 which have the property Pi , 1 ≤ i ≤ 3. Then by inclusion-exclusion
principle the number to be determined in the problem is given by
³ ´ ³ ´
|Ā1 ∩ Ā2 ∩ Ā3 | = |S| − |A1 | + |A2 | + |A3 | + |A1 ∩ A2 | + |A1 ∩ A3 | + |A2 ∩ A3 | − |A1 ∩ A2 ∩ A3 |.
|A2 ∩ A3 | = 0,
|A1 ∩ A2 ∩ A3 | = 0.
Putting all these results into the inclusion-exclusion formula, we have
{3a, 4b, 3c}, {3a, 3b, 4c}, {3a, 2b, 5c}, {2a, 4b, 4c}, {2a, 3b, 5c}, {a, 4b, 5c}.
x1 + x2 + x3 + x4 = 15
2 ≤ x1 ≤ 6, −2 ≤ x2 ≤ 1, 0 ≤ x3 ≤ 6, 3 ≤ x4 ≤ 8.
y1 + y2 + y3 + y4 = 12
subject to
0 ≤ y1 ≤ 4, 0 ≤ y2 ≤ 3, 0 ≤ y3 ≤ 6, 0 ≤ y4 ≤ 5.
Let S be the set of all nonnegative integral solutions of the equation y1 + y2 + y3 + y4 = 12. Let P1 be the
property that y1 ≥ 5, P2 the property that y2 ≥ 4, P3 the property that y3 ≥ 7, and P4 the property that y4 ≥ 6.
2
Let Ai denote the subset of S consisting of the solutions satisfying the property Pi , 1 ≤ i ≤ 4. Then the problem is
to find the cardinality |Ā1 ∩ Ā2 ∩ Ā3 ∩ Ā4 | by the inclusion-exclusion principle. In fact,
¿ À µ ¶ µ ¶
4 4 + 12 − 1 15
|S| = = = = 455.
12 12 12
Similarly,
¿ À µ ¶ µ ¶
4 4+7−1 10
|A1 | = = = = 120,
7 7 7
¿ À µ ¶ µ ¶
4 4+8−1 11
|A2 | = = = = 165,
8 8 8
¿ À µ ¶ µ ¶
4 4+5−1 8
|A3 | = = = = 56,
5 5 5
¿ À µ ¶ µ ¶
4 4+6−1 9
|A4 | = = = = 84.
6 6 6
For the intersections of two sets, we have
¿ À µ ¶ µ ¶
4 4+3−1 6
|A1 ∩ A2 | = = = = 20,
3 3 3
|A1 ∩ A3 | = 1, |A1 ∩ A4 | = 4, |A2 ∩ A3 | = 4, |A2 ∩ A4 | = 10, |A3 ∩ A4 | = 0.
For the intersections of more sets,
|A1 ∩ A2 ∩ A3 | = |A1 ∩ A2 ∩ A4 | = |A1 ∩ A3 ∩ A4 | = |A2 ∩ A3 ∩ A4 | = |A1 ∩ A2 ∩ A3 ∩ A4 | = 0.
Thus the number required is given by
|Ā1 ∩ Ā2 ∩ Ā3 ∩ Ā4 | = 455 − (120 + 165 + 56 + 84) + (20 + 1 + 4 + 4 + 10) = 69.
3 Derangements
A permutation of {1, 2, . . . , n} is called a derangement if every integer i (1 ≤ i ≤ n) is not placed at the ith
position. We denote by Dn the number of derangements of {1, 2, . . . , n}.
Let S be the set of all permutations of {1, 2, . . . , n}. Then |S| = n!. Let Pi be the property that a permutation
of {1, 2, . . . , n} has the integer i in its ith position, and let Ai be the set of all permutations satisfying the property
Pi , where 1 ≤ i ≤ n. Then
Dn = |Ā1 ∩ Ā2 ∩ · · · ∩ Ān |.
For each (i1 , i2 , . . . , ik ) such that 1 ≤ i1 < i2 < · · · < ik ≤ n, a permutation of {1, 2, . . . , n} with i1 , i2 , . . . , ik fixed at
the i1 th, i2 th, . . ., ik th position respectively can be identified as a permutation of the set {1, 2, . . . , n}−{i1 , i2 , . . . , ik }
of n − k objects. Thus
|Ai1 ∩ Ai2 ∩ · · · ∩ Aik | = (n − k)!.
By the inclusion-exclusion principle, we have
n
X X
|Ā1 ∩ Ā2 ∩ · · · ∩ Ān | = |S| + (−1)k |Ai1 ∩ Ai2 ∩ · · · ∩ Aik |
k=1 i1 <i2 <···<ik
n
X X
= n! + (−1)k (n − k)!
k=1 i1 <i2 <···<ik
n
X ³n´
= (−1)k (n − k)!
k
k=0
n
X (−1)k n!
= n! ' (when n is large.)
k! e
k=0
3
Theorem 3.1. For n ≥ 1, the number Dn of derangements of {1, 2, . . . , n} is
µ ¶
1 1 1 n 1
Dn = n! 1 − + − + · · · + (−1) . (3)
1! 2! 3! n!
Corollary 3.2. The number of permutations of {1, 2, . . . , n} with exactly k numbers displaced is
³n´
Dk .
k
Here are a few derangement numbers:
D0 ≡ 1, D1 = 0, D2 = 1, D3 = 2, D4 = 9, D5 = 44.
with the initial condition D1 = 0, D2 = 1. The sequence Dn satisfies the recurrence relation
Dn = nDn−1 + (−1)n , n ≥ 2.
Proof. The recurrence relations can be proved without using the formula (3). Let Sk be the set of derangements
ka2 a3 · · · an of {1, 2, . . . , n} that have k at the beginning, k = 2, 3, . . . , n. The derangements in each Sk can be
partitioned into two types:
We may think of that the right position for the integer k is the first position, and the right position for the integer
1 is the kth position. Then there are Dn−1 derangements of the first type and Dn−2 derangements of the second
type. We thus obtain the recurrence relation
Dn = (n − 1)(Dn−1 + Dn−2 ).
4 Surjective Functions
Let X be a set with m objects and Y be a set with n objects. Then the number of functions of X to Y is nm . The
number of injective functions from X to Y is
³n´
m! = P (n, m).
m
Let C(m, n) denote the number of surjective functions from X to Y . What is C(m, n)?
Theorem 4.1. The number C(m, n) of surjective functions from a set of m objects to a set of n objects is given by
n
X ³n´
C(m, n) = (−1)k (n − k)m .
k
k=0
4
Proof. Let S be the set of all functions of X to Y . Write Y = {y1 , y2 , . . . , yn }. Let Ai be the set of all functions f
such that yi is not assigned to any element of X by f , i.e., yi 6∈ f (X), where 1 ≤ i ≤ n. Then
For each (i1 , i2 , . . . , ik ) such that 1 ≤ i1 < i2 < · · · < ik ≤ n, the set Ai1 ∩ Ai2 ∩ · · · ∩ Aik can be identified to the set
of all functions f from X to the complement Y − {i1 , i2 , . . . , ik }. Thus
X µ ¶ n
X ³n´
m
= (−1)k (n − k)m .
i1 , . . . , in k
i1 +···+in =m k=0
i1 ,...,in ≥1
Proof. The integer C(m, n) can be interpreted as the number of ways to place the objects of X into n distinct boxes
such that no one is empty. We then have
X µ ¶
m
C(m, n) = .
i +···+in =m
i1 , . . . , in
1
i1 ,...,in ≥1
The integer-valued function φ is defined on the set of positive integers, and is called the Euler phi function.
Theorem 5.1. Let n be a positive integer factorized into the form n = pe11 pe2r · · · perr , where p1 , p2 , . . . , pr are distinct
primes and e1 , e2 , . . . , er ≥ 1. Then the Euler function φ(n) is given by
r µ
Y ¶
1
φ(n) = n 1− .
pi
i=1
5
Proof. Let S = {1, 2, . . . , n}. Let Pi be the property that an integer of S has pi as a factor, and let Ai be the set of
all integers in S that have the property Pi , where 1 ≤ i ≤ r. Then φ(n) is the number of integers that have none of
the properties P1 , P2 , . . . , Pr , i.e.,
φ(n) = |Ā1 ∩ Ā2 ∩ · · · ∩ Ār |.
Note that ½ µ ¶ ¾
n
Ai = pi , 2pi , 3pi , . . . , pi , 1 ≤ i ≤ r.
pi
More generally, if 1 ≤ i1 < i2 < · · · < ik ≤ r, then
½ µ ¶ ¾
n
Ai1 ∩ Ai2 ∩ · · · ∩ Aik = q, 2q, 3q . . . , q , where q = pi1 pi2 · · · pik .
q
Thus
n
|Ai1 ∩ Ai2 ∩ · · · ∩ Aik | = .
pi1 pi2 · · · pik
By the inclusion-exclusion principle, we have
r
X X
|Ā1 ∩ Ā2 ∩ · · · ∩ Ār | = |S| + (−1)k |Ai1 ∩ Ai2 ∩ · · · ∩ Aik |
k=1 i1 <i2 <···<ik
r
X X n
= n+ (−1)k
pi1 pi2 · · · pik
k=1 i1 <i2 <···<ik
· µ ¶
1 1
= n 1− + ··· +
p1 pr
µ ¶
1 1 1
+ + + ··· +
p1 p2 p1 p3 pr−1 pr
µ ¶
1 1 1
− + + ··· +
p1 p2 p3 p1 p2 p4 pr−2 pr−1 pr
¸
1
+ · · · + (−1)r
p1 p2 · · · p r
Yr µ ¶
1
= n 1− .
pi
i=1
6
Proof. It suffices to show that f is surjective. Since gcd(m1 , m2 ) = 1, there are integers x and y such that
xm1 + ym2 = 1. For each (r1 , r2 ) ∈ [1, m1 ] × [1, m2 ], set r = r2 xm1 + r1 ym2 . Then
Proof. The first part follows from Lemma 5.3. The second part follows from the first part, i.e.,
Y r r ³ ´ Yr µ ¶ r µ ¶
¡ ei ¢ Y ei ei −1 ei 1 Y 1
φ(n) = φ pi = pi − pi = pi 1 − =n 1− .
pi pi
i=1 i=1 i=1 i=1
a1 6∈ X1 , a2 6∈ X2 , ..., an 6∈ Xn .
In other words, a permutation of S belongs to P (X1 , X2 , . . . , Xn ) provided that no element of X1 occupy the
first place, no element of X2 occupy the second place, ..., and no element of Xn occupy the nth place. We use
p(X1 , X2 , . . . , Xn ) to denote the number of permutations in P (X1 , X2 , . . . , Xn ), i.e.,
It is known that there is a one-to-one correspondence between permutations of {1, 2, . . . , n} and the placement
of n non-attacking, indistinguishable rooks on an n-by-n board. The permutation a1 a2 · · · an of {1, 2, . . . , n} corre-
sponds to the placement of n rooks on the board in the squares with coordinates (1, a1 ), (2, a2 ), . . ., (n, an ). The
permutations in P (X1 , X2 , . . . , Xn ) corresponds to placements of n non-attacking rooks on an n-by-n board in which
certain squares are not allowed to be put a rook.
Let S be the set of all placements of n non-attacking rooks on an n × n-board. A rook placement in S is said
to satisfy the property Pi provided that the rook in the ith row is in a column that belongs to Xi (i = 1, 2, . . . , n).
As usual let Ai denote the set of all rook placements satisfying the property Pi (i = 1, 2, . . . , n). Then by the
Inclusion-Exclusion Principle we have
7
Proposition 6.1. Let rk (1 ≤ k ≤ n) denote the number of ways to place k non-attacking rooks on an n × n-board
where each of the k rooks is in a forbidden position. Then
1 X
rk = |Ai1 ∩ Ai2 ∩ · · · ∩ Aik |. (4)
(n − k)!
1≤i1 <i2 <···<ik ≤n
Proof. Fix 1 ≤ i1 < i2 < · · · < ik ≤ n. Let r(i1 , i2 , . . . , ik ) be the number of ways to place k non-attacking rooks on
the i1 th row, the i2 th row, . . ., the ik th row such that the i1 th rook is not in Xi1 , the i2 th rook is not in Xi2 , . . .,
the ik th rook is not in Xik . For each such k rook arrangement, delete the rows and columns they located (for the
other n − k rooks cannot be arranged in those rows and columns), the leftover is an (n − k) × (n − k)-board, and
the other n − k rooks can be arranged there in (n − k)! ways. So
Theorem 6.2. The number of ways to place n non-attacking rooks on an n × n-board with forbidden positions is
given by
n
X
p(X1 , X2 , . . . , Xn ) = (−1)k rk (n − k)!,
k=0
where rk is the number of ways to place k non-attacking rooks on an n × n-board where each of the k rooks is in a
forbidden position.
Example 6.1. Let n = 5 and X1 = {1, 2}, X2 = {3, 4}, X3 = {1, 5}, X4 = {2, 3}, and X5 = {4, 5}.
× ×
× ×
× ×
× ×
× ×
1 P P
Note that r1 = 4! i |Ai | = 5 × 2 = 10. So r1 4! = i |Ai | = 10 · 4!. Since
× × × × × ×
× × × × × ×
× × × × × ×
8
× × × × × ×
× × × × × ×
× × × × × ×
We then have r3 = 5 · 6 + 5 · 4 = 50. Using symmetry again, we see that
5! − 10 × 4! + 35 × 3! − 50 × 2! + 25 × 1! − 2 = 13.
A permutation of {1, 2, . . . , n} is said to be nonconsecutive if 12, 23, . . ., (n − 2)(n − 1), (n − 1)n do not occur.
We denote by Qn the number of nonconsecutive permutations of {1, 2, . . . , n}.
Proof. Let S be the set of all permutations of {1, 2, . . . , n}. Let Pi be the property that in a permutation the pattern
i(i + 1) does occur, and let Ai be the set of all permutations satisfying the property Pi , 1 ≤ i ≤ n − 1. Then Qn is
equal to the number of permutations satisfying none of the properties, i.e., Qn = |Ā1 ∩ Ā2 ∩ · · · ∩ Ān |. Note that
|Ai | = (n − 1)!, i = 1, 2, . . . , n − 1.
Similarly,
|Ai ∩ Aj | = (n − 2)!, i < j.
More generally,
|Ai1 ∩ Ai2 ∩ · · · ∩ Aik | = (n − k)!.
Thus by the inclusion-exclusion principle,
n−1
X X n−1
X µ ¶
k k n−1
Qn = |S| + (−1) |Ai1 ∩ Ai2 ∩ · · · ∩ Aik | = (−1) (n − k)!.
k
k=1 1≤i1 <i2 <···<ik ≤n−1 k=0
Example 6.2. Suppose 8 persons line up in one column in such a way that every person except the first one has
a person in front. What is the chance when the 8 persons reline up after a break so that everyone has a different
person in his/her front?
We assign numbers 1, 2, . . . , 8 to the 8 persons so that the number i is assigned to the ith person (counted from
the front). Then the problem becomes to find the number of permutations of {1, 2, . . . , 8} in which the patterns 12,
23, . . ., 78 do not occur. For instance, 31542876 is an allowed permutation, while 83475126 is not.
The answer is given by
7 µ ¶
Q8 X 7 (8 − k)!
P = = (−1)k .
8! k 8!
k=0
Example 6.3. There are n persons seating at a round table. The n persons left the table and reseat after a break.
How many seating plans can be made in the second time so that each person has a different person seating on
his/her left comparing to the person before the break?
This is equivalent to finding the number of circular nonconsecutive permutations of {1, 2, . . . , n}. A circular
nonconsecutive permutation of {1, 2, . . . , n} is circular permutation of {1, 2, . . . , n} such that 12, 23, . . ., (n − 1)n,
n1 do not occur in the counterclockwise direction.
9
Let S be the set of all circular permutations of {1, 2, . . . , n}. Let Ai denote the subset of all circular permutations
of {1, 2, . . . , n} such that i(i + 1) does not occur, 1 ≤ i ≤ n. We understand that An is the subset of all circular
permutations that n1 does not occur. Then the answer is |Ā1 ∩ Ā1 ∩ · · · ∩ Ān |. Note that
More generally,
|Ai1 ∩ · · · ∩ Aik | = (n − k)!/(n − k) = (n − k − 1)!, 1 ≤ k ≤ n − 1;
|S| = (n − 1)! and |A1 ∩ A2 ∩ · · · ∩ An | = 1. We thus have
n−1
X ³n´
|Ā1 ∩ · · · ∩ Ān | = (−1)k (n − k − 1)! + (−1)n .
k
k=0
Theorem 6.4.
Qn = Dn + Dn−1 , n ≥ 2.
Proof.
n
X n−1
X
(−1)k (−1)k
Dn + Dn−1 = n! + (n − 1)!
k! k!
k=0 k=0
à n n
!
X (−1)k X (−1)k−1
= (n − 1)! n + n +
k! (k − 1)!
k=1 k=1
n
X (−1)k
= n! + (n − 1)! (n − k)
k!
k=1
n−1
X ¶ µ
n−1 k
= n! + (−1) (n − k)!
k
k=1
n−1
X µ ¶
k n−1
= (−1) (n − k)! = Qn .
k
k=0
7 Rook Polynomials
Definition 7.1. Let C be a board. Each square of C is referred as a cell. Let rk (C) be the number of ways to
arrange k rooks on the board C so that no one can take another. We assume r0 (C) = 1. The rook polynomial of
C is
X∞
R(C, x) = rk (C)xk .
k=0
We refer an arrangement of k rooks on a board C as a k-rook arrangement on C.
Proposition 7.2. Let C be a board. For each cell σ of C, let Cσ denote the board obtained from C by deleting all
cells on the row and column that contains the cell σ, and let C − σ denote the board obtained from C by deleting the
cell σ. Then
rk (C) = rk (C − σ) + rk−1 (Cσ ).
Equivalently,
R(C, x) = R(C − σ, x) + xR(Cσ , x).
Proof. The k rook arrangements on the board C can be divided into two kinds: the rook arrangements that the
square σ is occupied and the rook arrangements that the square is not occupied, i.e., the k-rook arrangements on
the board C − σ and the (k − 1)-rook arrangements on the board Cσ . Thus rk (C) = rk (C − σ) + rk−1 (Cσ ).
10
Two boards C1 and C2 are said to be independent if they have no common rows and common columns.
Independent boards must be disjoint. If C1 and C2 are independent boards, we denote by C1 + C2 the board that
consists of the cells either in C1 or in C2 .
Proposition 7.3. Let C1 and C2 be independent boards. Then
k
X
rk (C1 + C2 ) = ri (C1 ) rk−i (C2 ).
i=0
Equivalently,
R(C1 + C2 , x) = R(C1 , x)R(C2 , x).
Proof. Since C1 and C2 have disjoint rows and columns, then each i-rook arrangement of C1 and each j-rook
arrangement of C2 will constitute a (i + j)-rook arrangement of C1 + C2 , and vice versa. Thus
X
rk (C1 + C2 ) = ri (C1 )rj (C2 ).
i+j=k
i,j≥0
¤¤
Example 7.1. Find the rook polynomial of the board ¤¤¤ . We use ¡ (a square with dot) to denote a selected
¤¤¤
square when applying the recurrence formula of rook polynomial.
µ ¶ µ ¶ ³ ´
¤¤ ¤¤
R ¤¤¤ , x = R ¤¤¡ , x + xR ¤¤ ¤¤¡ , x
¤¤¡ ¤¤
· µ ¶ ³ ´¸ h ³ ´ i
¤¤ ¤¡ ¤¤ , x + xR (¤¤ , x)
= R ¤¤ , x + xR ¤ , x + x R ¤¤
¡¤
½· µ ¶ ³ ´ ¸ h ³ ´ i¾
¤¤ ¤ ¤
= R ¤¤ , x + xR ¤ , x + x R ¤ , x + xR(∅, x)
¤
h ³ ´ i
+x R ¤¤ ¤¤ , x + xR (¤¤ , x)
nh i £ ¤o
= (1 + 4x + 2x2 )(1 + x) + x(1 + 2x) + x (1 + x)2 + x
h i
+x (1 + 4x + 2x2 ) + x(1 + 2x)
= 1 + 8x + 16x2 + 7x3 .
For a function f : S → R, we consider the value f (x) as the weight of f at x. The total weight of f is the sum
X
w(f ) := f (x).
x∈S
11
Clearly, for functions fi and constants ci (1 ≤ i ≤ n), we have
à n ! n
X X
w ci fi = ci w(fi ).
i=1 i=1
(2) 1Ā = 1S − 1A ,
Proof.
1Ā1 ∩Ā2 ∩···∩Ān = 1Ā1 1Ā2 · · · 1Ān = (1S − 1A1 )(1S − 1A2 ) · · · (1S − 1An )
X
= f1 f2 · · · fn (where fi = 1S or −1Ai , 1 ≤ i ≤ n)
X
= 1S · · · 1S + 1S · · · 1S (−1Ai1 ) · · · (−1Aik )
| {z } | {z }
i1 <···<ik
n 1≤k≤n n−k
n
X X
= 1S + (−1)k 1Ai1 ∩Ai2 ∩···∩Aik .
k=1 i1 <i2 <···<ik
Let w be a real-valued function on a set S. Then w can be extended to a function on the power set P(S) of S
by X
w(A) = w(x), A ⊆ S; w(∅) ≡ 0.
x∈A
Let S = {1, 2, . . . , n}. We introduce two functions α and β on the power set P(S) of S as follows: For I ⊆ S,
½ ¡T ¢
w i∈I Ai if I 6= ∅
α(I) =
0 if I = ∅,
½ ¡S ¢
w i∈I Ai if I 6= ∅
β(I) =
0 if I = ∅.
Theorem 8.2. Let α and β be functions defined above. Then
X
β(J) = (−1)|I|−1 α(I),
I⊆J
if and only if X
α(J) = (−1)|I|−1 β(I).
I⊆J
12
P P
Proof. Set f (I) = (−1)|I|−1 α(I) for I ⊆ S. Then β(J) = I⊆J (−1)|I|−1 α(I) is the same as β(J) = I⊆J f (I). By
the Möbius inversion, it is equivalent to X
f (J) = (−1)|J−I| β(I),
I⊆J
P |I|−1 β(I).
which is the same as α(J) = I⊆J (−1)
9 Möbius inversion
Let (X, ≤) be a locally finite poset, i.e., for each x ≤ y in X the interval [x, y] := {z ∈ X | x ≤ z ≤ y} is a finite
set. Let I(X) be the set of all functions f : X × X → R such that
f (x, y) = 0 if x 6≤ y;
such functions are called incidence functions on the poset X. When we give or define an incidence function f ,
we only give or define the values f (x, y) for the pairs (x, y) such that x ≤ y because f (x, y) = 0 for all pairs (x, y)
such that x 6≤ y.
The convolution product of two incidence functions f, g ∈ I(X) is a function f ∗ g : X × X → R, defined by
X
(f ∗ g)(x, y) := f (x, z)g(z, y).
z∈X
f ∗ (g ∗ h) = (f ∗ g) ∗ h,
For x 6≤ y, we automatically have (f ∗ (g ∗ h))(x, y) = ((f ∗ g) ∗ h))(x, y) = 0. The vector space I(X) together with
the convolution ∗ is called the incidence algebra of X.
Example 9.1. Let [n] = {1, 2, . . . , n} be the poset with the natrual order of natural numbers. An incidence function
f : [n] × [n] → R can be viewed as a upper triangular n × n matrix A = [aij ] given by aij = f (i, j). The convolution
is just the multiplication of upper triangular matrices.
There is a special function δ ∈ I(X), called the delta function of the poset (X, ≤), defined by
½
1 if x = y,
δ(x, y) :=
0 if x 6= y.
13
The delta function δ is the identity of the algebra I(X), i.e., for all f ∈ I(X),
δ ∗ f = f = f ∗ δ.
Indeed, for x ≤ y, X
(δ ∗ f )(x, y) = δ(x, z)f (z, y) = f (x, y);
x≤z≤y
X
(f ∗ δ)(x, y) = f (x, z)δ(z, y) = f (x, y).
x≤z≤y
Given an incidence function f ∈ I(X). A left inverse of f is a function g ∈ I(X) such that
g ∗ f = δ.
f ∗ h = δ.
g = g ∗ δ = g ∗ (f ∗ h) = (g ∗ f ) ∗ h = δ ∗ h = h.
If f has both a left and right inverse, we say that f is invertible; the left or right inverse of f must be unique and
is called the inverse of f .
The constant function of value 1 on Int(X) is known as the zeta function ζ of the poset (X, ≤), i.e.,
Let f ∈ I(X) and f (x, x) 6= 0 for all x ∈ X. We inductively define a function g ∈ I(X) by first letting
1
g(x, x) := for all x ∈ X;
f (x, x)
for x < y, when g(x, z) are defined for all z such that x ≤ z < y, we define
1 X
g(x, y) := − g(x, z)f (z, y).
f (y, y)
x≤z<y
This means that g is a left inverse function of f with respect to the convolution product ∗. Similarly, one can
show that f has a right inverse function h so that f ∗ h = δ. Since the associativity, we have
g = g ∗ δ = g ∗ (f ∗ h) = (g ∗ f ) ∗ h = δ ∗ h = h.
The left inverse and right inverse of f (if f (x, x) 6= 0 for all x ∈ X) are the same. So the left inverse function and
the right inverse function of f are just called the inverse function of f .
The inverse of the zeta function ζ in the incidence algebra I(X) is called the Möbius function of the poset
(X, ≤), denoted µ. The Möbius function µ can be defined as
14
Example 9.2. Let X = {1, 2, . . . , n}. The Möbius function of the poset (P(X), ⊆) is given by
This can be proved by induction on |B − A|. For |B − A| = 0, i.e., A = B, it is obviously true. Assume it is
true when |B − A| < p. Consider the case of |B − A| = p. In fact,
X
µ(A, B) = − µ(A, C)
A⊆C(B
X
= − (−1)|C|−|A|
A⊆C(B
p−1
X ³p´
= − (−1)k
k
k=0
= (−1) = (−1)|B−A| .
p
Example 9.3. Let X = {1, 2, . . . , n} and consider the linearly ordered set (X, ≤), where 1 < 2 < · · · < n. Then
for (k, l) ∈ X × X with k ≤ l, the Möbius function is given by
1 if l = k,
µ(k, l) = −1 if l = k + 1,
0 otherwise.
It is easy to see that µ(k, k) = 1 and µ(k, k + 1) = −1. It follows that µ(k, k + 2) = 0 and subsequently,
µ(k, k + i) = 0 for all i ≥ 2.
Theorem 9.1. Let (X, ≤) be a finite poset with a smallest element 0. Let f, g : X → R be real-valued functions
such that X
g(x) = f (z) for all x ∈ X.
z≤x
Then X
f (x) = g(z)µ(z, x) for all x ∈ X.
z:z≤x
Proof.
X XX
g(y)µ(y, x) = f (z)µ(y, x)
y:y≤x y≤x z≤y
X X
= µ(y, x) ζ(z, y)f (z)
y≤x z≤y
X X
= f (z) ζ(z, y)µ(y, x)
z∈x z≤y≤x
X
= f (z)δ(z, x)
z≤x
= f (x).
Corollary 9.2. Let [n] = {1, 2, . . . , n}. Let f, g : P([n]) → R be functions such that
X
g(I) = f (J), I ⊆ [n].
J⊆I
Then X
f (I) = (−1)|I|−|J| g(J), I ⊆ [n].
J⊆I
15
Permanent. Fix a positive integer n. Let Sn denote the symmetric group of [n] = {1, 2, . . . , n}, i.e., the set of all
permutations of [n]. Let A be an n × n real matrix. The permanent of A is defined as the number
n
X Y
per(A) := ai,σ(i) .
σ∈Sn i=1
For the chessboard C in Example 6.1, we associate a 0-1 matrix A = [aij ] as follows:
× × 0 0 1 1 1
× × 1 1 0 0 1
C= × × , A= 0 1 1 1 0 .
× × 1 0 0 1 1
× × 1 1 1 0 0
Then the number of ways to put 5 non-attacking indistinguishable rooks on C is the permanent per(A).
Fix an n-by-n matrix A. For each subset I ⊆ [n], let AI denote the submatrix of A, whose rows are those rows
of A indexed by I. Let F (I) be the set of all functions σ : [n] → I, G(I) the set of all surjective functions from [n]
onto I. Then G
F (I) = G(J).
J⊆I
Let P([n]) be the power set of [n]. We define a function f : P([n]) → R by f (∅) = 0 and
n
X Y
f (I) = ai,σ(i) , I ⊆ [n], I 6= ∅.
σ∈G(I) i=1
Then
n
X X Y n
X Y
g(I) = ai,σ(i) = ai,σ(i) , I ⊆ [n]. (6)
J⊆I σ∈G(J) i=1 σ∈F (I) i=1
In particular, X
f ([n]) = (−1)n−|I| g(I).
I⊆[n]
Note that by the second equality of (6), g(I) is the summation of a1,σ(1) · · · an,σ(n) over all functions σ : [n] → I.
Hence
X n
Y X
g(I) = a1,σ(1) · · · an,σ(n) = aij .
σ∈F (I) i=1 j∈I
It follows that
X n
Y X
F ([n]) = (−1)n−|I| aij = per(A).
I⊆[n] i=1 j∈I
However this formula is not much useful because there are 2n terms in the summation.
Definition 9.3. Let (Xi , ≤i ) (i = 1, 2) be two posets. The product poset (X1 × X2 , ≤) is given by
16
Theorem 9.4. Let µi be the Möbius functions of posets (Xi , ≤i ), i = 1, 2. Then the Möbius function µ of X1 × X2
for (x1 , x2 ) ≤ (y1 , y2 ) is given by
µ((x1 , x2 ), (y1 , y2 )) = µ1 (x1 , y1 ) µ2 (x2 , y2 ).
Proof. We prove it by induction on the length `((x1 , x2 ), (y1 , y2 )), the length of the longest chains in the interval
[(x1 , x2 ), (y1 , y2 )]. It is obviously true when ` = 0. For ` ≥ 1, we have
X
µ((x1 , x2 ), (y1 , y2 )) = − µ((x1 , x2 ), (z1 , z2 ))
(x1 ,x2 )≤(z1 ,z2 )<(y1 ,y2 )
X
= − µ1 (x1 , z1 ) µ2 (x2 , z2 ) (by induction)
(x1 ,x2 )≤(z1 ,z2 )<(y1 ,y2 )
X X
= µ1 (x1 , y1 ) µ2 (x2 , y2 ) − µ1 (x1 , z1 ) µ2 (x2 , z2 )
x1 ≤z1 ≤y1 x2 ≤z2 ≤y2
= µ1 (x1 , y1 ) µ2 (x2 , y2 ) − δ1 (x1 , y1 ) δ2 (x2 , y2 )
= µ1 (x1 , y1 ) µ2 (x2 , y2 ).
Example 9.4. Let n be a positive integer and Z+ = {1, 2, . . .}. Then Z+ is a poset whose partial ordering is
divisibility. Let n ∈ Z+ be factored as
n = pe11 pe22 · · · pekk ,
where pi are distinct prime numbers and ei are positive integers. Since µ(m, m) = 1 for all m ∈ Z+ and µ(1, n) is
inductively given by X
µ(1, n) = − µ(1, m)
m∈Z+ , m|n, m6=n
We only need to to consider the subposet (D(n), divisibility), where D(n) = {d ∈ [n] : d|n}. For r, s ∈ D(n), write
r = pa11 pa22 · · · pakk , s = pb11 pb22 · · · pbkk ,
where 0 ≤ ai , bi ≤ ei . Then r|s if and only if ai ≤ bi . This means that the poset D(n) is isomorphic to the product
poset
k
© ª Y
Q := (a1 , . . . , ak ) | ai ∈ [0, ei ] = [0, ei ],
i=1
where [0, ei ] = {0, 1, . . . , ei }. Thus µ(1, n) = µQ ((0, . . . , 0), (e1 , . . . , ek )), where
k
Y
µQ ((0, . . . , 0), (e1 , . . . , ek )) = µ[0,ei ] (0, ei ).
i=1
Note that
1 if ei = 0, ½
(−1)ei if ei ≤ 1,
µ[0,ei ] (0, ei ) = −1 if ei = 1, =
0 if ei ≥ 2.
0 if ei ≥ 2.
It follows that
½
(−1)e1 +···+ek if all ei ≤ 1,
µ(1, n) =
0 otherwise.
1 if n = 1,
= (−1)j if n is a product of j distinct primes,
0 otherwise.
Now for arbitrary m, n ∈ Z+ such that m|n,¡ the ¢ subposet {z ∈ Z+ : m|z, z|n} is isomorphic to the the subposet
n n
{z ∈ Z+ : z| m }. We then have µ(m, n) = µ 1, m . In number theory, we usually write
µ(n) := µ(1, n).
17
Theorem 9.5. Let f, g : Z+ → R be functions such that
X
g(n) = f (k) for all n ∈ Z+ .
k|n
Then X ³n´
f (n) = µ g(k) for all n ∈ Z+ .
k
k|n
Example 9.5. Let Φn := {k ∈ Z ∩ [1, n] | gcd(k, n) = 1}. Then φ(n) = |Φn |. Let
X
g(n) := φ(d) for all n ∈ Z+ .
d|n
Set Φdn := {k ∈ [1, n] : gcd(k, n) = d}. There is bijection Φdn → Φ1n/d , k 7→ k/d, where k ∈ Φdn . Then φ(n/d) = |Φdn |.
Note that for each integer k ∈ [1, n], there is an unique integer d ∈ [1, n] such that gcd(k, n) = d, and of course d|n.
Thus X X
n= φ(n/d) = φ(k).
d|n k|n
Note that µ(d) = 1 if and only if d = 1; µ(d) = (−1)j if d is a product of j distinct primes; and µ(d) = 0 otherwise.
Let the distinct primes dividing n be p1 , p2 , . . . , pr . Then
( )
n o Y
d ∈ [1, n] : d|n, µ(d) 6= 0 = x= a : I ⊆ {1, 2, . . . , r}
a∈I
n o
= 1, pi , pj pk , . . . | 1 ≤ i ≤ r, 1 ≤ j < k ≤ r, . . . .
We thus have
µ ¶ µ ¶
n n n n
φ(n) = n − + + ··· + + + ··· − ···
p1 p2 p1 p2 p 1 p 3
n
+ · · · + (−1)r
p1 p2 · · · pr
Yr µ ¶ Y µ ¶
1 1
= n 1− =n 1− .
pi p
i=1 primes p|n
with period n, i.e., xi+n = xi for all i ∈ Z. The minimal period of a circular permutation (xi ) of M is the smallest
positive integer d such that for all i ∈ Z,
xi+d = xi .
Let Ln (M ) be the set of all n-permutations of M , and Cn (M ) the set of all circular n-permutations of M . Then
Ln (M ) is just the set of all words of length n over the set S. Consider the map
σ : Ln (M ) → Ln (M ), σ(x1 x2 · · · xn ) = x2 · · · xn x1 .
A word w of length n is said to be primitive if the words w, σ(w), . . . , σ n−1 (w) are distinct. A period of an n-word
w is a positive integer m such that σ m (w) = w; the very smallest number of all periods of w is called the minimal
18
period of w. Every n-word has trivial period n. An n-word is primitive if and only if its minimal period is n. It
is clear that the minimal period d of a word w is a factor of any period m of w. In fact, write m = qd + r, where
0 ≤ r ≤ d − 1. Suppose r ≥ 1. Then
σ r (w) = σ r σ d
· · σ }d (w) = σ qd+r (w) = σ m (w) = w.
| ·{z
q
Let b = d/a, that is, d = ab. Then d|n is equivalent to b|(n/a). Thus
X X µ(b)
|Cn (M )| = |La (M )| .
ab
a|n b|(n/a)
P n P µ(b) 1 P n/a 1
¡n¢
Since φ(n) = d|n d µ(d), then b|(n/a) ab = n b|(n/a) b µ(b) = n φ a . We finally have
1X ³n´
|Cn (M )| = |La (M )| φ (since |La (M )| = k a |)
n a
a|n
1 X a ³n´
= k φ (set d = n/a)
n a
a|n
1 X n/d
= k φ(d).
n
d|n
Example 9.7. Let M = {n1 · a1 , . . . , nk · ak } be a multiset of type (n1 , . . . , nk ) such that n = n1 + · · · + nk . Set
m = gcd(n1 , . . . , nk ), Md := {(dn1 /m) · a1 , . . . , (dnk /m) · ak }. Let L(Md ) denote the set of all permutations of Md ,
L0a (Md ) the set of all permutations
F of Md with minimal period a, and L0 (Md ) the set of all primitive permutations
of Md . Then L(Md ) = a|d L0a (Md ) and |L0a (Md )| = |L0 (Ma )|. We have
X X µ ¶
0 0 d
|L(Md )| = |L (Ma )|, i.e., |L (Md )| = |L(Ma )| µ .
a
a|d a|d
19
Analogously, let C(Md ) denote the set of all circular permutations of Md , Ca0 (Md ) the set of all circular permutations
of Md with minimal period a, and C 0 (Md ) the set of all primitive circular permutations of Md . Then C(Md ) =
F 0 0 0
a|d Ca (Md ) and |Ca (Md )| = |C (Ma )|. We have
X X m
|C(Md )| = |C 0 (Ma )| = |L0 (Ma )| ·
an
a|d a|d
X m X ³a´
= |L(Mb )| µ (set c = ab , then a = bc, c| db )
an b
a|d b|a
1Xm X d/b
= |L(Mb )| µ(c)
n d d
c
b|d c| b
µ ¶
1Xm d
= |L(Mb )| φ (set a = db , i.e., b = ad )
n d b
b|d
1Xm
= |L(Md/a )| φ(a).
n d
a|d
³ ´
bn/m
Note that |L(Mb )| = bn1 /m,...,bnk /m
. Let d = m. We then have
1X
|C(Mm )| = φ(a) |L(Mm/a )|
n
a|m
µ ¶
1X n/a
= φ(a) .
n n1 /a, . . . , nk /a
a|m
For instance, M = {12a1 , 24a2 , 18a3 }. Then gcd(12, 24, 18) = 6. Note that φ(1) = 1, φ(2) = 1, φ(3) = 2,
φ(4) = 2, φ(5) = 4, φ(6) = 2. Thus the number of circular permutations of M is
· µ ¶ µ ¶ µ ¶ µ ¶¸
1 54 27 18 9
φ(1) + φ(2) + φ(3) + φ(6)
54 12, 24, 18 6, 12, 9 4, 8, 6 2, 4, 3
20
Homework 3
Proof.
¡n¢ Let S be a set of n elements, and let a, b, c be distinct
¡ n−3 ¢ elements of S. The number of k-subsets of S is
k , and the number of k-subsets of S − {a, b, c} is k . Then the LHS is the number of k-subsets of S that
contains at least of the elements of {a, b, c}. Such k-subsets can be divided into 3 types: (1) the k-subsets
that contain the element a; (2) the k-subsets that do not contain a but contain b; and (3) the k-subsets that
do not contain a, b but contain c. The numbers k-subsets of type (1), type (2), type (3) are
µ ¶ µ ¶ µ ¶
n−1 n−2 n−3
, ,
k−1 k−1 k−1
X ³n´ µn¶ n
X ³ n ´2
j
(−1) = (−1)k
i j k
i+j=n k=0
There are only ¡even¢ terms in the expansion. Thus the coefficient of xn is zero if n is odd; and the coefficient
of xn is (−1)m 2mm if n = 2m is even.
1
3. Prove that for all real numbers α and all integers k and n,
µ ¶µ ¶ µ ¶µ ¶
α n α α−k
= .
n k k n−k
¡n¢ ³ ´
α−k
Proof. For n < k, the LHS is zero because k = 0. The RHS is also zero because n−k = 0 by definition.
For n ≥ k, we divide the situation into the following cases:
If k ≥ 1, then
α(α − 1) · · · (α − n + 1) n!
LHS = ·
n! k!(n − k)!
α(α − 1) · · · (α − k + 1) (α − k)(α − k − 1) · · · (α − n + 1)
= ·
k! (n − k)!
= RHS.
¡α¢ ¡n¢ ¡α¢
If k = 0, then both LHS and RHS are both equal to n because k = k = 1 by definition.
¡n¢ ¡α¢
If k ≤ −1, then both LHS and RHS are both equal to zero because k = k = 0 by definition.
4. In a partition of the power set P (S) of S = {1, 2, . . . , n} into symmetric chains, find a formula for the number
of chains of size 1, size 2, and size k, respectively.
Solution. We claim that the number of symmetric chains of size larger than k is
µ ¶
n
.
d(n + k)/2e
n+k n−k
− = k,
2 2
¥ ¦ § n+k ¨
then any symmetric chain that contains one n−k 2 -subset and one 2 -subset must contain at leat k + 1
subsets. We thus conclude that the number of symmetric chains of size larger than k is
µ ¶ µ ¶
n n
= .
d(n + k)/2e b(n − k)/2c
2
5. Assume the expansion formula
X ∞
1
= zk , |z| < 1.
1−z
k=0
X ∞ µ ¶
1 n+k−1
= zk , |z| < 1.
(1 − z)n k
k=0
³ ´ ³ ´
n+k−1 k
Proof. For n = 1, it is obviously true because k = k = 1. For n ≥ 2, suppose
X ∞ µ ¶
1 n−1+k−1
= zk , |z| < 1.
(1 − z)n−1 k
k=0
Then
1 1 1
= ·
(1 − z)n 1 − z (1 − z)n−1
à ∞ ! ∞ µ
X X n − 1 + j − 1¶
= zi zj
j
i=0 j=0
∞
X X µ ¶
n+j−2 k
= z .
j
k=0i+j=k
i≥0,j≥0
We thus have
X µn + j − 2¶ Xk µ
n+j−2
¶ X k µ
n−2+j
¶
= =
j j n−2
i+j=k j=0 j=0
µ ¶ µ ¶ µ ¶
n−2 n−1 n−2+k
= + + ··· +
n−2 n−2 n−2
µ ¶ µ ¶
n−1+k n+k−1
= = .
n−1 k
6. Consider the partially ordered set {1, 2, . . . , 12} whose partial order is the divisibility.
(a) Determine a chain of largest size, and a partition of {1, 2, . . . , 12} into the smallest number of antichains.
(b) Determine an antichain of largest size, and a partition of {1, 2, . . . , 12} into the smallest number of chains.
(a) An antichain partition with four antichains: {1}, {2, 3, 5, 7, 11}, {4, 6, 10}, {8, 9, 12}.
There is one chain of length four: {1, 2, 4, 8}.
(b) A chain partition with six chains: {1, 2, 4, 8}, {3, 6, 12}, {5, 10}, {7}, {9}, {11}.
There are several antichains of largest size. For instance, {2, 6, 5, 7, 9, 11}, {4, 6, 5, 7, 9, 11}, {4, 6, 7, 9, 11, 10}.
3
7. Determine the number of 12-combinations of the multiset {4a, 3b, 4c, 5d}.
Solution. Let S be the set of permutations of the multiset M = {∞a, ∞b, ∞c, ∞d}. A1 , A2 , A3 , A4 be the
sets of permutations of M such that the number of a’s are more than 4, the number of b’s are more than 3,
the number of c’s are more than 4, and the number of d’s are more than 5, respectively. Then
¿ À µ ¶ µ ¶
4 4 + 16 − 1 19
|S| = = = ;
16 16 16
¿ À µ ¶ µ ¶
4 4 + 11 − 1 14
|A1 | = |A3 | = = = ,
11 11 11
¿ À µ ¶ µ ¶
4 4 + 12 − 1 15
|A2 | = = = ,
12 12 12
¿ À µ ¶ µ ¶
4 4 + 10 − 1 13
|A4 | = = = ;
10 10 10
¿ À µ ¶ µ ¶
4 4+7−1 10
|A1 ∩ A2 | = |A2 ∩ A3 | = = = ,
7 7 7
¿ À µ ¶ µ ¶
4 4+5−1 8
|A1 ∩ A4 | = |A3 ∩ A4 | = = = ,
5 5 5
¿ À µ ¶ µ ¶
4 4+6−1 9
|A1 ∩ A3 | = |A2 ∩ A4 | = = = ;
6 6 6
¿ À µ ¶ µ ¶
4 4+2−1 5
|A1 ∩ A2 ∩ A3 | = = = = 10,
2 2 2
¿ À
4
|A1 ∩ A2 ∩ A4 | = |A2 ∩ A3 ∩ A4 | = = 4,
1
¿ À
4
|A1 ∩ A3 ∩ A4 | = = 1;
0
|A1 ∩ A2 ∩ A3 ∩ A4 | = 0.
By the inclusion-exclusion formula, the answer is given by
µ ¶ · µ ¶ µ ¶ µ ¶¸ ·µ ¶ µ ¶ µ ¶¸
19 14 15 13 10 8 9
− 2 + + +2 + + − (10 + 2 · 4 + 1) + 0.
16 11 12 10 7 5 6
8. Determine the number of permutations of {1, 2, . . . , 8} in which no even integer is in its natural position.
Solution. Let S be the set of all permutations of {1, 2, . . . , 8}. The even integers in {1, 2, . . . , 8} are 2,4,6,8.
Let A1 , A2 , A3 , A4 be the sets of permutations that 2,4,6,8 are fixed respectively. Then
|S| = 8!,
8! − 4 × 7! + 6 × 6! − 4 × 5! + 4!.
4
9. Using combinatorial reasoning to prove the identity
n ³ ´
X n ³ ´
X
n n
n! = Dn−k = Dk .
k k
k=0 k=0
Proof. Let S be the set of all permutations of {1, 2, . . . , n}. Let ¡Ak¢ be the set of all permutations that k
n
integers are fixed at
Sntheir positions. Then |S| = n! and |Ak | = k Dn−k . The identity follows from the
disjoint union S = k=0 Ak .
10. What is the number of ways to place six non-attacking rooks on the 6-by-6 boards with forbidden positions
as shown?
(a)
× ×
× ×
× ×
(b)
× ×
× ×
× ×
× ×
× ×
× ×
(c)
× ×
× ×
×
× ×
×
Recall that the number Rn (C) of ways to place n non-attacking rooks on the n-by-n board C with forbidden
positions is given by
X n
Rn (C) = (−1)k rk (C)(n − k)!,
k=0
where rk (C) is the number of ways to place k non-attacking rooks on the board C. In all three cases, n = 6.
(a) Since r0 = 1, r1 = 6, r2 = 3 × 2 × 2 = 12, r3 = 2 × 2 × 2 = 8, r4 = r5 = r6 = 0, then
R6 (C) = 6! − 6 × 5! + 12 × 4! − 8 × 3!.
5
(c) Since the rook polynomial
¡ ¢¡ ¢
R(C, x) = 1 + 5x + 6x2 + x3 1 + 3x + x2 = 1 + 8x + 22x2 + 24x3 + 9x4 + x5 ,
R6 (C) = 6! − 8 × 5! + 22 × 4! − 24 × 3! + 9 × 2! − 1!.
so that the elements of the same type are not all consecutively together?
Solution. Let S be the set of all circular permutations of M = {2a, 3b, 4c, 5d}. Then
13!
|S| = .
2!3!4!5!
Let A1 , A2 , A3 , and A4 be the sets of circular permutations that the type a, the type b, the type c, and the
type d elements are consecutively together respectively. Then
12! 11! 10! 9!
|A1 | = , |A2 | = , |A3 | = , |A4 | = ;
3!4!5! 2!4!5! 2!3!5! 2!3!4!
10! 9! 8!
|A1 ∩ A2 | = , |A1 ∩ A3 | = , |A1 ∩ A4 | = ,
4!5! 3!5! 3!4!
8! 7! 6!
|A2 ∩ A3 | = , |A2 ∩ A4 | = , |A3 ∩ A4 | = ;
2!5! 2!4! 2!3!
7! 6! 5! 4!
|A1 ∩ A2 ∩ A3 | = , |A1 ∩ A2 ∩ A4 | = , |A1 ∩ A3 ∩ A4 | = , |A2 ∩ A3 ∩ A4 | = ;
5! 4! 3! 2!
|A1 ∩ A2 ∩ A3 ∩ A4 | = 3!.
Thus the answer is given by
µ ¶
13! 12! 11! 10! 9!
−+ + +
2!3!4!5!
3!4!5! 2!4!5! 2!3!5! 2!3!4!
µ ¶ µ ¶
10! 9! 8! 8! 7! 6! 7! 6! 5! 4!
+ + + + + + − + + + + 3!.
4!5! 3!5! 3!4! 2!5! 2!4! 2!3! 5! 4! 3! 2!
6
Recurrence Relations and Generating Functions
a0 , a1 , a2 , . . . , an , . . .
of countably many real or complex numbers, and is usually abbreviated as (an ; n ≥ 0) or just (an ). A sequence (an )
can be viewed as a function f from the set of nonnegative integers to the set of real or complex numbers, i.e.,
f (n) = an , n = 0, 1, 2, . . .
an = an−1 + q, n ≥ 1.
a0 , a0 q, a0 q 2 , ..., a0 q n , ...
an = qan−1 , n ≥ 1.
s0 = a0 ,
s1 = a0 + a1 ,
s2 = a0 + a1 + a2 ,
..
.
sn = a0 + a1 + · · · + an ,
..
.
1
Example 1.1. Determine the number an of regions which are created by n mutually overlapping circles in general
position on the plane. (By mutually overlapping we mean that each pair of two circles intersect in two distinct
points; thus non-intersecting or tangent circles are not allowed. By general position we mean that there are no
three circles through a common point.)
a0 = 1, a1 = 2, a2 = 4, a3 = 8.
It seems that we might have a4 = 16. However, by try-and-error we quickly see that a4 = 14.
Assume that there are n circles in general position on a plane. When we take one circle away, say the nth circle,
there are n − 1 circles in general position on the same plane. By induction hypothesis the n − 1 circles divide the
plane into an−1 regions. Note that the nth circle intersects each of the n − 1 circles in 2(n − 1) distinct points, say
the 2(n − 1) points on the nth circle are ordered as P1 , P2 , . . . , P2(n−1) . Then each of the 2(n − 1) arcs
intersects one and only one region in the case n − 1 circles and separate the region into two regions. Then there are
2(n − 1) more regions produced when the nth circle is drawn. We thus obtain the recurrence relation
an = an−1 + 2(n − 1)
= an−2 + 2(n − 1) + 2(n − 2)
= an−3 + 2(n − 1) + 2(n − 2) + 2(n − 3)
..
.
= a1 + 2(n − 1) + 2(n − 2) + 2(n − 3) + · · · + 2
(n − 1)n
= a1 + 2 · = 2 + n(n − 1)
2
= n2 − n + 2, n ≥ 2.
This formula is also valid for n = 1 (since a1 = 2), although it doesn’t hold for n = 0 (since a0 = 1).
Example 1.2 (Fibonacci Sequence). A pair of newly born rabbits of opposite sexes is placed in an enclosure at the
beginning of a year. Baby rabbits need one moth to grow mature; they become an adult pair on the first day of the
second month. Beginning with the second month the female is pregnant, and gives exactly one birth of one pair of
rabbits of opposite sexes on the first day of the third month, and gives exactly one such birth on the first day of
each next month. Each new pair also gives such birth to a pair of rabbits on the first day of each month starting
from the third month. Find the number of pairs of rabbits in the enclosure after one year?
Let fn denote the number of pairs of rabbits on the first day of the nth month. Some of these pairs are adult
and some are babies. We denote by an the number of pairs of adult rabbits and denote by bn the number of pairs
of baby rabbits on the day of the nth month. Then the total number of pairs of rabbits on the first day of the nth
month is fn = an + bn , n ≥ 1.
n 1 2 3 4 5 6 7 8 9 10 11 12 13
an 0 1 1 2 3 5 8 13 21 34 55 89 144
bn 1 0 1 1 2 3 5 8 13 21 34 55 89
fn 1 1 2 3 5 8 13 21 34 55 89 144 233
If a pair is adult on the first day of the nth month, then it gives one birth of one pair on the fist day of the next
month. So bn+1 = an , n ≥ 1. Note that each adult pair on the first day of the nth month is still an adult pair on
2
first day of the next month and each baby pair on the first day of the nth month becomes an adult pair on the first
day of the next month, we have an+1 = an + bn = fn , n ≥ 1. Thus
is called the Fibonacci sequence, and the terms in the sequence are called Fibonacci numbers.
sn = f0 + f1 + f2 + · · · + fn = fn+2 − 1. (2)
This can be verified by induction on n. For n = 0, we have s0 = f2 − 1 = 0. Now for n ≥ 1, we assume that it
is true for n − 1, i.e., sn−1 = fn+1 − 1. Then
sn = f0 + f1 + · · · + fn
= sn−1 + fn
= fn+1 − 1 + fn (by the induction hypothesis)
= fn+2 − 1. (by the Fibonacci recurrence)
Note that f1 = f2 = 1 is odd and f3 = 2 is even. Assume that f3k is even, f3k−2 and f3k−1 are odd. Then
f3k+1 = f3k + f3k−1 is odd (even + odd = odd), and subsequently, f3k+2 = f3k+1 + f3k is also odd (odd + even = odd).
It follows that f3(k+1) = f3k+2 + f3k+1 is even (odd + odd = even).
Theorem 1.1. The general term of the Fibonacci sequence (fn ) is given by
à √ !n à √ !n
1 1+ 5 1 1− 5
fn = √ −√ , n ≥ 0. (3)
5 2 5 2
Example 1.5. Determine the number hn of ways to perfectly cover a 2-by-n board with dominoes. (Symmetries
are not counted in counting the number of coverings.)
We assume h0 = 1 since a 2-by-0 board is empty and it has exactly one perfect cover, namely, the empty cover.
Note that the first few terms can be easily obtained such as
h0 = 1, h1 = 1, h2 = 2, h3 = 3, h4 = 5.
Now for n ≥ 3, the 2-by-n board can be covered by dominoes in two types:
1 2 n−1 n 1 2 n−2 n
There are hn−1 ways in the first type and hn−2 ways in the second type. Thus
hn = hn−1 + hn−2 , n ≥ 2.
Therefore the sequence (hn ; n ≥ 0) is the Fibonacci sequence (fn ; n ≥ 0) with f0 = 0 deleted, i.e.,
hn = fn+1 , n ≥ 0.
3
Example 1.6. Determine the number bn of ways to perfectly cover a 1-by-n board by dominoes and monominoes.
bn = bn−1 + bn−2 , b0 = b1 = 1, b2 = 2.
bX2 cµ
n−1
¶
n−k−1
fn = , n ≥ 0.
k
k=0
where the coefficients α1 (n), α2 (n), . . ., αk (n) and βn are functions of n. The linear recurrence relation (4) is said
to be homogeneous if βn = 0 for all n ≥ k, and is said to have constant coefficients if α1 (n), α2 (n), . . ., αk (n)
are constants. The recurrence relation
4
A solution of the linear recurrence relation (4) is any sequence (an ) which satisfies (4). The general solution
of (4) is a solution
xn = an (c1 , c2 , . . . , ck ) (6)
with some parameters c1 , c2 , . . . , ck , such that for arbitrary initial values x0 , x1 , . . . , xk−1 there are constants c1 , c2 , . . . , ck
so that (6) is the unique sequence which satisfies both the recurrence relation (4) and the initial conditions.
Let S∞ denote the set of all sequences (an ; n ≥ 0). It is clear that S∞ becomes an infinite-dimensional vector
space under the ordinary addition and scalar multiplication of sequences. Let Nk be the set all solutions of the
nonhomogeneous linear recurrence relation (4), and Hk the set of all solutions of the homogeneous linear recurrence
relation (5). We shall see that Hk is a k-dimensional subspace of the vector space S∞ , and Nk is a k-dimensional
affine subspace of S∞ .
Theorem 2.2 (Structure Theorem for Linear Recurrence Relations). (a) The solution space Hk is a k-dimensional
subspace of the vector space S∞ of sequences. Thus, if (an,1 ), (an,2 ), . . ., (an,k ) are linearly independent solutions
of the homogeneous linear recurrence relation (5), then the general solution of (5) is
Proof. (a) To show that Hk is a vector subspace of S∞ , we need to show that Hk is closed under the addition and
scalar multiplication of sequences. Let (an ) and (bn ) be solutions of (5). Then
This means that Hk is closed under the addition and scalar multiplication of sequences.
To show that Hk is k-dimensional, consider the projection π : S∞ −→ Rk defined by
We shall see that the restriction of π to Hk is a linear isomorphism. For any (a0 , a1 , . . . , ak−1 ) ∈ Rk , define an as
Obviously, we have π(a0 , a1 , a2 , . . .) = (a0 , a1 , . . . , ak−1 ). This means that the restriction π|Hk is surjective. Now for
any sequence (xn ) ∈ Hk , if π(x0 , x1 , x2 , . . .) = (0, 0, . . . , 0), then x0 = x1 = · · · = xk−1 = 0. Applying the recurrence
relation (5) for n = k, we have xk = 0; applying (5) again for n = k + 1, we obtain xk+1 = 0. Continuing to apply
(5), we have xn = 0 for n ≥ k. Thus (xn ) is the zero sequence. This means that π is injective. We have finished the
proof that π|Hk is a linear isomorphism from Hk onto Rk .
(b) For any solution (bn ) of (4), we claim that the sequence hn := bn − an (n ≥ 0) is a solution of (5). So
bn = an + hn , n ≥ 0.
5
In fact, since (an ) and (bn ) are solutions of (4), applying the recurrence relation (4), we have
hn = [α1 (n)bn−1 + α2 (n)bn−2 + · · · + αk (n)bn−k + βn ]
−[α1 (n)an−1 + α2 (n)an−2 + · · · + αk (n)an−k + βn ]
= α1 (n)(bn−1 − an−1 ) + α2 (n)(bn−2 − an−2 ) + · · · + αk (n)(bn−k − an−k )
= α1 (n)hn−1 + α2 (n)hn−2 + · · · + αk (n)hn−k , n ≥ k.
This means that (hn ) is a solution of (5). Conversely, for any solution (hn ) of (5), we have
an + hn = [α1 (n)an−1 + α2 (n)an−2 + · · · + αk (n)an−k + βn ]
+[α1 (n)hn−1 + α2 (n)hn−2 + · · · + αk (n)hn−k ]
= α1 (n)(an−1 + hn−1 ) + α2 (n)(an−2 + hn−2 ) + · · · + αk (n)(an−k + hn−k ) + βn
for n ≥ k. This means that the sequence (an + hn ) is a solution of (4).
Definition 2.3. The Wronskian Wk (n) of k solutions (an,1 ), (an,2 ), . . ., (an,k ) of the homogeneous linear recurrence
relation (5) is the determinant
an,1 an,2 · · · an,k
an+1,1 an+1,2 · · · an+1,k
Wk (n) = det . . .. , n ≥ 0.
. . .
. .
an+k−1,1 an+k−1,2 · · · an+j−1,k
The Wronskian of (an,1 ), (an,2 ), . . ., (an,k ) is also an infinite sequence (Wk (n); n ≥ 0).
Theorem 2.4. The solutions (an,1 ), (an,2 ), . . ., (an,k ) of the homogeneous linear recurrence relation (5) are linearly
independent if and only if there is a nonnegative integer n0 such that the Wronskian
Wk (n0 ) 6= 0.
In other words, the solutions (an,1 ), (an,2 ), . . ., (an,k ) are linearly dependent if and only if Wk (n) = 0 for all n ≥ 0.
Proof. We show that the sequences (an,1 ), (an,2 ), . . ., (an,k ) are linearly dependent if and only if Wk (n) = 0 for all
n ≥ 0. If (an,1 ), (an,2 ), . . ., (an,k ) are linearly dependent, then for any n ≥ 0 the columns of the matrix
an,1 an,2 · · · an,k
an+1,1 an+1,2 · · · an+1,k
.. .. ..
. . .
an+k−1,1 an+k−1,2 · · · an+j−1,k
are linearly dependent because the columns are part of the sequences (an,1 ), (an,2 ), . . ., (an,k ) respectively. It follows
from linear algebra that the determinant of the matrix is zero, i.e., Wronskian Wk (n) = 0 for all n ≥ 0.
Conversely, if Wk (n) = 0 for all n ≥ 0, in particular, Wk (0) = 0, then there are constants c1 , c2 , . . . , ck , not all
zero, such that
c1 ai,1 + c2 ai,2 + · · · + ck ai,k = 0 for 0 ≤ i ≤ k − 1.
Thus, applying the recurrence relation (5) for the sequences (an,1 ), (an,2 ), . . ., (an,k ) respectively for n = k, we have
k
X k
X k
X
cj ak,j = cj αi (k)ak−i,j
j=1 j=1 i=1
k
X k
X
= αi (k) cj ak−i,j = 0.
i=1 j=1
Continuing to apply the recurrence relation (5) for n ≥ k + 1, we conclude that for the same constants c1 , c2 , . . . , ck ,
c1 an,1 + c2 an,2 + · · · + ck an,k = 0, n ≥ k + 1.
This means that the sequences (an,1 ), (an,2 ), . . ., (an,k ) are linearly dependent.
6
3 Homogeneous linear recurrence relations with constant coefficients
In this section we only consider linear recurrence relations of the form
where α1 , α2 , . . ., αk are constants. We call this kinds of recurrence relations as homogeneous linear recurrence
relations of order k with constant coefficients. Sometimes it is convenient to write (7) as of the form
is called the characteristic equation associated with the recurrence relation (8), and the polynomial on the left
side of (9) is called the characteristic polynomial.
Example 3.1. The Fibonacci sequence (fn ; n ≥ 0) satisfies the linear recurrence relation
Example 3.2. The geometric sequence (xn ; n ≥ 0), where xn = q n , satisfies the linear recurrence relation
xn = qxn−1 , n≥1
It is quite heuristic that solutions of the first order homogeneous linear recurrence relations are geometric
sequences. This hints that the recurrence relation (7) may have solutions of the form xn = q n . The following
theorem confirms the speculation.
xn = q n
is a solution of the kth order homogeneous linear recurrence relation (8) with constant coefficients if and only if the
number q is a root of the characteristic equation (9).
(b) If the characteristic equation (9) has k distinct roots q1 , q2 , . . ., qk , then the general solution of (8) is
This means that (11) and (12) are equivalent. This finishes the proof of Part (a).
(b) Since q1 , q2 , . . . , qk are roots of the characteristic equation (9), xn = qin are solutions of the homogeneous
linear recurrence relation (8) for all i (1 ≤ i ≤ k). Since the solution space of (8) is a vector space, the linear
combination
xn = c1 q1n + c2 q2n + · · · + cn qkn , n ≥ 0
7
are also solutions (8). Now given arbitrary values for x0 , x1 , . . . , xk−1 , the sequence (xn ) is uniquely determined by
the recurrence relation (8). Set
and Ai is the matrix obtained from A by replacing its ith column by the column [x0 , x1 , . . . , xk−1 ]T . The determinant
of A is given by Y
det A = (qj − qi ) 6= 0.
1≤i<j≤k
Example 3.3. Find the sequence (xn ) satisfying the recurrence relation
x3 − 2x2 − x + 2 = 0.
xn = c1 (−1)n + c2 + c3 2n .
xn = q n , nq n , ..., nm−1 q n
8
(b) Let q1 , q2 , . . . , qs be distinct roots with the multiplicities m1 , m2 , . . . , ms respectively for the characteristic
equation (9). Then the sequences
are linearly independent solutions of the homogeneous linear recurrence relation (8). Their linear combinations form
the general solution of the recurrence relation (8).
Proof. The falling factorial polynomial of degree k is (x)k := x(x − 1) · · · (x − k + 1). Let q be a root of the
characteristic polynomial P (t) with multiplicity m. Then q is a root of the (m − 1)th derivative P (m−1) (t). We
claim that xn = (n)i q n , where 0 ≤ i ≤ m − 1, is solution the recurrence relation. In fact,
Set c0 q n + c1 nq n + · · · + cm−1 nm−1 q n = 0 for all n. Since q 6= 0, we have c0 + c1 n + · · · + cm−1 nm−1 = 0 for
all n. Consider c0 , c1 , . . . , cm−1 as variables and let n = 1, 2, . . . , m; we have a system of linear equations about
c0 , c1 , . . . , cm−1 . The coefficient matrix
1 1 1 2 · · · 1m
1 2 2 2 · · · 2m
2 · · · 3m
A= 1 3 3
.. .. .. ..
. . . .
1 m m2 · · · mm
Q
and det A = 1≤i<j≤m (j − i) 6= 0. Hence c0 = c1 = · · · = cm−1 = 0.
Now set
(a1 q1n + a2 nq1n + · · · + am1 −1 nm1 −1 q1n ) + · · · + (c1 qsn + c2 nqsn + · · · + cms −1 nms −1 qsn ) = 0.
Then
(a1 + a2 n + · · · + am1 −1 nm1 −1 )q1n + · · · + (c1 + c2 n + · · · + cms −1 nms −1 )qsn = 0.
Let u1 = a1 q1n +a2 nq1n +· · ·+am1 −1 nm1 −1 q1n , . . ., us = c1 qsn +c2 nqsn +· · ·+cms −1 nms −1 qsn . Then u1 +u2 +· · ·+us =
0.
In particular, when n = 0, we obtain c0 = 0. Thus for all n we have
xn = αxn−1 + βn , n ≥ 1. (13)
(a) Let βn = cq n be an exponential function of n. Then (13) has a particular solution of the following form.
• If q 6= α, then xn = Aq n .
• If q = α, then xn = Anq n .
9
Pk i
(b) Let βn = i=0 bi n be a polynomial function of n with degree k.
• If α 6= 1, then (13) has a particular solution of the form
xn = A0 + A1 n + A2 n2 + · · · + Ak nk ,
where the coefficients A0 , A1 , . . ., Ak are recursively determined as
bk
Ak = ,
1−α
k
X µ ¶
1 j
Ai = bi + α (−1)j−i Aj , 0 ≤ i ≤ k − 1.
1−α i
j=i+1
Then
k
X k
X j µ ¶
X k
X
j j i j−i
Aj n = α Aj n (−1) + bj nj .
i
j=0 j=0 i=0 j=0
Xk Xk Xk µ ¶ Xk
i i j−i j
Ai n = α n (−1) Aj + bi ni .
i
i=0 i=0 j=i i=0
Xk Xk µ ¶
Ai − bi − α j−i j
(−1) Aj ni = 0.
i
i=0 j=i
10
Example 4.1. Solve the difference equation
½
xn = xn−1 + 3n2 − 5n3 , n ≥ 1
x0 = 2.
Solution.
n
X n
X ¡ ¢
xn = x0 + bi = 2 + 3i2 − 5i3
i=1 i=1
Xn n
X
= 2+3 i2 − 5 i3
i=1 i=1
µ ¶2
n(n + 1)(2n + 1) n(n + 1)
= 2+3× −5× .
6 2
n
X µ ¶2
n(n + 1)
i3 = .
2
i=1
An + B = 3[A(n − 1) + B] − 4n
Comparing the coefficients of n0 and n, it follows that A = 2 and B = 3. Thus the general solution is given by
xn = 2n + 3 + 3n c.
xn = −3n + 2n + 3.
Theorem 4.2. Given a nonhomogeneous linear recurrence relation of the second order
x2 − α1 x − α2 = 0.
Then (14) has a particular solution of the following forms, where A is a constant to be determined.
(a) If q 6= q1 , q 6= q2 , then xn = Aq n .
11
Proof. The homogeneous linear recurrence relation corresponding to (14) is
Aq n = α1 Aq n−1 + α2 Aq n−2 + cq n .
Then
A(q 2 − a1 q − a2 ) = cq 2 .
Since q is not a root of the characteristic equation x2 = α1 x + α2 , that is, q 2 − α1 q − α2 6= 0, the coefficient A is
determined as
cq 2
A= 2 .
q − α1 q − α2
(b) Since q = q1 6= q2 , then xn = q n is a solution of (15) but xn = nq n is not, that is,
It follows that
Then £ ¤
A nq 2 − α1 (n − 1)q − α2 (n − 2) = cq 2 .
Since α1 q + 2α2 6= 0, the coefficient A is determined as
cq 2
A= .
α1 q + 2α2
(c) Since q = q1 = q2 , then both xn = q n and xn = nq n are solutions of (15), but xn = n2 q n is not. It then
follows that
q 2 − α1 q − α2 = 0, α1 q + 2α2 = 0, and
12
Put xn = An2 × 5n into the recurrence relation; we have
xn = A0 + A1 n + · · · + Ak nk ,
where A0 , A1 , . . ., Ak are constants to be determined. If k ≤ 2, then a particular solution has the form
xn = A0 + A1 n + A2 n2 .
yn = (α1 − 1)yn−1 + βn , n ≥ 2,
k
X k
X j
X µ ¶ k
X j
X µ ¶ k
X
j j−i j i j−i j i
Aj n = α1 Aj (−1) n + α2 Aj (−2) n + bj nj ;
i i
j=0 j=0 i=0 j=0 i=0 j=0
k
X k
X k
X µ ¶ k
X k
X µ ¶ k
X
j i j−i j i j−i j
Aj n = α1 n (−1) Aj + α2 n (−2) Aj + bj nj .
i i
j=0 i=0 j=i i=0 j=i j=0
13
(b) The recurrence relation (16) becomes
xn = α1 xn−1 + (1 − α1 )xn−2 + βn , n ≥ 2.
Set yn = xn − xn−1 for n ≥ 1; the recurrence (16) reduces to a first order recurrence relation.
xn = 2n2 + 6n + 3 + 2 × 3n − 4n × 3n .
5 Generating functions
The (ordinary) generating function of an infinite sequence
a0 , a1 , a2 , . . . , an , . . .
a0 , a1 , a2 , . . . , an , 0, 0, . . .
1, 1, . . . , 1, . . .
is the function
1
A(x) = 1 + x + x2 + · · · + xn + · · · = .
1−x
14
Example 5.2. For any positive integer n, the generating function for the binomial coefficients
³n´ ³n´ ³n´ ³n´
, , , ..., , 0, . . .
0 1 2 n
is the function
n ³ ´
X n
xk = (1 + x)n .
k
k=0
Example 5.3. For any real number α, the generating function for the infinite sequence of binomial coefficients
³α´ ³α´ ³α´ ³α´
, , , ..., , ...
0 1 2 n
is the function
∞ ³ ´
X α
xn = (1 + x)α .
n
n=0
a0 , a1 , a2 , . . . , an , . . .
be the infinite sequence whose general term an is the number of nonnegative integral solutions of the equation
x1 + x2 + · · · + xk = n.
x1 + x2 + x3 + x4 = n,
15
Example 5.7. Determine the number an of bags with n pieces of fruit (apples, bananas, oranges, and pears) such
that the number of apples is even, the number bananas is a multiple of 5, the number oranges is at most 4, and the
number of pears is either one or zero.
The generating function of the sequence (an ) is
Ã∞ !à ∞ !à 4 !à 1 !
X X X X
A(x) = x2i x5i xi xi
i=0 i=0 i=0 i=0
(1 + x + + + x2 x3 x) 4
x )(1 +
= 2 5
(1 − x )(1 − x )
(1 + x)(1 − x5 )/(1 − x)
=
(1 + x)(1 − x)(1 − x5 )
X∞ µ ¶
1 n −2
= = (−1) xn
(1 − x)2 n
n=0
X∞ µ ¶ ∞
X
n+1
= xn = (n + 1)xn .
n
n=0 n=0
Thus an = n + 1.
Example 5.8. Find a formula for the number an,k of integral solutions (i1 , i2 , . . . , ik ) of the equation
x1 + x2 + · · · + xk = n
such that i1 , i2 , . . . , ik are nonnegative odd numbers.
The generating function of the sequence (an ) is
̰ ! ̰ !
X X xk
A(x) = x2i+1 · · · x2i+1 =
(1 − x2 )k
i=0 i=0
X∞ µ ¶ X ∞ µ ¶
k i+k−1 2i i+k−1
= x x = x2i+k
i i
i=0P ³ ´
i=0
∞ j+r−1
x2j for k = 2r
j=r j−r
= P∞ ³ j+r ´ 2j+1
j=r j−r x for k = 2r + 1.
³ ´ ³ ´
We then conclude that a2s,2r = s+r−1
s−r , a2s+1,2r+1 = s+r
s−r , and an,k = 0 otherwise. We may combine the three
cases into µ ¶
n k
b 2 c+d 2 e−1
bn c−b k2 c
if n − k = even,
an,k = 2
0 if n − k = odd.
Example 5.9. Let an denote the number of nonnegative integral solutions of the equation
2x1 + 3x2 + 4x3 + 5x4 = n.
Then the generating function of the sequence (an ) is
∞
X X
A(x) = 1 xn
n=0 i,j,k,l≥0
2i+3j+4k+5l=0
Ã∞ ! ∞ Ã
∞
!Ã ∞ !
X X X X
= x2i x3j x4k x5l
i=0 j=0 k=0 l=0
1
= .
(1 − x2 )(1 − x3 )(1 − x4 )(1 − x5 )
16
Theorem 5.1. Let sn be the number of nonnegative integral solutions of the equation
a1 x1 + a2 x2 + · · · + ak xk = n.
then µ ¶
X ∞ ∞ µ
X ¶
1 −n k n+k−1 1
= (−ax) = ak xk , |x| < .
(1 − ax)n k k |a|
k=0 k=0
0, 1, 22 , . . . , n2 , . . . .
1 P∞ k
Since 1−x = k=0 x , then
µ ¶
d ³ k ´ X k−1
∞
X ∞
1 d 1
2
= = x = kx .
(1 − x) dx 1−x dx
k=0 k=0
x P∞ k
Thus (1−x)2
= k=0 kx . Taking the derivative with respect to x we have
X ∞
1+x
= k 2 xk−1 .
(1 − x)3
k=0
∞
X
A(x) = a0 + a1 x + (5an−1 − 6an−2 ) xn
n=2
= a0 + a1 x − 5xa0 + 5xA(x) − 6x2 A(x).
Applying the initial values and collecting the coefficient functions of A(x), we further have
¡ ¢
1 − 5x + 6x2 A(x) = 1 − 7x.
17
Observing that 1 − 5x + 6x2 = (1 − 2x)(1 − 3x) and applying partial fraction,
1 − 7x A B
= + .
1 − 5x + 6x2 1 − 2x 1 − 3x
The constants A and B can be determined by
Then ½
A +B = 1
−3A −2B = −7
Thus A = 5, B = −4. Hence
1 − 7x 5 4
2
= − .
1 − 5x + 6x 1 − 2x 1 − 3x
Since
X ∞ X ∞
1 1
= 2n xn and = 3n xn
1 − 2x 1 − 3x
n=0 n=0
Theorem 6.1. Let (an ; n ≥ 0) be a sequence satisfying the homogeneous linear recurrence relation
P (x)
A(x) = , (18)
Q(x)
where Q(x) is a polynomial of degree k with a nonzero constant term and P (x) is a polynomial of degree strictly
less than k.
Conversely, given such polynomials P (x) and Q(x), there is a unique sequence (an ) that satisfies the linear
homogeneous recurrence relation (17) and its generating function is the rational function in (18).
Proof. The generating function A(x) of the sequence (an ) can be written as
k−1 ∞ k−1 ∞
à k !
X X X X X
A(x) = ai xi + an xn = ai xi + αi an−i xn
i=0 n=k i=0 n=k i=1
k−1
X Xk ∞
X k−1
X k
X ∞
X
i n i
= ai x + αi an−i x = ai x + αi an xn+i
i=0 i=1 n=k i=0 i=1 n=k−i
k−1
X ∞
X k−1
X ∞
X k−i−1
X
= ai xi + αk xk an xn + αi xi an xn − aj xj
i=0 n=0 i=1 n=0 j=0
k−1
X k
X k−1
X k−i−1
X
= ai xi + A(x) αi xi − αi xi aj xj
i=0 i=1 i=1 j=0
k−1
X k
X k−1
X l
X
= ai xi + A(x) αi xi − xl αi al−i .
i=0 i=1 l=1 i=1
Then à ! à !
k
X k−1
X k−1
X l
X k−1
X i
X
A(x) 1 − αi xi = ai xi − xl αi al−i = a0 + al − αi al−i xl .
i=1 i=0 l=1 i=1 l=1 i=1
18
Thus
k−1
à l
!
X X
P (x) = a0 + al − αi al−i xl ,
l=1 i=1
k
X
Q(x) = 1 − αi xi .
i=1
Conversely, let (an ) be the sequence whose generating function is A(x). Let
∞
X k
X k
X
A(x) = an xn , P (x) = bi xi , Q(x) = 1 − αi xi .
n=0 i=0 i=1
P (x)
Then A(x) = Q(x) is equivalent to
à k
!Ã ∞
! k
X X X
1− αi xi an xn = bi xi .
i=1 n=0 i=0
The polynomial Q(x) can be viewed as an infinite series with αi = 0 for i > k. Thus
∞ ∞
à n ! k
X X X X
n
an x − αi an−i xn = bi xi .
n=0 n=0 i=1 i=0
Proposition 6.2 (Partial Fractions). (a) If P (x) is a polynomial of degree less than k, then
P (x) A1 A2 Ak
k
= + 2
+ ··· + ,
(1 − ax) 1 − ax (1 − ax) (1 − ax)k
where A1 (x), A2 (x), and A3 (x) are polynomials of degree q + r, p + r, and p + q, respectively.
7 A geometry example
A polygon P in R2 is called convex if the segment joining any two points in P is also contained in P . Let Cn
denote the number ways to divide a labelled convex polygon with n + 2 sides into triangles. The first a few such
numbers are C1 = 1, C2 = 2, C3 = 5.
We first establish a recurrence relation between Cn+1 and C0 , C1 , . . . , Cn . Let P (v1 , v2 , . . . , vn+3 ) denote a convex
polygon with the vertices v1 , v2 , . . . , vn+3 . In each triangular decomposition of P (v1 , v2 , . . . , vn+3 ) into triangles, the
segment v1 vn+3 is one side of a triangle ∆ in the decomposition; the third vertex of the triangle ∆ is one of the vertices
v2 , v3 , . . . , vn+2 . Let vk+2 be the third vertex of ∆ other than v1 and vn+3 (0 ≤ k ≤ n); see Figure 1 below. Then
we have one convex polygon P (v1 , v2 , . . . , vk+2 ) of (k + 2) sides and another convex polygon P (vk+2 , vk+3 , . . . , vn+3 )
19
vk+2
vn+2
vn+3 v3
v1 v2
Figure 1: vk+2 is the third vertex of the triangle with the side v1 vn+3
of (n − k + 2) sides. Then by induction there are Ck ways to divide P (v1 , v2 , . . . , vk+2 ) into triangles and there are
Cn−k ways to divide P (vk+2 , vk+3 , . . . , vn+3 ) into triangles. We thus have the following recurrence relation
n
X
Cn+1 = Ck Cn−k with C0 = 1.
k=0
P∞ n
Consider the generating function F (x) = n=0 Cn x . Then
à ∞
!Ã ∞
!
X X
n n
F (x)F (x) = Cn x Cn x
n=0 n=0
∞
à n !
X X
= Ck Cn−k xn
n=0 k=0
X∞ ∞
1X n
= Cn+1 x = Cn xn
x
n=0 n=1
F (x) 1
= − .
x x
We thus obtain the equation
xF (x)2 − F (x) + 1 = 0.
Solving for F (x), we obtain √
1± 1 − 4x
F (x) = .
2x
Note that
∞ µ1¶
X
√
1 − 4x = 2 (−4x)n
n
n=0
∞
X 1
· ( 12 − 1) · · · ( 12 − n + 1) 2n
= 1+ 2
2 (−1)n xn
n!
n=1
∞
X (−1)(−3)(−5) · · · (−2(n − 1) + 1)
= 2n (−1)n xn
n!
n=0
X∞
1 · 3 · 5 · · · (2(n − 1) − 1) n n
= − 2 x
n!
n=0
∞
X (2(n − 1))!
= 1−2 xn
n!(n − 1)!
n=1
X∞
(2n)!
= 1−2 xn+1 .
n!(n + 1)!
n=0
20
We conclude that
√
1−1 − 4x
F (x) =
2x
X∞
(2n)!
= xn
n!(n + 1)!
n=0
X∞ µ ¶
1 2n
= xn .
n+1 n
n=0
The sequence (Cn ) is known as the Catalan sequence and the numbers Cn as the Catalan numbers.
Example 7.1. Let Cn be the number of ways to evaluate a matrix product A1 A2 · · · An+1 (n ≥ 0) by adding various
parentheses. For instance, C0 = 1, C1 = 1, C2 = 2, and C3 = 5. In general the formula is given by
µ ¶
1 2n
Cn = .
n+1 n
Note that each way of evaluating the matrix product A1 A2 · · · An+2 will be finished by multiplying of two
matrices at the end. There are exactly n + 1 ways of multiplying the two matrices at the end:
is obvious.
The exponential generating function of a sequence (an ; n ≥ 0) is the infinite series
∞
X an
E(x) = xn .
n!
n=0
21
Example 8.1. The exponential generating function of the sequence
is given by
n
X P (n, k)
E(x) = xk
k!
k=0
n ³ ´
X n
= xk
k
k=0
= (1 + x)n .
Example 8.2. The exponential generating function of the constant sequence (an = 1; n ≥ 0) is
∞
X xn
E(x) = = ex .
n!
n=0
Theorem 8.1. Let M = {n1 a1 , n2 a2 , . . . , nk ak } be a multiset over the set S = {a1 , a2 , . . . , ak } with n1 many a1 ’s,
n2 many a2 ’s, . . ., nk many ak ’s. Let an be the number of permutations of the multiset M . Then the exponential
generating function of the sequence (an ; n ≥ 0) is given by
Ãn !Ã n ! Ãn !
X 1
xi X 2
xi X k
xi
E(x) = ··· . (19)
i! i! i!
i=0 i=0 i=0
Proof. Note that an = 0 for n > n1 + · · · + nk . Thus E(x) is a polynomial. The right side of (19) can be expanded
to the form
n1 ,nX
2 ,...,nk n1 +nX
2 +···+nk X
xi1 +i2 +···+ik xn n!
= .
i1 !i2 ! · · · ik ! n! i +i +···+i =n i1 !i2 ! · · · ik !
i1 ,i2 ,...,ik =0 n=0 1 2 k
0≤i1 ≤n1 ,...,0≤ik ≤nk
Note that the number of permutation of M with exactly i1 a1 ’s, i2 a2 ’s, . . ., and ik ak ’s such that
i1 + i2 + · · · + ik = n
Example 8.3. Determine the number of ways to color the squares of a 1-by-n chessboard using the colors, red,
white, and blue, if an even number of squares are colored red.
22
Let an denote the number of ways of such colorings and set a0 = 1. Each such coloring can be considered as a
permutation of three objects r (for red), w (for white), and b (for blue) with repetition allowed, and the element r
appears even number of times. The exponential generating function of the sequence (an ) is
Ã∞ !à ∞ !2
X x2n X xn
E(x) =
(2n)! n!
n=0 n=0
ex + e−x 2x 1 ¡ 3x ¢
= e = e + ex
à 2∞ 2
∞
!
1 X n
3 x n X xn
= +
2 n! n!
n=0 n=0
∞
1X xn
= (3n + 1) · .
2 n!
n=0
Thus
5n + 2 × 3n + 1
an = , n ≥ 0.
4
Example 8.5. Determine the number of ways to color the squares of a 1-by-n board with the colors, red, blue, and
white, where the number of red squares is even and there is at least one blue square.
The exponential generating function for the sequence is
Ã∞ !à ∞ !à ∞ !
X x2i X xi X xi
E(x) =
(2i)! i! i!
i=0 i=0 i=1
ex + e−x x x
= e (e − 1)
2
1 ¡ 3x ¢
= e − e2x + ex − 1
2
∞
1 X 3n − 2n + 1 xn
= − + ·
2 2 n!
n=0
Thus
3n − 2n + 1
an = , n≥1
2
23
and
a0 = 0.
9 Combinatorial interpretations
Theorem 9.1. The combinatorial interpretations of ordinary generating functions:
(a) The number of ways of placing n indistinguishable balls into m distinguishable boxes is the coefficient of xn in
̰ !m
¡ ¢ m X 1
1 + x + x2 + · · · = xk = .
(1 − x)m
k=0
(b) The number of ways of placing n indistinguishable balls into m distinguishable boxes with at most rk balls in
the kth box is the coefficient of xn in the expression
m
Y ¡ ¢
1 + x + x2 + · · · + xrk .
k=1
(c) The number of ways of placing n indistinguishable balls into m distinguishable boxes with at least sk balls in
the kth box is the coefficient of xn in the expression
m
Y ¡ ¢ xs1 +···+sm
xsk 1 + x + x2 + · · · = .
(1 − x)m
k=1
(d) The number of ways of placing n indistinguishable balls into m distinguishable boxes, such that the number of
balls held in the kth box is allowed in a subset Ck ⊂ Z≥0 (1 ≤ k ≤ m), is the coefficient of xn in the expression
X X X
xk xk · · · xk .
k∈C1 k∈C2 k∈Cm
Proof. Let us consider the situation of placing infinitely many indistinguishable balls into m distinguishable boxes.
We use the symbol x to represent a ball and xk to represent indistinguishable k balls. In the course of placing the
balls into m boxes, each box contains either none of balls (x0 = 1), or one ball (x), or two balls (x2 ), or three balls
(x3 ), etc.; that is, each box contains
1 + x + x2 + x3 + · · ·
balls, where the plus sign “+” means “or”.
If we use multiplication to represent “and”, then all possible distributions of balls in the m boxes in the course of
placing are contained in the expression
(1 + x + x2 + · · · )m . (20)
Thus, when there are n distinguishable balls to be placed into the m distinguishable boxes, the number of distri-
butions of the n balls in the m boxes will be the coefficient of xn in the expression (20). Indeed, to compute the
coefficient of xn in (20), we select xn1 from column 1, xn2 from column 2, . . ., xnm from column m in the above table
24
such that xn1 xn2 · · · xnm = xn , and do this in all possible ways. The number of such ways is clearly the number of
non-negative integer solutions of the equation
y1 + y2 + · · · + ym = n,
¡ ¢
and is given by m+n−1
n .
The situation for other cases are similar.
(a) The number of ways of selecting an ordered n objects with repetition allowed from an m-set is the coefficient
n
of xn! in the expression
µ ¶m ÃX ∞
!m
x x2 x3 xk
1+ + + + ··· = = emx . (21)
1! 2! 3! k!
k=0
(b) The number of ways of selecting an ordered n objects from an m-set such that the number of kth objects is
n
allowed in a subset Ck ⊆ Z≥0 , is the coefficient of xn! in the expression
X xk X xk X xk
··· . (22)
k! k! k!
k∈C1 k∈C2 k∈Cm
Example 9.1. Find the number of 4-permutations of the multiset M = {a, a, b, b, b, c}.
25
Week 13-14: Special Counting Sequences
We have considered several special counting sequences. For instance, the sequence n! counts the number of
permutations of an n-set; the sequence Dn counts the number of derangements of an n-set; and the the Fibonacci
sequence fn counts the pairs of rabbits.
1 Catalan Numbers
Definition 1.1. The Catalan sequence is the sequence
µ ¶
1 2n
Cn = , n ≥ 0.
n+1 n
The number Cn is called the nth Catalan number. The first few Catalan numbers are
C0 = 1, C1 = 1, C2 = 2,
C3 = 5, C4 = 14, C5 = 42.
Theorem 1.2. The number of words a1 a2 · · · a2n of length 2n having exactly n positive ones +1’s and exactly n
negative ones −1’s and satisfying
We define another map g : Sn −→ Un as follows: For each word a01 a02 · · · a02n in Sn , the word has exactly n + 1
positive ones and exactly n − 1 negatives ones. There is a smallest integer k such that
1
Then k ≥ 1, a01 + a02 + · · · + a0k−1 = 0, and a0k = 1. Switch the signs of the first k terms in a01 a02 . . . a02n to get a new
word a1 a2 · · · ak a0k+1 · · · a02n , where a1 = −a01 , a2 = −a02 , . . ., ak = −a0k . The word a1 a2 · · · ak a0k+1 · · · a02n has exactly
n ones and exactly n negative ones, and is unacceptable because a1 + a2 + · · · + ak < 0. We set
g(a01 a02 · · · a02n ) = a1 a2 · · · ak a0k+1 · · · a02n .
Now it is easy to see that the maps f and g are inverses of each other. Hence
µ ¶
2n (2n)!
|Un | = |Sn | = = .
n+1 (n + 1)!(n − 1)!
(2n)!
It follows from |An | + |Un | = n!n! that
(2n)! (2n)!
|An | = −
n!n! (n + 1)!(n − 1)!
µ ¶
(2n)! 1 1
= −
n!(n − 1)! n n + 1
(2n)! 1
= ·
n!(n − 1)! n(n + 1)
µ ¶
1 2n
= .
n+1 n
Corollary 1.3. The number of nondecreasing lattice paths from (0, 0) to (n, n) and above the straight line x = y is
equal to the nth Catalan number µ ¶
1 2n
Cn = , n ≥ 0.
n+1 n
Proof. Viewing the +1 as a unit move upward and −1 as a unit move to the right, then each word of length 2n
with exactly n positive ones (+1’s) and n negative ones (−1’s) can be interpreted as a nondecreasing lattice path
from (0, 0) to (n, n) and above the straight line x = y.
Example 1.1. There are 2n people line to get into theater. Admission is 50 cents. Of the 2n people, n have a 50
cent piece and n has a 1 dollar bill. Assume the box office at the theater begin with empty cash register. In how
many ways can the people line up so that whenever a person with a dollar bill buys a ticket and the box office has
a 50 cent piece in order to make change?
If the 2n people are considered indistinguishable, then the answer is the Catalan number
µ ¶
1 2n
Cn = .
n+1 n
If the 2n people are consider distinguishable, then answer is
µ ¶
1 2n (2n)!
· n!n! = .
n+1 n n+1
2
The difference sequence ∆(∆an ) of the sequence (∆an ) is called the second order difference sequence of an
(n ≥ 0), and is denoted by ∆2 an (n ≥ 0). More specifically,
Similarly, the pth order difference sequence ∆p an of an (n ≥ 0) is the difference sequence ∆(∆p−1 an ) of the
sequence ∆p−1 an , namely,
We define the 0th order difference sequence ∆0 an to be the sequence itself, namely,
∆0 an = (∆0 a)n := an , n ≥ 0.
To avoid the cumbersome on notations of the higher order difference sequences, we view each sequence (an ; n ≥ 0)
as a function
f : {0, 1, 2, . . .} −→ C, f (n) = an , n ≥ 0.
Let S(∞) denote the vector space of all functions defined on the set {0, 1, , 2, . . .} of natural numbers. Then S(∞)
is a vector space under the ordinary addition and scalar multiplication of functions. Now the difference operator ∆
is a linear operator on S(∞). For each sequence f ∈ S(∞), ∆f is the sequence of S(∞) defined by
Hence
∆(αf + βg) = α∆f + β∆g.
Theorem 2.3. For any sequence f ∈ S(∞) the pth order difference sequence ∆p f is given by
p
X ³p´
∆p f (n) := (∆p f )(n) = (−1)p−k f (n + k), n ≥ 0.
k
k=0
3
By definition of difference, ∆p f = ∆(∆p−1 f ), we thus have
¡p¢ ³ ´ ¡ p−1 ¢
p−1
Applying the Pascal formula k = k−1 + k , we obtain
p
X ³p´
p
(∆ f )(n) = (−1)p−k f (n + k), n ≥ 0.
k
k=0
in which the pth row is the pth order difference sequence (∆p f )(n) = (∆p a)n (n ≥ 0), where p ≥ 0.
f (n) = an = 2n2 + 3n + 1, n ≥ 0.
Theorem 2.5. For any polynomial sequence an = f (n) (n ≥ 0) of degree p, the (p + 1)th order difference sequence
∆p+1 f is identically zero, that is,
(∆p+1 f )(n) = 0, n ≥ 0.
A sequence an = f (n) (n ≥ 0) of the form
4
Proof. We proceed by induction on p. For p = 0, the sequence f (n) = α0 is a constant sequence, and
(∆f )(n) = α0 − α0 = 0
is the zero sequence. Consider p ≥ 1; and assume ∆p g ≡ 0 for any polynomial sequence g ∈ S(∞) of degree at most
p − 1. Compute the difference
£ ¤
(∆f )(n) = αp (n + 1)p + ap−1 (n + 1)p−1 + · · · + α1 (n + 1) + α0
−[αp np + ap−1 np−1 + · · · + α1 n + α0 ]
h ³p´ i
= αp − αp + αp−1 np−1 + · · · .
1
The sequence g = ∆f is a polynomial sequence of degree at most p − 1. Thus by the induction hypothesis,
∆p+1 f = ∆p (∆f ) = ∆p g ≡ 0.
Theorem 2.6. The difference table of any sequence an = f (n) (n ≥ 0) is determined by the 0th diagonal sequence
(∆0 f )(0), (∆1 f )(0), (∆2 f )(0), ..., (∆n f )(0), ...
Let n ≥ 1; and assume it is true for the case n − 1, that is, for any sequence h ∈ S(∞),
Xµ
n−1
n−1
¶
h(n − 1) = (∆k h)(0).
k
k=0
Xµ
n−1
n−1
¶ Xµ
n−1
n−1
¶³ ´
k
f (n) = (∆ f )(0) + ∆k (∆f ) (0)
k k
k=0 k=0
Xµ
n−1
n−1
¶ Xµ
n−1
n−1
¶
k
= (∆ f )(0) + (∆k+1 f )(0)
k k
k=0 k=0
X ·µ
n−1
n−1
¶ µ
n−1
¶¸
0
= (∆ f )(0) + + (∆k f )(0) + (∆n f )(0)
k k−1
k=1
n ³
X n´
= (∆k f )(0).
k
k=0
5
Corollary 2.7. If the 0th diagonal of the difference table for a sequence an = f (n) (n ≥ 0) is
then the sequence an = f (n) is a polynomial sequence of degree p, and is explicitly given by
³n´ ³n´ ³n´ µ ¶
n
an = f (n) = c0 + c1 + c2 + · · · + cp , n ≥ 0.
0 1 2 p
In other words,
p ³ ´
X n
an = f (n) = (∆k f )(0), n ≥ 0.
k
k=0
Proof. It follows from Theorem 2.6. In fact, for the 0th diagonal sequence
(∆0 f )(0) = 0, (∆1 f )(0) = 0, ..., (∆p−1 f )(0) = 0, (∆p f )(0) = 1, 0, ...
It is easy to see that the first p + 1 terms of the sequence f (n) are given by
For instance, for the case p = 3 this is seen from the following difference table.
0 0 0 1 4 10 20
0 0 1 3 6 10
0 1 2 3 4
1 1 1 1
0 0 0
0 0
0
Note that the terms f (n) are not constant for n ≥ p + 1. However, (∆p+1 f )(n) = 0 for n ≥ 0. Thus f (n) is a
polynomial sequence of degree p such that f (0) = f (1) = · · · = f (p − 1) = 0 and f (p) = 1. Therefore
µ ¶
n(n − 1)(n − 2) · · · (n − p + 1) n
f (n) = = , n ≥ 0.
p! p
The formulas for f (n) in general case follows from the linearity of ∆.
an = f (n) = n3 + 2n2 − 3n + 2, n ≥ 0.
6
Pn ³ ´ ³ ´
k n+1
Proof. Recall the identity k=i i = i+1 . Then
n
X k µ ¶
n X
X k
f (k) = (∆i f )(0)
i
k=0 k=0 i=0
n
" n µ ¶#
X X k
= (∆i f )(0)
i
i=0 k=i
Xn µ ¶
n+1
= (∆i f )(0).
i+1
i=0
Example 2.4. For the sequence an = f (n) = n2 (n ≥ 0), computing the difference we have
0 1 4
1 3
2
Thus µ ¶ µ ¶
2 2 2 2 n+1 n+1 (n + 1)n(2n + 1)
1 + 2 + 3 + ··· + n = +2 = .
2 3 6
For the sequence an = n3 , computing the difference we obtain
0 1 8 27
1 7 21
6 14
8
Thus µ ¶ µ ¶ µ ¶
3 3 3 3 n+1 n+1 n+1 (n + 1)n(2n2 + 1)
1 + 2 + 3 + ··· + n = +6 +8 = .
2 3 4 6
For an = n4 , computing the difference we have
0 1 16 81 256
1 15 65 175
14 50 110
36 60
24
Hence
n
X µ ¶ µ ¶ µ ¶ µ ¶
4 n+1 n+1 n+1 n+1
k = + 14 + 36 + 24
2 3 4 5
k=1
(n + 1)n(6n3 + 9n2 + n − 1)
= .
30
Example 2.5. Consider the sequence an = np with p ≥ 0. Let
C(p, 0), C(p, 1), C(p, 2), ..., C(p, p), 0, 0, ....
7
Definition 2.9. The falling factorial of n with length k is the number
[n]0 = 1,
[n]k = n(n − 1) · · · (n − k + 1) for k ≥ 1.
[n]k+1 = (n − k)[n]k ;
³n´ [n]k
=
k k!
Corollary 2.10. For any integer p ≥ 0,
p
X
np = S(p, k)[n]k (3)
k=0
Theorem 2.11. The Stirling number S(p, k) of the second kind are integers and satisfy the recurrence relation:
S(0, 0) = S(p, p) = 1 if p ≥ 0
S(p, 0) = 0 if p ≥ 1
(4)
S(p, 1) = 1 if p ≥ 1
S(p, k) = S(p − 1, k − 1) + kS(p − 1, k) if p − 1 ≥ k ≥ 1
Proof. For p = 0, we have an = n0 = 1; it follows that S(0, 0) = 1. Since [n]k is a polynomial of degree k in n,
it follows from (3) that S(p, p) = 1. For p ≥ 1, the constant term of the polynomial np is zero. Since [n]k is a
polynomial of degree k, then the constant term of [n]k is zero for all k ≥ 1. It follows from (3) that S(p, 0) = 0.
Now notice that
Xp p−1
X
np = S(p, k)[n]k and np−1 = S(p − 1, k)[n]k .
k=0 k=0
It follows that
p−1
X p−1
X
p p−1
n =n×n = n S(p − 1, k)[n]k = S(p − 1, k)n[n]k
k=0 k=0
p−1
X
= S(p − 1, k)(n − k + k)[n]k
k=0
p−1
X p−1
X
= S(p − 1, k)(n − k)[n]k + S(p − 1, k)k[n]k
k=0 k=0
p−1
X p−1
X
= S(p − 1, k)[n]k+1 + kS(p − 1, k)[n]k
k=0 k=0
Xp p−1
X
= S(p − 1, j − 1)[n]j + kS(p − 1, k)[n]k .
j=1 k=1
Thus
p
X p−1
X
S(p, k)[n]k = S(p − 1, p − 1)[n]p + [S(p − 1, k − 1) + k(S(p − 1, k)][n]k .
k=0 k=1
8
Therefore
S(p, k) = S(p − 1, k − 1) + kS(p − 1, k), 1 ≤ k ≤ p − 1.
In particular, for p ≥ 2 and k = 1, since S(p − 1, 0) = 0, we have
S(p, 1) = S(p − 1, 0) + S(p − 1, 1) = S(p − 1, 1) = · · · = S(2, 1) = S(1, 1) = 1.
With the recurrence relation we conclude that S(p, k) are integers for all 0 ≤ k ≤ p.
(p, k) 0 1 2 3 4 5 6 7 8
0 1
1 0 1
2 0 1 1
3 0 1 3 1
4 0 1 7 6 1
5 0 1 15 25 10 1
6 0 1 31 90 65 15 1
7 0 1 63 301 350 140 21 1
8 0 1 127 966 1701 1050 266 28 1
Theorem 2.12.
n
X p µ
X ¶
p n+1
k = C(p, k)
k+1
k=1 k=0
Xp
S(p, k)
= [n + 1]k+1
k+1
k=0
p+1
X S(p, j − 1)
= [n + 1]j .
j
j=1
The cardinality |P| is called the number of parts (or blocks) of the partition P. We denote by Sn,k the number of
partitions of an n-set into k parts. A partition of a set S into k parts can be viewed as a placement of S into k
indistinguishable boxes so that each box is nonempty.
Example 2.6. (a) For an n-set S and k = 1, the number of ways to partition S into one part is always 1, i.e.,
Sn,1 = 1.
(b) For S = {1, 2}, there is only one partition of S into two parts, namely, {{1}, {2}}. There is only one partition
of S into one part.
(c) For S = {1, 2, 3}, there are three partitions of S into two parts:
{{1}, {2, 3}}, {{1, 2}, {3}}, {{1, 3}, {2}}.
There is only one partition of S into one part.
(d) For S = {1, 2, 3, 4}, there are 7 partitions of S into two parts:
{{1}, {2, 3, 4}}, {{1, 3, 4}, {2}}, {{1, 2, 4}, {3}}, {{1, 2, 3}, {4}},
{{1, 2}, {3, 4}}, {{1, 3}, {2, 4}}, {{1, 4}, {2, 3}}.
There are 6 partitions of S into three parts:
{{1}, {2}, {3, 4}}, {{1}, {3}, {2, 4}}, {{1}, {4}, {2, 3}},
{{2}, {3}, {1, 4}}, {{2}, {4}, {1, 3}}, {{3}, {4}, {1, 2}}.
9
Theorem 2.14. The number Sn,k satisfy the recurrence relation:
S0,0 = Sn,n = 1 if n≥0
Sn,0 = 0 if n≥1
(5)
S n,1 = 1 if n≥1
Sn,k = Sn−1,k−1 + kSn−1,k if n−1≥k ≥1
Proof. Obviously, S0,0 = Sn,n = 1. For n ≥ 1, its also clear that Sn,0 = 0 and Sn,1 = 1.
Let S be a set of n elements, n > k ≥ 1. Fix an elements a ∈ S. The partitions of S into k parts can be divided
into two categories: partitions in which {a} is a single part, and the partitions that {a} is not a single part. The
formal partitions can be viewed as partitions of S − {a} into k − 1 parts; there are Sn−1,k−1 such partitions. The
latter partitions can be obtained by partitions of S − {a} into k parts and joining the element a in one of the k
parts; there are kSn−1,k such partitions. Thus
Corollary 2.15.
S(p, k) = Sp,k , 0 ≤ k ≤ p.
Theorem 2.16.
k
X µ ¶
k
C(p, k) = (−1)i (k − i)p
i
i=0
k µ ¶
1 X k
S(p, k) = (−1)i (k − i)p .
k! i
i=0
Definition 2.17. The nth Bell number Bn is the number of partitions of a n-set into nonempty indistinguishable
boxes, i.e.,
Xn
Bn = Sn,k .
k=0
Proof. Let S be a set of n elements and fix an element a ∈ S. For each partition P of S, there is a part (or block)
A which contains a. Then A0 = A − {a} is a subset of S − {a}. The other blocks of P except the block A form a
partition P 0 of S − A. Let k = |A0 |. Then 0 ≤ k ≤ p − 1. Conversely, for any subset A0 ⊂ S − {a} and¡ any¢partition
P 0 of S − A0 ∪ {a}, the collection P 0 ∪ {A ∪ {a}} forms a partition of S. If |A0 | = k, then there are p−1
k ways to
select A0 ; there are Bn−1−k partitions for the set S − A0 ∪ {a}. Thus
Xµ
n−1
n−1
¶ Xµ
n−1
n−1
¶
Bn = Bn−1−k = Bk .
k k
k=0 k=0
10
The falling factorial [n]k is a polynomial of degree k in n, and so can be written as a linear combination of the
monomials 1, n, n2 , . . . , nk . Let
p
X p
X
k
[n]p = n(n − 1) · · · (n − p + 1) = s(p, k)n = (−1)p−k c(p, k)nk .
k=0 k=0
The integers s(p, k) are called the signed Stirling numbers of the first kind. For variables x1 , x2 , . . . , xp , the
elementary symmetric polynomials s0 , s1 , s2 , . . . , sp are defined as follows:
s0 (x1 , x2 . . . , xp ) = 1,
Xp
s1 (x1 , x2 . . . , xp ) = xi ,
i=1
X
s2 (x1 , x2 . . . , xp ) = xi xj ,
i<j
..
.
sp (x1 , x2 . . . , xp ) = x1 x2 · · · xp ,
Since
p
X
[n]p = n(n − 1) · · · (n − p + 1) = (−1)p−k sp−k (0, 1, . . . , p − 1)nk ,
k=0
we have
s(p, k) = (−1)p−k sp−k (0, 1, . . . , p − 1).
Theorem 2.19. The integers c(p, k) satisfy the recurrence relation:
c(0, 0) = c(p, p) = 1 for p ≥ 0
c(p, 0) = 0 for p ≥ 1 (6)
c(p, k) = c(p − 1, k − 1) + (p − 1)c(p − 1, k) for p − 1 ≥ k ≥ 1
Proof. It follows from the definition that c(0, 0) = c(p, p) = 1 and c(p, 0) = 0 for p ≥ 1.
Let 1 ≤ k ≤ p − 1. Note that
X p
[n]p = (−1)p−k c(p, k)nk ,
k=0
p−1
X
[n]p−1 = (−1)p−1−k c(p − 1, k)nk ,
k=0
[n]p = (n − (p − 1))[n]p−1 .
Then
p−1
X
[n]p = (−1)p−1−k (n − (p − 1))c(p − 1, k)nk
k=0
p−1
X p−1
X
p−1−k k+1
= (−1) c(p − 1, k)n − (−1)p−1−k (p − 1)c(p − 1, k)nk
k=0 k=0
Xp p−1
X
= (−1)p−k c(p − 1, k − 1)nk + (p − 1) (−1)p−k c(p − 1, k)nk .
k=1 k=0
11
Proposition 2.20. Let cn,k denote the number of arrangements of n objects into k nonempty circular permutations.
Then cn,k satisfy the recurrence relation:
c = cn,n = 1 for n ≥ 0
0,0
cn,0 = 0 for n ≥ 1 (7)
cn,k = cn−1,k−1 + (n − 1)cn−1,k for n − 1 ≥ k ≥ 1
cn,n = 1 for n ≥ 0
because when S is divided into n circles then each circle contains exactly one object. We also have
cn,0 = 0 for n ≥ 1
because when S is nonempty then any arrangement contains at least one circle.
Now fix the object an of S. Then the arrangements of S into k circles can be divided into two kinds: the
arrangements that the singleton {an } is a circle, and the arrangements that the singleton {an } is not a circle. In
the former case, deleting the circle {an } the arrangements become the arrangements of n − 1 objects into k − 1
circles; there are cn−1,k−1 such arrangements. In the latter case, deleting the element a from the circle that an is
contained, the arrangements S become arrangements of S − {an } into k circles; for each such arrangement S into k
circles can be obtained by petting an into the left of elements a1 , a2 , . . . , an−1 , and there are n − 1 such ways; there
are (n − 1)cn−1,k arrangements of the second type. Thus we obtain the recurrence relation:
Corollary 2.21.
c(p, k) = cp,k .
3 Partition Numbers
A partition of a positive integer n is a representation of n as an unordered sum of one or more positive integers
(called parts). The number of partitions of n is denoted by pn . For instance,
2 = 1 + 1,
3 = 2 + 1 = 1 + 1 + 1,
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1.
p0 = 1, p1 , p2 , ..., pn , ....
where ak is the number of parts equal to k. If i is not a part of the partition λ then ak = 0, and in this case the
term k ak is usually omitted. For instance, the partitions
5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1
can be written as
51 , 11 41 , 21 31 , 12 31 , 11 22 , 13 21 , 15 .
12
Let λ be the partition
n = n1 + n2 + · · · + nk
of n with n1 ≥ n2 ≥ · · · ≥ nk . The Ferrers diagram of λ is a left-justified array of dots which hask rows with ni
dots in the ith row. For instance, the Ferrers diagram of the partition 15 = 6 + 4 + 3 + 1 + 1 is
• • • • • •
• • • •
• • •
•
•
Theorem 3.1.
∞
X ∞
Y 1
pn xn = . (8)
1 − xk
n=0 k=1
Proof. Note that the right side of (8) is the product of the series
1
= 1 + xk + x2k + x3k + · · ·
1 − xk
for 1 ≤ k ≤ ∞. The term xn arises in the product by choosing a term xa1 1 form the first factor, a term xa2 2 from
the second factor, a term xa3 3 from the third factor, and so on, with
a1 1 + a2 2 + a3 3 + · · · + ak k + · · · = n.
of the integer n.
λ: n = λ 1 + λ 2 + · · · + λk , λ 1 ≥ λ 2 ≥ · · · ≥ λk ,
µ: n = µ1 + µ2 + · · · + µk , µ1 ≥ µ2 ≥ · · · ≥ µk .
The partition λ is called majorized by the partition µ (or µ majorizes λ), denoted by λ ≤ µ, if
λ1 + λ2 + · · · + λi ≤ µ1 + µ2 + · · · + µi for i = 1, 2, . . . , k.
λ: 9 = 5 + 1 + 1 + 1 + 1,
µ: 9 = 4 + 2 + 2 + 1,
ν: 9 = 4 + 4 + 1.
4 ≤ 4,
4 + 2 ≤ 4 + 4,
4 + 2 + 2 ≤ 4 + 4 + 1,
4 + 2 + 2 + 1 ≤ 4 + 4 + 1.
5 > 4,
4 + 2 + 2 > 5 + 1 + 1.
13
Theorem 3.3. The lexicographic order is a linear extension of the partial order of majorization on the set Pn of
partitions of a positive integer n.
Proof. Let λ = (λ1 , λ2 , . . . , λk ) and µ = (µ1 , µ2 , . . . , µk ) be distinct partitions of n. We need to show that if λ is
majorized by µ then there exists an i such that
In fact we choose the smallest integer i such that λj = µj for all j < i but λi 6= µi . Since
λ1 + λ2 + · · · + λi ≤ µ1 + µ2 + · · · + µi ,
4 A Geometric Problem
In this section we shall give a geometric and combinatorial interpretation for the numbers
³n´ ³n´ ³n´
h(k)
n = + + · · · + , k ≥ 0, n ≥ 0.
0 1 k
For each fixed k ≥ 0, we obtain a sequence
(k) (k) (k)
h0 , h1 , h2 , ..., h(k)
n , ... .
(k)
∆h(k)
n = hn+1 − h(k)
n
X n + 1¶ X
k µ k ³ ´
n
= −
i i
i=0 i=0
Xk · µ ¶ µ ¶¸
n+1 n
= −
i i
i=0
Xk µ ¶
n
=
i−1
i=0
³n´ ³n´ µ ¶
n
= + + ··· + = h(k−1)
n .
0 1 k−1
(k)
Theorem 4.1. The number hn counts the number of regions into which a k-dimensional space is divided by n
hyperplanes in general position.
Hyperplanes of a k-dimensional space are in general position means that any l (1 ≤ l ≤ k) hyperplanes meet in
a (k − l)-dimensional plane, but no l + 1 hyperplanes meet in a (k − l)-dimensional plane.
14
Proof. For k = 1, a 1-dimensional space is a straight line, and a 0-dimensional plane is a point. If n distinct points
are inserted on the straight line, the line gets divided into n + 1 parts (called regions). Thus the number of regions
of a line divided by n distinct points is ³n´ ³n´
h(1)
n = + .
0 1
For k = 2, consider n lines in a plane in general position. General position means in this case that the lines are
distinct and not parallel (so that each pair of lines intersects in exactly one point) and no three lines meet in the
same point.
Suppose n lines are in general position and we insert a new line so that the the total n + 1 lines are in general
position. The first n lines intersect the (n + 1)th line at n distinct points, and the (n + 1)th line is divided into
h(1)
n =n+1
(1)
parts. Each of these hn parts divides a region formed by the first n lines into two regions. Thus the number of
(1) (2)
regions formed by n + 1 lines is increased by hn = ∆hn from the number of regions formed by n lines. Note that
(2)
∆h(2) (2)
n = hn+1 − hn = n + 1.
(2)
Since h0 = 1 is the number of regions of a plane divided by zero lines, we conclude that the number of regions of
a plane divided by n lines in general position is
³n´ ³n´ ³n´
h(2)
n = + + .
0 1 2
(3)
For k = 3, the number regions of 3-dimensional space divided by zero planes is h0 = 1. Consider n + 1 planes
in general position, the first n planes intersect the (n + 1)th plane in n lines, and these n lines on the (n + 1)th plane
(2)
are in general position. Then there are hn regions on the (n + 1)th plane, and each of these regions divides a solid
region formed by the first n planes into two solid regions. Thus the number of solid regions formed by n + 1 planes
(2) (3)
in general position is increased by hn = ∆hn from the number of solid regions formed by n planes in general
position. By induction we conclude that the number of solid regions formed by n planes in general position is
³n´ ³n´ ³n´ ³n´
h(3)
n = + + + .
0 1 2 3
More generally, the number of regions of a k-dimensional space divided by 0 number of (k − 1)-dimensional
(k+1)
planes is h0 = 1. Consider n + 1 planes of dimension k − 1, the first n planes intersect the (n + 1)th plane in n
distinct (k − 2)-dimensional planes in general position. These n planes of dimension k − 2 divide the (n + 1)th plane
(k−1)
into hn regions of dimension k − 1, and each of these (k − 1)-dimensional regions divides a k-dimensional region
(formed by the first n planes of dimension k − 1) into two k-dimensional regions. Then the number of k-dimensional
(k−1) (k)
regions formed by n + 1 planes of dimension k − 1 is increased by hn = ∆hn from the number of regions formed
by the first n planes of dimension k − 1. By induction we conclude that
³n´ ³n´ ³n´
h(k)
n = + + · · · + .
0 1 k
15
Homework 4
Chapter 7 p.246 (3rd edition) 7, 12, 19, 22, 24, 25b,e, 26, 30, 32, 37
1. Let an equal the number of different ways in which the squares of 1-by-n chessboard can be colored, using
the colors red, white, and blue so that no two squares colored red are adjacent. Find and verify a recurrence
relation that an satisfies. Then find a formula for an .
2. Solve the recurrence relation an = 8an−1 − 2an−2 , (n ≥ 2), with initial values a0 = −1 and a1 = 0.
5. Let M be the multiset {∞ · e1 , ∞ · e2 , ∞ · e3 , ∞ · e4 }. Determine the generating function for the sequence
(an ; n ≥ 0), where an is the number of n-combinations of M with the additional restrictions:
(a) Each ei occurs an odd number of times.
(b) Each ei occurs a multiple-of-3 number of times.
(c) The element e1 does not occur, and e2 occurs at most once.
(d) The element e1 occurs 1, 3, or 11 times, and the element e2 occurs 2, 4, or 5 times.
(e) Each ei occurs at least 10 times.
6. Solve the following recurrence relations by using the method of generating functions.
(a) an = an−1 + an−2 , (n ≥ 2); a0 = 1, a1 = 3.
(b) an = 3an−2 − 2an−3 , n ≥ 3; a + 0 = 1, a1 = 1, a2 = 0.
an = 4an−1 + 4n , n ≥ 1; a0 = 3.
8. Determine the generating function for the number an of the bags of fruit of apples, oranges, bananas, and pears
in which there are an even number of apples, at most two oranges, a multiple of three number of bananas,
and at most one pear. Then find the formula for an from the generating function.
¡ ¢
9. Let an = n2 , n ≥ 0. Determine the generating function of (an ; n ≥ 0).
10. Let M be the multiset {∞ · e1 , ∞ · e2 , . . . , ∞ · ek }. determine the exponential generating function for the
sequence (an ; n ≥ 0), where a0 = 1 and for n ≥ 1:
(a) an equals the number of n-permutations of M in which each object occurs an odd number of times.
(b) an equals the number of n-permutations of M in which each object occurs at least four times.
(c) an equals the number of n-permutations of M in which 1 occurs at least once, e2 occurs at least twice,
. . ., ek occurs at least k times.
(d) an equals the number of n-permutations of M in which 1 occurs at most once, e2 occurs at most twice,
. . ., ek occurs at most k times.
1
1. Let q be a root of the characteristic polynomial of the recurrence relation
2. In the recurrence relation (1), let Yn = [yn,0 , yn,1 , . . . , yn,k−1 ]T , where yn,i = xkn+i . Show that the recurrence
relation (1) can be changed into the following matrix recurrence relation of order 1:
Yn = AYn−1 .
Find possible relation between the roots of the characteristic polynomial of (1) and the eigenvalues of the
matrix A.
x11 < x12 < · · · < x1n , x21 < x22 < · · · < x2n ,
and
x11 < x21 , x12 < x22 , ..., x1n < x2n ,
equals the nth Catalan number Cn .
2. Let m and n be the non-negative integers with m ≤ n. There are m + n people in line to get into a theater
for which admission is 5 dollars. Of the m + n people, n have a 5 dollar single coin m have a 10 dollar bill.
The box office opens with an empty cash register. Show that the number of ways the people can line up so
that change is available when needed is
µ ¶
n−m+1 m+n
.
n+1 m
(an ; n ≥ 0) be defined by an = 2n2 − n + 3. Determine the difference table of (an ; ≥ 0); and find a formula
3. Let P
for nk=0 ak .
4. Show that the Stirling numbers of the second kind satisfy the relation:
5. The number of partitions of a set of n elements into k distinguishable boxes (some of which may be empty)
is k n . By counting in a different way prove that
n µ ¶
X
n k
k = i!S(n, i).
i
i=1
2
6. Show that the Stirling numbers of the first kind satisfy
7. Let a1 , a2 , . . . , am be distinct positive integers, and let qn = qn (a1 , a2 , . . . , am ) be equal to the number of
partitions of n in which all parts are taken from a1 , a2 , . . . , am . Define q0 = 1. Show that the generating
function for q1 , q2 , . . . , qn , . . . is
Ym
1
.
(1 − xtk )
k=1
(k)
8. Evaluation hk−1 , the number of regions into which k-dimensional spaces is partitioned by k − 1 hyperplanes
in general position.