Excerpt from "Art of Problem Solving Volume 2: and Beyond" ©2013 AoPS Inc.

www.artofproblemsolving.com

Chapter 17

Counting in the Twilight Zone

In Volume 1 we examined a great many counting methods, but all were based on the rock of common
sense. In this chapter we will look at counting methods which go far beyond common sense, and
thus allow the counting of far more interesting things.

17.1 One to One

We will escape the realm of common sense with the help of the obvious-seeming proposition that if
a one to one correspondence can be drawn between the members of two groups, the two groups are
equal in size. Recall that one to one (also written 1-1 or 1 : 1) means that each object in either group
corresponds to one and only one object in the other.

EXAMPLE 17-1 Prove that the number of integers greater than 0 and less than 100 equals the
number of integers greater than 100 and less than 200.

Proof: For any integer n in the first group (so 0 < n < 100) the corresponding integer in the
second group will be n + 100. Clearly 100 < n + 100 < 200. It is clear that every integer n in the first
group has a single counterpart n + 100 in the second, and that every integer m in the second group
has a single counterpart m 100 in the first group. Thus the correspondence is one to one, and the
two groups of numbers are the same size.

17.2 Clever Correspondences

Like any obvious statement, the one to one correspondence principle is useless taken by itself. It
must be coupled with a clever correspondence if it is to have any power.
A common example is of the form:

A dog trainer wants to buy 8 dogs all of which are either cocker spaniels, Irish setters, or
Russian wolfhounds. In how many ways can she make the choice?

/ 196 .
Copyrighted Material
 Excerpt from "Art of Problem Solving Volume 2: and Beyond" ©2013 AoPS Inc.
www.artofproblemsolving.com

the ART of PROBLEM SOLVING: Volume 2 / 197

The problem is an example of making selections with repetition, because we can choose as many
as we wish from each category. At face value it doesn’t seem any harder than many problems we
tackled in Volume 1. However, if you try it you’ll see it’s much harder.

EXERCISE 17-1 Think about the problem until you see why it can’t easily be done with our previous
methods.

Our problem can be solved with a neat one to one correspondence. Namely, for each choice of 8
dogs we can write a sequence like
ddd dd ddd.

The number of d’s before the first represents the number of spaniels, the number in the middle
the number of setters, and the number after the second the number of wolfhounds.

EXAMPLE 17-2 To what choice of dog varieties does the sequence above correspond?

Solution: Since there are three d’s before the first , we have three spaniels. Since there are
two d’s in the middle, there are two setters. Since there are three d’s at the end, there are three
wolfhounds. (Note that this is in fact a legal sequence since exactly eight dogs are accounted for.)
EXERCISE 17-2 Prove that we can write exactly one sequence for each choice of dogs, and that each
sequence corresponds to exactly one choice of dogs. What happens in the case that there are zero
dogs of some variety? Is this OK?

Since we have established in Exercise 17-2 a one to one correspondence between choices of dogs
and sequences, all we have to count is the number of sequences. But counting the sequences is easy,
since each sequence is just a matter of choosing two positions for the ’s out of 10 total positions.
(There are 10 positions because we have 8 d’s and 2 ’s.) The number of ways to choose 2 positions
out of 10 is 10
2 = 45.

EXERCISE 17-3 Find (and prove) a simple formula for the number of ways to buy n dogs if there
are r varieties to choose from.
EXERCISE 17-4 Prove that the number you found in the previous exercise is equal to the number
of solutions in nonnegative integers of x1 + x2 + · · · + xr = n.

There are many other ways to set up one to one correspondences; in general, when a problem
looks too difficult by other methods, look for a correspondence to a simpler problem. It will in
general require some creativity on your part to come up with the particular correspondences which
do the job, but you’ll get a feel for what works with experience.

EXAMPLE 17-3 In how many ways may five people be seated in a row of twenty chairs given that
no two people may sit next to one another?

Copyrighted Material
 Excerpt from "Art of Problem Solving Volume 2: and Beyond" ©2013 AoPS Inc.
www.artofproblemsolving.com

198 . CHAPTER 17. COUNTING IN THE TWILIGHT ZONE

Solution: Consider some arrangement of the five people as specified, then take one chair out from
between each pair of people. What you’re left with is a unique arrangement of 5 people in 16 chairs
without restrictions. Similarly, starting with an unrestricted arrangement of 5 people in 16 chairs,
adding a chair between each pair of people gives a unique arrangement of 5 non-adjacent people in
20 chairs. (Convince yourself of these two assertions.) Thus there is a one to one correspondence
between the restricted 20-chair arrangements of the problem and unrestricted 16-chair arrangements.
The number of unrestricted 16-chair arrangements is the number of ways to choose 5 chairs out of
16, or 16
5 .
EXAMPLE 17-4 How many nonnegative integer solutions are there to x1 + x2 + x3  50?

Solution: We have seen how to solve x1 + x2 + · · · + xr = n, but the inequality complicates

the problem. We might be tempted to successively solve x1 + x2 + x3 = 50, then x1 + x2 + x3 = 49, and
so on, then try to simplify the sum of the results. But creative thinking yields a di↵erent way: just
put as much of the 50 as is desired into x1 + x2 + x3 , and put the rest into a new variable y. With this
idea, it becomes clear that a one to one correspondence exists between nonnegative solutions of our
inequality and nonnegative solutions of the equality x1 + x2 + x3 + y = 50, which by Exercises 17-3
and 17-4 has 533 solutions.

17.3 Easy as . . .
In the first volume we used sets and Venn diagrams to attack problems like:

There are 100 students taking language classes at Austin High School. If 60 are taking
German and 75 are taking Spanish and these are the only languages taught, how many
students take both Spanish and German?

Let’s try a new approach. Say there are x students taking both languages. We could try counting
the number of students taking languages by just adding the number of students in each language, or
60 + 75 = 135. Since we know there are 100 students taking languages, we have made a mistake. Our
error is in counting students taking both languages twice, once for German and once for Spanish.
Thus, we must subtract from 135 the number of students taking both languages so that we only
count them once. Hence, the total number of students taking language classes is 135 x. Setting this
equal to 100 we find x = 35.
This is the heart of the Principle of Inclusion-Exclusion, or PIE: if we count something twice,
subtract it once so we only count it once. It’s that simple! When we move from two classes to three,
the counting becomes a bit trickier, but the concept is the same. For example, let’s call the classes
A, B, and C and let the number of students in each be #(A), #(B), and #(C), respectively. To take care
of overcounting students in both classes A and B, we must subtract the number of students in both
classes, which we’ll call #(A \ B). Similarly, we subtract the number of students in both B and C and
in both A and C, for a total of
#(A) + #(B) + #(C) #(A \ B) #(A \ C) #(B \ C)
students. To convince yourself that this takes care of students enrolled in two classes, pretend you
are in exactly two of the classes. How many times are you added to the total? Subtracted? How
many times are you counted?

Copyrighted Material
 Excerpt from "Art of Problem Solving Volume 2: and Beyond" ©2013 AoPS Inc.
www.artofproblemsolving.com

the ART of PROBLEM SOLVING: Volume 2 / 199

Now what if you’re in all three classes? You’re added three times and subtracted three times, so
you’re not counted at all! To take care of this, we must add back the number of students in all three
classes. This makes our total number of students

#(A) + #(B) + #(C) #(A \ B) #(A \ C) #(B \ C) + #(A \ B \ C).

EXERCISE 17-5 Again, pretend you are in 1, 2, or 3 classes and make sure that the aforementioned
method only counts you once no matter how many times you are added or subtracted.
EXERCISE 17-6 What if there were 4 classes? How about 5 classes?
EXAMPLE 17-5 How many positive integers less than or equal to 1000 do not have 2, 3, or 5 among
their prime factors?

Solution: We count the number of positive integers less than or equal to 1000 which do have
2, 3, or 5 among their prime factors and subtract that number from 1000 to find how many do not.
There are 1000/2 = 500 multiples of 2, b1000/3c = 333 multiples of 3 and 1000/5 = 200 multiples of
5 in this range, for a total of 500 + 333 + 200 = 1033 positive integers less than or equal to 1000 with
2, 3, or 5 as a factor. We’ve obviously overlooked something. We’ve badly overcounted, because
many numbers are multiples of more than just one of these three numbers. Applying the Principle
of Inclusion-Exclusion, we subtract from 1033 the number of multiples of both 2 and 3, of both 2 and
5, and of both 3 and 5. Finally, we then add to the result the number of integers which are multiples
of all three.
Any number which is a multiple of 2 and 3 is a multiple of (2)(3) = 6, since 2 and 3 have no
common nontrivial factors. Hence, we seek the multiples of 6, 10, 15, and 2(3)(5) = 30. There are
b1000/6c = 166 multiples of 6, b1000/10c = 100 multiples of 10, b1000/15c = 66 multiples of 15, and
b1000/30c = 33 multiples of 30. By PIE, there are

1033 166 100 66 + 33 = 734

integers less than or equal to 1000 with 2, 3, or 5 among their factors. Hence, there are 1000 734 = 266
integers in that range which are not multiples of 2, 3, or 5.
EXERCISE 17-7 Suppose there is some number of objects placed in n categories A1 , A2 ,. . ., An , where
each object may be in more than one category. Let #(Ai ) be the number of objects in category Ai .
Suppose #(Ai ) is the same for all i, #(Ai \ A j ) is the same for all distinct pairs (i, j), #(Ai \ A j \ Ak ) is
the same for all triples (i, j, k), etc. Show that the Principle of Inclusion-Exclusion gives

n n n
#(A1 [ A2 [ A3 [ · · · [ An ) = #(A1 ) #(A1 \ A2 ) + #(A1 \ A2 \ A3 )
1 2 3
n n
#(A1 \ A2 \ A3 \ A4 ) + · · · + ( 1)n #(A1 \ A2 \ · · · \ An ).
4 n
This application of the Principle of Inclusion-Exclusion is very useful in problems containing sym-
metry.
EXAMPLE 17-6 There are four baskets numbered from 1 to 4 and four balls numbered from 1 to 4.
Each basket is allowed to have at most two balls. In how many ways can the balls be placed in the
baskets such that no ball has the same number as the basket it is in?

Copyrighted Material
 Excerpt from "Art of Problem Solving Volume 2: and Beyond" ©2013 AoPS Inc.
www.artofproblemsolving.com

200 . CHAPTER 17. COUNTING IN THE TWILIGHT ZONE

Solution: This problem has symmetry, so we apply the concepts of the previous exercise. First
we count the number of ways to put the balls in the baskets with no restrictions. There are 4! ways to
put the balls in 4 di↵erent baskets. There are 41 42 (3)(2) ways to put two balls in one basket and the
others in their own baskets (4 ways to pick the basket with two balls, 6 ways to pick the balls in that
basket, (3)(2) ways to put the other balls in di↵erent baskets). Finally, we can put two balls each in
two baskets in 42 42 ways (6 ways to pick the two non-empty baskets and 6 ways to distribute the
balls among these baskets). Hence there are 24 + 144 + 36 = 204 ways to put the balls in the baskets.
To solve the problem, we will count the ways the balls can be put in the baskets such that at least
one ball has the same number as the basket that holds it. Let #(i) be the number of ways to fill the
baskets such that basket i holds ball i. From the previous exercise, we seek the quantity

4 4 4 4
#(1) #(1 \ 2) + #(1 \ 2 \ 3) #(1 \ 2 \ 3 \ 4).
1 2 3 4

For the first, after we put ball 1 in basket 1, we can either put another ball in that basket or put
all the balls in the other baskets. The former can be done in 31 (32 ) = 27 ways (3 ways to pick the
other ball in basket 1, 32 ways to put the other balls in the other baskets); the latter can be done in
3 3
1 2 (2) + 3! = 24 ways, where we divide this into the case of two of the balls in one of the other
three baskets and the case of the other three being in di↵erent baskets. For #(1 \ 2) we put balls 1
and 2 in baskets 1 and 2. The other two balls can be put in the baskets in 2 + (2)(2)(2) + (2)(2) = 14
ways, where we consider the cases of putting 2, 1, or 0 of the remaining balls in the first two baskets.
(Make sure you see this.) The last two are easy. After we put 3 balls in the right baskets, the other
has four choices and we can only get them all right in 1 way. Putting these in our above expression,
there are
4(27 + 24) 6(14) + 4(4) 1(1) = 135

ways to put the balls in the baskets so that at least one ball is in the right basket. This leaves
204 135 = 69 ways of filling the baskets so that no ball has the same number as the basket that
holds it.
This is a very complicated counting problem, and you may argue that you would be better o↵
just listing the possibilities and counting. Using the Principle of Inclusion-Exclusion is better than
listing and counting because it’s awfully hard to tell if we’ve listed all the possibilities, and as the
number of possibilities gets large (what if there were 6 balls and 6 baskets), the listing and counting
method becomes very unreliable.

17.4 Generating Functions

When it comes to counting, generating functions are the cleverest thing there is. The idea of
generating functions is that functions can be manipulated in various ways which combinatorial
quantities cannot, so to examine the properties of some combinatorial function A(k), we instead look
at the function
A(0) + A(1)x + A(2)x2 + A(3)x3 + · · · ,

Copyrighted Material