Chapter 2
Combinatorics
Life presents many situations where we find ourselves counting objects or their arrangements.
You sit down to an exam and find that you need to do any five problems from the eight given.
How many different choices can you make? You have three pairs of jeans, three shirts, and
two pairs of shoes you like; how many different outfits can you make? Does it matter if you
are color blind? Suppose 30 hockey teams from the National Hockey League compete for
the Stanley Cup: in how many different ways can the tournament be arranged? In how many
different ways can the teams rank in the final standing (with no ties allowed)? How many
different lineups are possible for six local jazz bands at a benefit concert?
The answers to questions like these require methods known as combinatorics, a topic of
mathematics devoted to the art of counting. In particular, the typical questions that arise in the
course of analyzing an algorithm, or designing a program, tend to require counting. Another
practical example provides one of the most efficient error-detection method, called codabar.
This method is used by all m ajor credit card companies, as well as other enterprises. When
a bank issues a credit card with the identification number a
1
a
2
a
3
a
4
-b
5
b
6
b
7
b
8
-c
9
c
10
c
11
c
12
-
d
13
d
14
d
15
d
16
, the last digit, d
16
, is the check digit to control the accuracy, which is chosen
as follows. Double the sum of all digits in odd positions, then add those digits that exceed
4 and then add all the remaining digits in even positions. The check digit is chosen to make
the total ends with zero. How many such numbers exist? This is more complicated than the
previous examples, but they all are solved using the same approach.
Obviously, it is impossible to include all combinatorial methods in one chapter—there are
many books devoted to this subject (see, for instance, [26, 30, 93, 115]). This chapter gives
an introduction to combinatorics and will be used as a reference later on.
In this chapter, three elementary counting methods are considered: the Fundamental Princi-
ple of Counting, permutations, and combinations. We also discuss the formal properties of
summation and the most common set of combinatorial numbers: the binomial coefficients. In
addition, we present some basic properties of canonical power series—hypergeometric func-
tion. At the end, a famous asymptotic formula—the Stirling approximation to a factorial—is
considered.
25
26
Chapter 2. Combinatorics
2.1 Properties of Summation
Sums are among the most frequently used operations on expressions. Recall some facts about
them. For example, there are several ways to denote a summation:
x
1
+ x
2
+ ···+ x
n
=
n
∑
j=1
x
j
, or
∑
16 j6n
x
j
, or
∑
j∈[1..n]
x
j
, or even
∑
p( j)
x
j
,
where p( j) is some property of j, where j is an integer, and 1 6 j 6 n. If n < 1, this is a
summation over the null set, which is customarily defined to be zero
1
. By convention, a sum
over an empty set of indices equals zero. T here may be more complicated cases, as examples
show. Other possibilities for p( j ) could be that j is a perfect square, or that j is a prime
number greater than 13, and so on.
Example 2.1 Find the sum
n
∑
k=1
1
k(k + 1)
. This example uses the ability to split a sum into
sums of its components without changing its value.
Solution
. Using partial fraction decomposition
2
(PFD), we have
n
∑
k=1
1
k(k + 1)
=
n
∑
k=1
1
k
−
1
k + 1
=
n
∑
k=1
1
k
−
n
∑
k=1
1
k + 1
always allowed for a finite summation
=
1 +
1
2
+
1
3
+ ···+
1
n
−
1
2
+
1
3
+ ···+
1
n
+
1
n + 1
= 1 −
1
n + 1
=
n
n + 1
.
This is a telescopic sum because of the “cross-cancellations” between the two separated sums
in the parentheses above. When n approaches infinity we get a compact result,
∞
∑
k=1
1
k(k + 1)
= lim
n→∞
n
n + 1
= lim
n→∞
1
1 +
1
n
= 1.
We recall some basic properties of infinite sums. Let T be an infinite index set; we are only
allowed to write
∑
k∈T
(a
k
+ b
k
) =
∑
k∈T
a
k
+
∑
k∈T
b
k
if it is true that
3
∑
k∈T
|a
k
| < ∞ and
∑
k∈T
|b
k
| < ∞,
a condition which is called absolute convergence.
To see that the condition is not necessary, consider the last example: the two harmonic series
∑
k>1
1
k
and
∑
k>1
−1
k + 1
1
Some authors use t he definition
∑
m6 j6n
x
j
= −
∑
n6 j6m
x
j
, where m > n. We do not follow this notation.
2
This topic is discussed in more detail in section 12.5.
3
This is a sufficient condition.
Get Methods in Algorithmic Analysis now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
