7 Basic Counting

In this chapter, we will explore the mathematics of counting. This handout will review the
basics of counting so we can tackle more advanced concepts in the following days.

7.1 Constructive Counting

Constructive counting is a fundamental method in combinatorics. Essentially, we count the
number of objects that satisfy some property by “constructing” them, i.e. directly creating
the possible objects that satisfy the given conditions, and keeping track of how many there
are.

Example 7.1. How many ways are there to choose a boy and a girl from a class of 12 boys
and 13 girls?

Solution. Note the choice of boys is separate from the choice of girls. Thus, for every boy we
choose, we can then choose 13 corresponding girls, giving a total of 12 · 13 = 156. 

Example 7.2. The Committee of Everaise needs to split 3 unique jobs among 8 staff
members. If each staff member can do as many jobs as they please, how many ways are
there to assign the jobs?

Solution. For each job, we choose who can do the job, for which there are 8 people. As a
result, there are 8 · 8 · 8 = 512 possibilities. 

Example 7.3 (2015 AMC 8). How many integers between 1000 and 9999 have four distinct
digits?

Solution. We construct such 4 digit numbers by choosing each digit. For the leftmost digit,
there are 9 such possibilities (excluding 0). The next digit has 9 such possibilities, excluding
the leftmost digit. The following digit has 8 possibilities as it must be distinct from the leftmost
two. The last digit similarly has 7 possibilities, giving for a total of 9 · 9 · 8 · 7 = 4536 such
integers. 

Example 7.4. Let a word be a string of letters that alternate between consonants and
vowels. In terms of n, how many words of length n are there that start with a consonant?

Solution. There are 21 consonants and 5 vowels. If a word starts with a constant, then it must
alternate as consonant, vowel, consonant, etc. We can then construct a word by choosing each
letter.

If n is odd, then we also end with a consonant, so letting n = 2k + 1, there are 21k+1 · 5k
such words. If n = 2k is even, then we have 21k · 5k many words. 

1
Math Competitions I Everaise Academy

Exercise 7.5. A palindrome is a word that reads the same forwards and backwards. How many
3-letter palindromes are there? 4-letter? Can you generalize?

7.2 Casework
Casework is essentially organized constructive counting: we split a problem into several smaller
problems (the “cases”) with restrictions that make them easier to count, and then we add them
up at the end to get the final answer.

Casework can often be very bashy, but on the flip side is useful for solving a huge number
of counting problems that appear on the AMC/AIME. One of the most important skills in
competition math is to be able to quickly determine whether or not a problem can feasibly be
solved with casework within the time limit. This intuition can only be gained through practice.

An important warning is that cases must be independent: otherwise, we could poten-

tially count a particular possibility either more than once (i.e. overcount) or not at all (i.e.
undercount). Let’s take a look at an actual problem:

Example 7.6 (2004 AIME II). A jar has 10 red candies and 10 blue candies. Terry picks two
candies at random, then Mary picks two of the remaining candies at random. Given that
the probability that they get the same color combination, irrespective of order, is m/n,
where m and n are relatively prime positive integers, find m + n.

Solution. We use casework on the candies that Terry chooses.

Case 1: Terry picks out 2 red candies. He can pick out 2 red candies with probability
10 9 9
· = ,
20 19 38
and the probability that Mary does too after Terry has picked his two red candies is
8 7
· .
18 17
14
Thus, the probability that Mary and Terry both pick two red candies is .
323
Case 2: Terry picks out 1 red and 1 blue candy. Note that it doesn’t matter which order he
picks them due to symmetry, so we just need the second ball to be different. He will pick
out this particular combination with
20 10
·
20 19
probability and Mary will pick out 1 red and 1 blue with
18 9
·
18 17
90
probability, so the probability that both pick out these combinations is .
323
Case 3: Terry picks out 2 blue candies The probability that both pick 2 blue candies is the
same as the probability of both picking out 2 red candies, so we just multiply the number
we got in the first case by 2 for this last case.

2
Math Competitions I Everaise Academy

Summing up the probabilities gives

90 14 118
+2· = .
323 323 323


Let’s move onto another example:

Example 7.7. The numbers 1447, 1005, and 1231 have something in common: each is a
four-digit number beginning with 1 that has exactly two identical digits. How many such
numbers are there?

Solution. Looking at the given examples, we notice two ‘types’ of integers: one where the 1 is
the repeated digit, and the other where a different digit is repeated twice. Hence, this gives us
the idea of casework.
Case 1: 1 is the repeated digit. There are 3 places to put the other 1 as we must start with a
1. In the other two spots, we have 9 · 8 = 72 ways to fill up the other two digits, as they
must be distinct from 1, so we have 216 different integers under this case.
Case 2: 1 is not repeated. We again must choose 2 other digits, similarly with 72 different
ways. Now, if our digits are x and y, we have 3 ways to arrange them:

1xxy
1xyx
1yxx

so we end up with another 216 different integers.

Summing them up gives our answer of 216 + 216 = 432. 

Video Example 7.8. There are 5 yellow pegs, 4 red pegs, 3 green pegs, 2 blue pegs, and 1
orange peg on a triangular peg board. In how many ways can the pegs be placed so that
no horizontal row or vertical column contains two pegs of the same color?

Solution. Watch https://youtu.be/-pty0Yoz1yk for the solution to this problem! 

Exercise 7.9 (2006 AMC 12). A bug starts at one vertex of a cube and moves along the edges
of the cube according to the following rule. At each vertex the bug will choose to travel along
one of the three edges emanating from that vertex. Each edge has equal probability of being
chosen, and all choices are independent. What is the probability that after seven moves the bug
will have visited every vertex exactly once?

Exercise 7.10 (2005 AMC 10). How many three-digit numbers satisfy the property that the
middle digit is the average of the first and the last digits?

7.3 Complementary Counting

Casework and constructive counting aren’t always the best approaches. There can be times
when there are just too many possibilities to consider. But, if we know the total amount of

3
Math Competitions I Everaise Academy

cases, then we can just count the cases that we don’t want, and then subtract this from the total
number of cases to count what we do want. You can think of this as taking the complement of
a subset.

Example 7.11. How many 4 digit binary strings have at least one 0, assuming a binary
string can start with a 0?

Solution. It would be messy to count this directly, as we’d have to keep track of how many
0’s there are and their placement in the overall string. However, note there are 24 = 16 total 4
digit binary strings as each string either has 0 or a 1, and there only exists 1 string without a 0
(namely, 1111). Thus, there are 16 − 1 = 15 binary strings with at least one 0.

Putting this in a set perspective, our set was every 4 digit binary string. The condition was
having at least one 0, so our original set was split into two subsets: ones with at least one 0
and ones without a 0. 

Example 7.12 (2006 AMC 10). How many four-digit positive integers have at least one
digit that is a 2 or a 3?

Solution. Again, there’s no need to go through all the cases where we have perhaps one 2
no 3s, two 2 and one 3, etc. when we can just count the numbers without a 2 or 3. We have
9 · 10 · 10 · 10 = 9000 four-digit numbers, and the amount of four-digit integers without a 2 or 3
is 7 · 8 · 8 · 8 = 3584, so our answer is simply 5416. 

We will finish off complementary counting with a harder example.

Example 7.13 (2017 AIME II). Find the number of subsets of {1, 2, 3, 4, 5, 6, 7, 8} that are
subsets of neither {1, 2, 3, 4, 5} nor {4, 5, 6, 7, 8}.

Solution. We first need to have a way to count the number of subsets. If we want to make a
subset, either an element from the original set is in the subset or it isn’t in it, so this means we
have 2n subsets for a set with n integers.

So, with complementary counting, we want to count the number of subsets that are subsets
of {1, 2, 3, 4, 5} or {4, 5, 6, 7, 8} and subtract them from 28 = 256, the total number of subsets
of the original set.

Each set has 5 elements, so each set has 25 subsets and combined gives us 64 subsets. However,
since {4, 5} overlap between the two sets, we inevitably overcount the total number of subsets
we need to subtract. Since {4, 5} has 4 subsets, our final answer is 256 − 64 + 4 = 196. 

Concept. Remember that at the end of the day, you still need extensive constructive
counting skills to really nail counting problems, but complementary counting is just another
strategy to make your constructive counting more efficient. In general, if you feel that
counting the complement involves less cases, you should go for this approach.

4
Math Competitions I Everaise Academy

Exercise (2008 AMC 12). A parking lot has 16 spaces in a row. Twelve cars arrive, each of
which requires one parking space, and their drivers chose spaces at random from among the
available spaces. Auntie Em then arrives in her SUV, which requires 2 adjacent spaces. What
is the probability that she is able to park?

7.4 Committees and Combinatorial Identities

Committees are an extension of constructive counting with a crucial distinction: the order in
which the elements are chosen doesn’t matter. Through our exploration of committees, we will
also look at combinations and identities involving them.

First consider the following example:

Example 7.14. The Math Club of Newton High School has 8 board members. They must
elect a committee of 3 people to serve as directors. How many ways are there to do this?
Note that there is no difference between the director positions.

Solution. At first glance, this may seem like a simple constructive counting problem that we
have already done. There are 8 choices for the first director, 7 for the second, and 6 for the
third– so our answer should be 8 · 7 · 6.

However, we have overcounted; the 3 director positions are not distinct. For example, choosing
Aspara, then Brussel, then Kale as our directors is the same choosing Kale, then Brussel, then
Aspara, but we counted both in our previous calculation.

So, how many times have we overcounted? Suppose one of our possible committees is As-
para, Brussel, and Kale. There are 3! = 6 ways to order the following 3 people, each of which
were counted in our original calculation. In other words, we counted each possible committee 6
times. Thus, the number of possible committees is equal to
8·7·6
= 56.
3·2·1


Picking a few elements from a set of elements where the order in which they are chosen doesn’t
matter is a common theme in combinatorics problems. Note that if a problem uses words such
as “committee” or “combination,” it likely implies that order does not matter.

Example 7.15. Find a general formula for the number of ways to pick a committee of m
people from a pool of n people.

Solution. First, we must pick m people in a constructive counting manner, for which there are

n · (n − 1) · · · · (n − m + 1)

ways to do so. We can rewrite this as

n!
(n − m)!

5
Math Competitions I Everaise Academy

Then, we must divide to compensate for overcounting. We counted each possible committee m!
times because we counted every possible permutation of each committee. Therefore, we must
divide by m!. The number of ways to pick a committee of m people from a pool of n people is
n!
.
(n − m)!m!

This notation is slightly messy, so it is convention to use the following notation. For nonnegative
integers n, m where n ≥ m,  
n n!
= .
m (n − m)!m!
We call such a notation a binomial.
 
n
is also verbally referred to as “n choose m” because it is the number of ways you can
m
choose m elements from a set of n elements with no regards to the order in which they are
chosen.
Remark. When simplifying with fractions involving factorials, make sure to cancel out as many
factors as possible between the numerator and denominator before multiplying anything.
We now present important combinatorial identities involving binomials.

Theorem 7.16 (Pascal’s Identity). For integers n, r Pascal’s Identity asserts

     
n n−1 n−1
= + .
r r r−1

Proof. We present a counting approach. Consider a
group of n people from which we must form
a committee of r members. This can be done in nr ways.

Additionally, consider a specific person Mateo. Any committee can either contain
 Mateo
 or
n−1
not contain Mateo. The number of ways for a committee to contain Mateo is , since
r
we choose r people out of the remaining n − 1.

If a committee contains Mateo, then we nowmust choose

 r − 1 remaining members from the
n−1
remaining n − 1 people, which can be done in ways. As a result, since both expressions
r−1
count the number of committees of r people formed from n people, we have
     
n n−1 n−1
= + .
r r r−1

Exercise 7.17. Verify Pascal’s identity algebraically with the definition of binomials.

A corollary and important result from Pascal’s Identity is the Hockey Stick Identity:

6
Math Competitions I Everaise Academy

Theorem 7.18 (Hockey Stick Identity).

         
r r+1 r+2 n n+1
+ + + ··· + = .
r r r r r+1

Proof. Indeed, the result comes from repeatedly applying Pascal’s Identity. We have that
               
r r+1 r+2 n r+1 r+1 r+2 n
+ + + ··· + = + + + ··· +
r r r r r+1 r r r
     
r+2 r+2 n
= + + ··· +
r+1 r r
..
= .
   
n n
= +
r+1 r
 
n+1
= .
r+1


     
6 7 12
Exercise 7.19. Calculate + + ··· + .
3 3 3

7.5 Grid Paths

Let’s say we have a person at point A on a 2-dimensional grid trying to reach another point B
on the grid. However, the person can only move across adjacent points on the grid. How many
different paths are there from A to B?

This idea of counting grid paths is very common. We dive into some examples to see how
to solve these kinds of problems.

Example 7.20. Bob is stuck at home, which is located at the origin of an arbitrary
Cartesian coordinate system. He wants to buy some food at the supermarket, which is
3 units up and 4 units left of his home (so at (4, 3)). Because he can only walk across
sidewalks, Bob can only go in directions parallel to the axes. Also, because Bob doesn’t
want to waste time, he wants to travel exactly 7 units. How many ways can he walk to the
supermarket?

We draw a diagram of the grid.

7
Math Competitions I Everaise Academy

Now, note that Bob can only go one unit at a time, and he can only go in the up and right
direction since he can’t travel more than 7 units.

There are several possibilities. He can go up 3 units and left 4 units, go left 4 units then
up 3 units, or some path in between. Let’s model a move up as U and a move right as R. Since
Bob can move up exactly 3 times and he can move right exactly 4 times, his sequence of moves
can be any permutation of 3U ’s and 4R’s.

We’ve done this before! How many ways can you arrange 3 U s and 4 Rs?
We can just choose
which of the seven positions will contain a U , so the number of paths is 73 = 35 .

Exercise 7.21. Show that the original problem and our new problem of arranging U ’s and R’s
are in a one-to-one correspondence.

There can also be restrictions that can make the problem trickier:

Example 7.22. Assume the same problem as last time, but there is a police station at
(2, 1) and Bob does not want to be at that point. How many paths can Bob take en route
to the supermarket?

Solution. Since it’s more straightforward to count paths crossing through the police station,
we’ll use complementary counting.

To do this, we need to find how many paths there are from B to P and multiply this by
the number of paths from P to S; since every path we’re looking for passes through the po-
lice station, it must be a composition of a path going to the police station and a path leading out.
  
3 4
There are = 18 paths that cut through the police station. (Verify the results yourself.)
1 2
Thus, there are 35 − 18 = 17 ways to avoid the police department. 

We can also have irregular grid patterns.

Example 7.23. Bob moves to another city, where the grid pattern is shown below. If he
only goes up and right, how many paths does Bob have to get to the supermarket?

8
Math Competitions I Everaise Academy

Solution. It appears that our current method cannot handle this complex system. When all
else fails, we can use a recursive approach.

Label a number at every point that signifies how many paths lead up to that point. This
number can be determined by adding the numerical values of the points immediately below and
to the left of the point, since a point can be reached by taking any path to the point below then
moving up, or by taking any path to the point to the left then moving right, and in no other
way since the only possible moves are up or right.

We will illustrate how this works. First, we can fill in the edges with 1 since there’s only
one possible way to travel to any of the edge points:

We can fill in the rest by adding the two numbers that lead to it (the number to the left and
the number below). Verify that the numbers we filled in are correct.

Evidently, the answer is 17. 

7.6 Stars and Bars

Stars and Bars is a method of counting essential to problem solving. We begin with a motivating
example:

Example 7.24. There are three dogs and you have ten identical toys. How many ways are
there to distribute all of the toys to the dogs?

9
Math Competitions I Everaise Academy

Solution. This seems like a hassle to count directly; we’d have to split by cases depending on
how many toys go to each dog.

Instead, we can create a depiction of the ten toys as circles:

How can we divvy up these toys? We can start by using two dividers between the circles to
distinguish between the three dogs. Each divider will be represented by a single line.

In the above example, we gave the first dog 2 toys, the second dog 0 toys and the third dog
with 8 toys.

Amazingly, just by moving the dividers, we can count

 thenumber
 of ways to distribute the
10 + 2 12
toys. We can find the answer as follows. There are = = 66. 
2 2

Exercise 7.25. Show that the original problem and the new problem of ordering dividers and
circles are in a one to one correspondence.

With this, we can easily generalize.

Theorem 7.26 (Stars and Bars Formulas). Suppose we are given n objects to be distributed
among r people. If each person must receive a positive number of objects, there are
 
n−1
r−1

Ways to distribute the objects among the r people. If each person receives a nonnegative
number of objects (i.e a person can receive 0 objects), there are
 
n+r−1
r−1

Ways to distribute the objects.

Now let’s apply this to a hard problem:

Example 7.27 (2011 AIME II). Ed has five identical green marbles, and a large supply
of identical red marbles. He arranges the green marbles and some of the red ones in a
row and finds that the number of marbles whose right hand neighbor is the same color as
themselves is equal to the number of marbles whose right hand neighbor is the other color.
An example of such an arrangement is GGRRRGGRG.

Let m be the maximum number of red marbles for which such an arrangement is pos-
sible, and let N be the number of ways he can arrange the m + 5 marbles to satisfy the
requirement. Find N .

10
Math Competitions I Everaise Academy

Solution. A simpler way to put the problem condition is that the number of color continua-
tions (GG and RR) found in the row must be the same as the number of color switches (GR and
RG). Because of this, if we wanted to add as many red marbles as we could, we would be limited
by the number of color switches. Therefore, we want this limit of color switches to be rather high.

The maximum number of color switches is 10, found in the sequence RGRGRGRGRGR. We
have 0 color continuations here. Now, we should add more red marbles to the end to increase
the amount of these continuations. We end up with 16 red marbles.

Now we have to order these to keep the equality of continuations and switches. We can place
these red marbles anywhere but since they are indistinguishable, we have to use stars and bars
to count them. Note that we have 10 stars, which are the unused red marbleswe wish to place,
10 + 5
and 5 bars, which are the green marbles. This gives us an answer of = 3003. 
5

Exercise 7.28. How many solutions are there to the equation a + b + c + d ≤ 14 where a, b, c,
and d are non-negative integers?

7.7 Homework Problems

Problem 7.1 (2009 AMC 10). [3] How many 7-digit palindromes (numbers that read the same
backward as forward) can be formed using the digits 2, 2, 3, 3, 5, 5, 5?

Problem 7.2 (2012 AIME II). [5] At a certain university, the division of mathematical sci-
ences consists of the departments of mathematics, statistics, and computer science. There are
two male and two female professors in each department. A committee of six professors is to
contain three men and three women and must also contain two professors from each of the
three departments. Find the number of possible committees that can be formed subject to
these requirements.

Problem 7.3 (2017 AMC 10). [5] Alice refuses to sit next to either Bob or Carla. Derek
refuses to sit next to Eric. How many ways are there for the five of them to sit in a row of 5
chairs under these conditions?

Problem 7.4 (2006 AIME II). [7] Let (a1 , . . . , a12 ) be a permutation of (1, . . . , 12) for which
a1 > a2 > a3 > a4 > a5 > a6 and a6 < a7 < a8 < a9 < a10 < a11 < a12 . An example of such a
permutation is (6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12). Find the number of such permutations.

Problem 7.5 (2013 AIME I). [7] In the array of 13 squares shown below, 8 squares are colored
red, and the remaining 5 squares are colored blue. If one of all possible such colorings is chosen
at random, the probability that the chosen colored array appears the same when rotated 90
degrees around the central square is n1 , where n is a positive integer. Find n.

11
Math Competitions I Everaise Academy

Problem 7.6 (2003 AMC 12). [7] Objects A and B move simultaneously in the coordinate
plane via a sequence of steps, each of length one. Object A starts at (0, 0) and each of its steps is
either right or up, both equally likely. Object B starts at (5, 7) and each of its steps is either to
the left or down, both equally likely. The probability that the objects meet can be represented
as m/2n for positive integers m and n where m is not divisible by 2. What is m + n?

Problem 7.7 (2013 AMC 10). [8] Central High School is competing against Northern High
School in a backgammon match. Each school has three players, and the contest rules require
that each player play two games against each of the other school’s players. The match takes
place in six rounds, with three games played simultaneously in each round. In how many
different ways can the match be scheduled?

Problem 7.8 (2012 AMC 10). [8] A 3 × 3 square is partitioned into 9 unit squares. Each unit
square is painted either white or black with each color being equally likely, chosen independently
and at random. The square is then rotated 90 ◦ clockwise about its center, and every white
square in a position formerly occupied by a black square is painted black. The colors of all other
squares are left unchanged. The probability the grid is now entirely black can be represented
as pq , where p and q are relatively prime positive integers. What is p + q?

Problem 7.9 (2018 AMC 12). [8] A scanning code consists of a 7 × 7 grid of squares, with
some of its squares colored black and the rest colored white. There must be at least one square
of each color in this grid of 49 squares. A scanning code is called symmetric if its look does
not change when the entire square is rotated by a multiple of 90◦ counterclockwise around its
center, nor when it is reflected across a line joining opposite corners or a line joining midpoints
of opposite sides. What is the total number of possible symmetric scanning codes?

Problem 7.10 (2007 AIME I). [10] In a 6 x 4 grid (6 rows, 4 columns), 12 of the 24 squares
are to be shaded so that there are two shaded squares in each row and three shaded squares in
each column. Let N be the number of shadings with this property. Find the remainder when
N is divided by 1000.

Problem 7.11 (2018 PUMaC). [10] In an election between A and B, during the counting of
the votes, neither candidate was more than 2 votes ahead, and the vote ended in a tie, 6 votes
to 6 votes. Two votes for the same candidate are indistinguishable. In how many orders could
the votes have been counted? One possibility is AABBABBABABA.

12