COMBINATORICS EXERCISES Stephan Wagner

1. How many possible ways are there to form five-letter words using only the letters A–H?
How many such words consist of five distinct letters?

2. How many different number plates for cars can be made if each number plate contains two
letters (A–Z) followed by five digits (0–9)?

3. We want to design a flag that consists of three horizontal stripes; the colour of the middle
stripe should be different from the other two stripes. How many possibilities are there, if
the colours red, green, blue, yellow, black and white can be used?

4. How many diagonals does a regular dodecagon (a twelve-sided polygon) have?

5. How many three-digit numbers abc have the property that a ≤ b ≤ c?

6. How many different four-digit numbers are there such that the product of the four digits
is 420?

7. The dean of science wants to select a committee consisting of mathematicians and physi-
cists to discuss a new curriculum. There are 15 mathematicians and 20 physicists at the
faculty; how many possible committees of 8 members are there, if there must be more
mathematicians than physicists (but at least one physicist) on the committee?

8. A palindrome is a word that can be read the same way in either direction (such as RACE-
CAR). How many 9-letter palindromes (not necessarily meaningful) can be formed using
the letters A–Z?

9. The four women Anne, Betsie, Charlotte and Dolores and the six men Eric, Frank, George,
Harry, Ian and James are friends. Each of the women wants to marry one of the six men.
In how many ways can this be done?

10. How many five-element subsets of {1, 2, 3, . . . , 10} contain at least one odd element?

11. Determine the coefficient of x3 y 4 z in the expansion of

(a) (x + y 2 + z)6 (b) (2x − y − 3z)8

12. In how many possible orders can the letters of the word MATHEMATICS be arranged?

13. At a dance, there are 20 girls and 20 boys. How many ways are there to form 20 pairs?
How many, if boys may dance with boys and girls with girls?

14. Consider sequences (x1 , x2 , . . . , xn ) of length n whose elements are taken from the set
{1, 2, . . . , n}. Determine the proportion of those sequences that do not contain the number
1; what happens as n → ∞?

15. How many words of length n can be formed from the letters A,B,C if the letter A has to
occur an even number of times?

16. Determine the number of pairs (A, B) of sets such that A is a subset of B and B is a
subset of {1, 2, . . . , n}.
17. Prove the identity
n ( )
∑ ( )
k n+1
=
m m+1
k=m
in two different ways:

• by induction on n,
• by a counting argument: if m + 1 numbers are chosen from the set {0, 1, . . . , n}, how
many choices are there such that the largest number chosen is k?

18. Find a formula for the sum ( )

∑
n
n
k
k
k=0

by means of the binomial theorem. [HINT: differentiate!]

What can be deduced about the average number of elements in a random subset of
{1, 2, . . . , n}?

19. Consider all r-element subsets of the set {1, 2, . . . , n}. Each of them has a maximum; prove
that the sum of these maxima is ( )
∑n
k−1
k
r−1
k=r
(n+1) ( ) (k )
and show that this sum is equal to r r+1 . [HINT: show first that k k−1 r−1 = r r , and
make use of the previous problem.] Deduce that the average maximum of an r-element
subset of {1, 2, . . . , n} is precisely r+1
r
(n + 1).

20. We want to count the number of ways to choose five elements from the set {1, 2, . . . , 20}
with the restriction that we may not choose consecutive integers.

• Why is this number equal to the number of positive integer solutions to the equation

l1 + l2 + l3 + l4 + l5 + l6 = 21

with the additional restriction that l2 , l3 , l4 , l5 > 1? [HINT: Consider differences]

• Substitute m2 = l2 + 1, . . . , m5 = l5 + 1 to obtain

l1 + m2 + m3 + m4 + m5 + l6 = 17,

where l1 , m2 , m3 , m4 , m5 , l6 can be arbitrary positive integers. Use the dots-and-bars

argument to determine the number of solutions.
• In general, in how many ways can k elements be chosen from {1, 2, . . . , n} if no
consecutive numbers are allowed?

21. Prove that

n (
∑ )
4n
= 24n−2 + (−1)n · 22n−1
4k
k=0
for all n > 0.

22. A man has a certain number of friends; he wants to invite three of them for dinner every
day of the year. How many friends must he have at least if he does not want to invite the
same three friends twice?
23. A single piece is placed on the lower-left corner square of an 8 × 8-chessboard. The piece
may only move horizontally or vertically, one square at a time. How many possible ways
are there to move the piece to the opposite corner in 14 moves (the smallest possible
number of moves)?
24. Prove the formula ( ) ( ) ( ) ( )
n+2 n n n
= +2 +
m+1 m+1 m m−1
by comparing coefficients in the identity (1 + x)n+2 = (1 + x)2 (1 + x)n .
25. How many 3-element subsets of {1, 2, 3, . . . , 100} contain at least one element that is di-
visible by 2 and at least one element that is divisible by 5?
26. Each of the nine unit squares of a 3 × 3-square is coloured randomly red or blue, each with
probability 12 . Determine the probability that none of the four 2 × 2-squares is completely
red.
27. According to a recent survey, 60% of Stellenbosch students play rugby, 50% play cricket,
and 70% play tennis. Furthermore, it was found that 30% play both rugby and cricket,
35% play rugby and tennis, and 30% play cricket and tennis. Someone claims that 20%
play all three sports. Show that this cannot be true.
28. How many numbers between 1 and 1000000 are neither a square nor a cube of an integer?
29. The South African National Assembly consists of 400 members. How many possible ways
are there to divide the 400 seats among three parties (a) such that none of them has a
majority? (b) such that none of them has a 2/3-majority?
30. Bridge is played with a standard deck of 52 cards, each player receives 13 cards. How
many possible hands can a player get in a game of bridge? In the HCP (high card points)
system, four points are assigned to an ace, three points to a king, two to a queen and one
to a jack. How many possible hands result in a total of (a) exactly three points? (b) at
least three points?
31. Prove the identity
∑
n ( )
n+1
i(n − i) =
3
i=0
by a combinatorial argument: If three numbers are chosen from the set {0, 1, . . . , n}, how
many choices are there such that the middle one is i? Use the same idea to determine the
sum
∑n ( )( )
i n−i
.
r ℓ
i=0

32. Determine a formula for the number of permutations of {1, 2, . . . , n} with exactly p fixed
points. What is the probability that a randomly chosen permutation has p fixed points,
as n → ∞?
33. Prove the identity
∑n ( ) n ( )( ) (( ) ( ))
2n 2 ∑ 2n 2n 1 4n 2n
= = + (−1)n
2k 2k 2n − 2k 2 2n n
k=0 k=0

by means of an appropriate polynomial identity.

34. Solve the following nonhomogeneous recursions:

(a) an = 3an−1 − 2an−2 + 3n ; a0 = −3, a1 = 6.

(b) an = an−1 + 2an−2 + 9n2n ; a0 = 0, a1 = 4.

35. Let Fn denote the Fibonacci sequence, defined by F0 = 0, F1 = 1 and Fn+1 = Fn + Fn−1 .
Show that
∑n
Fk = Fn+2 − 1.
k=0

36. Suppose that A(x) is the generating function of a sequence an . What is the generating
function of the sequence
∑n
(a) 3n an , (b) kak ?
k=0

37. We consider the number of triangulations of a regular n-gon (the figure shows some possible
triangulations in the case n = 6; there are fourteen triangulations in this case). Show that
the number of triangulations is a Catalan number.

38. A certain computer system only allows passwords that obey to the following rules:

• A password is a combination of any of the ten digits 0-9, the 52 (uppercase and
lowercase) letters and the eight additional characters !,$,%,&,§,*,(,).
• Any letter or special character has to be followed by a digit.

Determine the number of possible passwords whose length is (a) eight (b) at most eight
by means of generating functions.

39. Consider the following variant of the “coin stack” problem: this time, we form stacks of
squares; a configuration consists of rows of contiguous squares placed on top of each other
in such a way that the leftmost and the rightmost square in every row remain unoccupied.
The figure shows a possible configuration. How many stacks of this type are there, if the
bottom row consists of n squares?
40. Determine the number of compositions of an integer n into odd summands by means of
generating functions and the symbolic method (for instance, 5 + 3 + 1 + 1 + 3 is a feasible
composition of 13).

41. Solve the following nonlinear recursion by means of generating functions:

∑
n
an = kak , a0 = 0, a1 = 1.
k=0

42. Grandma wants to reward her four grandchildren; she has an amount of R100 available,
and wants to distribute it according to the following rules:

• The oldest should get at least R25,

• The youngest should not get more than R20.

Determine the number of possible ways to distribute the money.

43. Using the symbolic method, determine the exponential generating function for words over
the alphabet {A,B,C} with the property that every letter occurs at least twice.

44. Motzkin paths are defined like Dyck paths, the only exception being that horizontal
(“level”) steps are possible as well. The figure shows an example of a Motzkin path.
Determine the generating function for Motzkin paths by means of the symbolic method.

45. Determine the generating function for unary-binary trees, that is, rooted trees with
the property that every node has either one or two children (internal node), or no child
(external node).

46. Recall that a derangement is a permutation without fixed points (equivalently, a per-
mutation without a cycle of length 1). Show that the exponential generating function for
e−x
derangements is given by 1−x , and deduce the formula

∑
n
(−1)k
n!
k!
k=0

for the number of derangements of {1, 2, . . . , n}.

47. A person moves on a line, one step to the left (with probability p) or one step to the right
(with probability q = 1 − p) at every second.
2
(2n)
(a) Show that there are n+1 n sequences of steps that take the person back to the
original position for the first time after exactly 2n + 2 steps (n ≥ 0).
 (b) Show: the probability for the person to return to the original position at some stage
is given by
∞
∑ ( )
2 2n n+1 n+1
p q .
n+1 n
n=0

(c) Write this expression in terms of the generating function for the Catalan numbers
and simplify to prove that the probability is exactly 1 − |p − q|.

48. Determine formulas for the following special Stirling numbers:

[ ] { }
n n
(a) , (b)
n−2 n−2

49. In how many different ways can billiard balls numbered 1 to 8 be coloured in four colours
(red, blue, green, yellow) if every colour has to be used at least once?

50. Every permutation can be broken up into “runs” (consecutive elements in increasing order)
in a unique way. For instance, the permutation

7|259|148|36

has four runs, indicated by the bars. How many permutations of nine elements have exactly
four runs?

51. Determine the number of permutations of {1, 2, . . . , 7} with at least 4 cycles.

52. Let σ be a permutation of {1, 2, . . . , n}. For every j, we define bj to be the number of
elements to the left of j that are larger than j. The sequence b1 , b2 , . . . , bn is called the
inversion table of σ.

(a) Determine the inversion table of the permutation σ = 5274361.

(b) Determine the permutation σ whose inversion table is 4, 4, 3, 2, 2, 0, 0.

53. Show that [ ]

∑
n
n k
(−1) n−k
x = xn = x(x − 1)(x − 2) . . . (x − n + 1).
k
k=0

54. Show that [ ] ∑ [ ]

n
n+1 n! j
= .
k+1 j! k
j=k

HINT: How many permutations of {1, 2, . . . , n + 1} are there for which 1 is in a cycle of
length n + 1 − j?

55. Show that { } ∑n ( ){ }

n+1 n j
= .
k+1 j k
j=k

HINT: How many set partitions of {1, 2, . . . , n + 1} are there for which 1 is in a group of
n + 1 − j elements?
56. Show that
m ( ) { }
∑ m { }
∑
m n n
k! = mk = mn
k k k
k=1 k=1

by means of a combinatorial argument: how many functions from {1, 2, . . . , n} to {1, 2, . . . , m}

have exactly k distinct values in their range?

57. Prove: if n > 1, then the number of permutations of {1, 2, . . . , n} with an even number of
cycles equals the number of permutations with an odd number of cycles.

58. A permutation can be regarded as a bijection from {1, 2, . . . , n} to {1, 2, . . . , n}. Therefore,
any permutation has an inverse. For example, the inverse of 56128473 is the permutation
34861275.

(a) Why do a permutation and its inverse have the same number of cycles?
(b) Show: a permutation that is equal to its own inverse consists only of 1- and 2-cycles.
[ ]
(c) Prove by means of (a) and (b): if k < n/2, then nk is even.

59. A Joyce tree is a binary tree whose nodes are placed at distinct levels, see the figure.
How many Joyce trees with 2n + 1 nodes are there?

∑
60. The generating function A(x) = ∞ n x
n=1 an x satisfies the equation A(x) = (1−A(x))2 . De-
termine an explicit formula for the coefficients an by means of the Lagrange inversion
formula.

61. Show that the exponential generating function of the sequence (−1)n/2−1 (4n − 2n )Bn
(where Bn is the n-th Bernoulli number) is ix + x tan x, and deduce the formula
n
Bn = (−1)n/2−1 tn−1
4n − 2n
for all even values of n, where tn−1 denotes a tangent number.

62. Draw the Ferrers diagram of the partition 8 + 6 + 6 + 6 + 4 + 4 + 3 + 2 + 1 + 1 + 1, and

determine the conjugate partition.

63. In how many ways can one give change of n rand using R1 or R2 coins?

64. Determine generating functions for the following types of partitions:

(a) Partitions with the property that 1 occurs an even number of times (possibly 0) as a
part, while 2 does not occur as a part at all.
(b) Partitions with the property that 1 does not occur as a part.

Show that the generating functions in (a) and (b) are the same.
65. Use generating functions to show that the number of partitions of n in which every part
occurs at most twice is the same as the number of partitions of n with the property that
none of the parts is divisible by 3.

66. Prove that the q-binomial coefficients

[ ]
n (1 − q)(1 − q 2 ) . . . (1 − q n )
=
k q (1 − q)(1 − q ) . . . (1 − q k ) · (1 − q)(1 − q 2 ) . . . (1 − q n−k )
2

satisfy the recursion [ ] [ ] [ ]

n+1 n n+1−k n
= +q .
k q k q k−1 q

67. Prove the q-binomial theorem (Cauchy binomial theorem):

∏
n n [ ]
∑ n
(1 + q j x) = xk q k(k+1)/2 .
k q
j=1 k=0

The special case q = 1 is the ordinary binomial theorem.

68. A partition that is equal to its conjugate is called a self-conjugate partition. Show that
the number of self-conjugate partitions of n is the same as the number of partitions of n
into distinct odd parts. [HINT: look at the figure]