Chapter 6
Combinatorics
6.1 Introduction to Counting
188
Combinatorics is the study of counting. That sounds rather babyish, but in fact count
ing problems can be quite deep and interesting and have many connections to other
branches of mathematics. For example, consider the following problem.
Example 6.1.1 (Czech and Slovak 19 95) Decide whether there exist 10 ,000 10 -digit
numbers divisible by 7, all of which can be obtained from one another by a reordering
of their digits.On the surface, it looks like a number theory problem. But it is actually just a
question of carefully counting the correct things. We will solve this problem soon, on
page 204, but first we need to develop some basic skills.
Our first goal is a good understanding of the ideas leading up to binomial the
orem. We assume that you have studied this subject a little bit before, but intend to
review it and expand upon it now. Many of the concepts will be presented as a se
quence of statements for you to verify before moving on. Please do not rush; make
sure that you really understand each statement! In particular, pay attention to the tiniest
of arithmetical details: good combinatorial reasoning is largely a matter of knowing
exactly when to add, multiply, subtract, or divide.Permutations and Combinations
Items 6.1.2-6 .1.12 introduce the concepts of permutations and combinations, and use
only addition, multiplication, and division.6.1.2 Simple Addition. If there are a varieties of soup and b varieties of salad, then
there are a + b possible ways to order a meal of soup or salad (but not both soup and
salad).
6.1.3 Simple Multiplication. If there are a varieties of soup and b varieties of salad,