MathCount with Proofs AwesomeMath Summer Program 2024

n


HANDOUT #3: One Million Uses of k

1 Binomial Theorem
Pascal’s Triangle: Pascal’s Triangle is a sequence of rows of positive integers. The top row has a 1. The
next row has two 1s. Each row thereafter has one more number than the row above it, begins and ends with
1s, and the numbers between the 1s are each the sum of the two numbers above it in the previous row. If
the top row is
row zero, and the n + 1 numbers in row n are numbered 0, 1, 2, ..., n, then entry k in row n
is equal to nk .

h
Binomial Theorem: The Binomial Theorem tells us how to expand the n-th power of a binomial. In
particular, (x + y)n expands to
be a sum of terms of the form xk · y n−k . The theorem tells us that the
coefficient of the k-th term is nk . This is easy to see since each term of the form xk · y n−k results from the

at
product (x + y)(x + y)(x
+ y) · · · (x + y) where we select an x from each of k of the (x + y) factors, and this
can be done is exactly nk ways since we have to select k of the n factors.

Formally,

Theorem 1.1: Binomial Theorem

Let n be a non-negative integer, then

n
(x + y) =
 
n 0 n
0
x y +
 
n 1 n−1
1
x y +
 
n 2 n−2
2
x y
eM
+ ··· +
 

n
x y =
n  
n n 0 X n k n−k
k
x y .
k=0
om
EXAMPLES: (x + y)3 = y 3 + 3xy 2 + 3x2 y + x3 .
(x + y)5 = y 5 + 5xy 4 + 10x2 y 3 + 10x3 y 2 + 5x4 y + x5 .

Example 1.1

What is the x4 y term in the expansion of (2x − y)5 ?

es

5


ANSWER: 4 (2x)4 (−y) = −5 · 16 · x4 y = −80x4 y.

Paths on a Grid: Consider the grid below showing three rows and four columns of 1 by 1 squares. We
would like to count the number of paths from the lower left corner of the grid to the upper right corner of the
Aw

grid that follow the edges of the squares whose total length is 7. For example, one could follow a path that
moves four squares to the right followed by moving three squares up, or one could move one square to the
right, one square up, one square to the right, one square up, one square to the right, one square up, and one
square to the right. Any path that satisfies the conditions consists of four moves to the right and three moves
up, and these moves can occur in any order. We could symbolize the paths with R representing moves to
the right and U representing moves up. The two paths just mentioned would be RRRRUUU and RURURUR.

The number of paths is then the number of arrangements of the 7 letters RRRRUUU. Since there are 7
positions and 3 of them must be U, there are 73 = 35 paths.

Example 1.2

How many paths of length 8 are there from the lower left to the upper right in a 4 by 4 grid?

1
MathCount with Proofs AwesomeMath Summer Program 2024

8


ANSWER: 4 = 70.

h
Example 1.3

at
How many of those paths pass through the center point of the grid?

4 2


ANSWER: Such a path must go through a 2 by 2 grid twice, so there are 2 = 62 = 36.

2 Sticks and Stones

eM
Sticks and Stones: The sticks and stones technique is the standard approach for counting the number of
ways n indistinguishable objects can be distributed to k distinguishable containers. We let n stones
represent the n indistinguishable objects and let k − 1 sticks represent divisions between the k containers
om
lined up. For example, if we want to know the number of ways of distributing 10 candies to 4 children, we
would represent the situation with 10 stones and 3 sticks. Note that in this problem we are not interested
in which candies go to which child, only how many candies go to each child. A possible way of distributing
the candies would be 3 candies to the first child, 2 to the second, 4 to the third, and 1 to the last. We would
represent this with sticks and stones by “◦ ◦ ◦| ◦ ◦| ◦ ◦ ◦ ◦|◦”. Note that we get exactly one way to distribute
candies for each arrangement of the sticks and stones. How many arrangements are there of the sticks and
stones? There are 10 stones and 3 sticks, so there are 13 positions, and we want to count the
number of
ways of choosing the positions for the 10 stones (or the 3 sticks), and this can be done in 13
es

10 = 286 ways.
The number of ways of distributing n indistinguishable objects to k distinguishable containers is n+k−1


n .

The number of rearrangements of RRRRUUU calculated above can be thought of as a sticks and
stones
problem. Think of the U’s as sticks and distribute 4 R’s among them. The number of ways is 4+3 = 35 as
Aw

3
before.

Example 2.1

How many ways can a camp counselor distribute six logs to three campfires?

6+3−1


ANSWER: 6 = 28 ways.

Example 2.2

What if each campfire requires at least one log?

ANSWER: First place one log on each fire. Then distribute the remaining three logs to the three fires

2
MathCount with Proofs AwesomeMath Summer Program 2024

3+3−1


in 3 = 10 ways.

Example 2.3

What if no fire is to receive more than 3 logs?

ANSWER: We can count the number of ways that a fire can get at least 4 logs. To do this we first
choose the fire
which gets 4 logs (3 ways). Then we choose a way to distribute two logs to the three
fires 2+3−1


2 = 6 ways . It is important to note that it is impossible for more than one fire to receive 4
logs. If it were possible, this counting problem would be more difficult. The final answer is 28−3·6 = 10 ways.

h
Ways to Sum: How many ordered triples (x, y, z) of nonnegative integers have the property that
x + y + z = 8? For example, (1,5,2) and (4,4,0) are two such triples. This problem can be solved using the
sticks and stones technique since you can think about the problem as having eight 1s which get distributed
to the three variables x, y, and z. Thus, the number of triples is 8+3−1

at


8 = 45. What if the variables must
be positive integers? Then we can allot one 1 to each variable and distribute the remaining five 1s to the
three variables in 5+3−1


5 = 21.

Selections with Repetitions: How many different results can you get from rolling four dice? Here the

outcomes is k+n−1k


.
k elements from A
eM
result for each individual die is a selection from the set {1, 2, 3, 4, 5, 6} although repetitions are allowed. The
result from rolling four dice is just a reporting of how many 1s, how many 2’s, how many 3’s, and so forth, we
got. For example, on one roll of four dice, you could get 2,3,3,6. How many results are possible? Let xk be
the number of times that a die appears with the number k. Then after four rolls, x1 +x2 +x
where each xk ≥ 0. From above, we see that the number of solutions to this is 4+6−1
if set A has n elements, and we select with repetition allowed,
4
the

3 +x4 +x5 +x6 = 4
= 126. In general,
number of possible
om
3 Multinomial Coefficients
Multinomial Coefficients: The Binomial Theorem tells how to take the nth power of a binomial. Similarly,
n

a b c
the Multinomial Theorem tells how to expand (x + y + z)n as a sum of terms of the form a,b,c x y z
n
es

n!


where a + b + c = n. The theorem says that the multinomial coefficient a,b,c = a!b!c! . This is easy to see
since each term of the form xa y b z c results from the product (x + y + z)(x + y + z)(x + y + z) · · · (x + y + z)
where we select an x from each of
a of the
(x + y + z) factors, y from b of the factors, and z from the other
c factors. This can be done in na · n−a n


b ways, but this is equal to the multinomial coefficient a,b,c . In
Aw

n n! n n




general, if a + b + c + · · · + k = n, then a,b,c,...,k = a!b!c!···k! . Note that k = k,n−k .

Example 3.1

What is the coefficient of xy 3 z 2 in the expansion of (x + y + z)6 ?

6 6! 720


ANSWER: 1,3,2 = 1!3!2! = 1·6·2 = 60.

Example 3.2

In how many ways can eight different books be distributed to 4 people so each person receives two
books?

3
MathCount with Proofs AwesomeMath Summer Program 2024

ANSWER: We must count the number of ways of assigning
two books to person 1, two to person 2,
8 8!
two to person 3, and two to person 4. This can be done in 2,2,2,2 = 2·2·2·2 ways. Note that this is also the
number of ways of permuting the digits 11223344 because we can think of the books being lined up, and the
tags 1,1,2,2,3,3,4,4 being permuted to show which books go to which people.

Some Properties of nk : If you add all the numbers in row n of Pascal’s Triangle, you get 2n . For exam-

ple, the numbers in the fourth row are 40 + 41 + 42 + 43 + 44 = 1+4+6+4+1 = 16 = 24 . This can be seen

in two ways. First, the sum of the numbers in row n give the number of subsets of a set with n elements of all
the sizes 0, 1, 2, . . . n and so, they must add to the total number
Pn of subsets of the set which is 2n . It can also
n
n


be seen from the Binomial Theorem which shows (1 + 1) = k=0
k . Similarly,
if we alternate signs of the
coefficients in the nth row of Pascal’s triangle when n > 0, we get n0 − n1 + n2 −· · · (−1)n nn = (1−1)n = 0.

h
at
eM
om
es
Aw

4
MathCount with Proofs AwesomeMath Summer Program 2024

4 PROBLEM SET #3
1. Generate Pascal’s Triangle through row 10.
2. Binomial Coefficients

A. What is the x2 y 3 term in the expansion of (x + 2y)5 ?

B. What is the x3 y 3 term in the expansion of (2x − 3y)6 ?
C. What is the x3 y 3 term in the expansion of (x − 2y + 3)8 ?
3. Lattice Grids

h
A. On a 4 by 6 grid, how many paths of length 10 are there from the lower left corner to the upper
right corner?
B. How many of these paths go through the center point of the grid?

at
C. On a 6 by 6 grid, how many paths of length 12 are there from the lower left corner to the upper
right corner?
D. How many of these paths do not touch the park which is a 2 by 2 square in the center of the grid?
4. Arranging Plates

eM
A. In how many ways can you arrange five red plates and three white plates in a row?
B. In how many of these arrangements are no two of the white plates next to each other?
C. In how many ways can you arrange four red plates, three white plates, and two blue plates in a
row?
D. In how many of these arrangements are there at least one red and one blue plate between each
om
pair of the white plates?

5. How many solutions are there to x + y + z = 10 where

A. the variables are nonnegative integers?
B. the variables are positive integers?
C. the variables are positive integers less than 6?
es

D. the variables are integers greater than −3?

6. You have a bag with one red, one blue, and one green marble. How many sequences of colors can get
if you select a marble from the bag 8 times with replacement?
Aw

7. (2017 AMC 12 B) Call a positive integer monotonous if it is a one-digit number or its digits, when read
from left to right, form either a strictly increasing or a strictly decreasing sequence. For example, 3,
23578, and 987620 are monotonous, but 88, 7434, and 23557 are not. How many monotonous positive
integers are there?
8. (2020 AIME I) A club consisting of 11 men and 12 women needs to choose a committee from among
its members so that the number of women on the committee is one more than the number of men on
the committee. The committee could have as few as 1 member or as many as 23 members. Let N be
the number of such committees that can be formed. Find the sum of the prime numbers that divide
N.
9. (2009 Purple Comet) How many ordered triples (a, b, c) of odd positive integers satisfy a + b + c = 25?
10. (1989 AIME) Ten points are marked on a circle. How many distinct convex polygons of three or more
sides can be drawn using some (or all) of the ten points as vertices? (Polygons are distinct unless they
have exactly the same vertices.)

5
MathCount with Proofs AwesomeMath Summer Program 2024

11. (2013 Purple Comet) How many ordered triples (a, b, c) of positive integers satisfy a ≤ b ≤ c and
a · b · c = 1000?
12. (2013 Purple Comet) In how many ways can you write 12 as an ordered sum of integers where the
smallest of those integers is equal to 2? For example, 2 + 10, 10 + 2, and 3 + 2 + 2 + 5 are three such
ways.

13. (2016 AIME II) Find the number of sets {a, b, c} of three distinct positive integers with the property
that the product of a, b, and c is equal to the product of 11, 21, 31, 41, 51, and 61.
14. (2018 AIME II) Find the number of functions f (x) from {1, 2, 3, 4, 5} to {1, 2, 3, 4, 5} that satisfy
f (f (x)) = f (f (f (x))) for all x in {1, 2, 3, 4, 5}.

h
15. (2018 Purple Comet) The following diagram shows a grid of 36 cells. Find the number of rectangles
pictured in the diagram that contain at least three cells of the grid.

at
eM
16. (2021 AIME I) Find the number of ways 66 identical coins can be separated into three nonempty piles
om
so that there are fewer coins in the first pile than in the second pile and fewer coins in the second pile
than in the third pile.
17. (2022 AIME I) For any finite set X, let |X| denote the number of elements in X. Define
X
Sn = |A ∩ B|,
es

where the sum is taken over all ordered pairs (A, B) such that A and B are subsets of {1, 2, 3, . . . , n}
with |A| = |B|. For example, S2 = 4 because the sum is taken over the pairs of subsets

(A, B) ∈ {(∅, ∅), ({1}, {1}), ({1}, {2}), ({2}, {1}), ({2}, {2}), ({1, 2}, {1, 2})} ,
Aw

giving S2 = 0 + 1 + 0 + 0 + 1 + 2 = 4. Let SS2021

2022
= pq , where p and q are relatively prime positive integers.
Find the remainder when p + q is divided by 1000.
18. (2020 Wisconsin Math Talent Search) We are given a 2020-sided convex polygon. We want to select
three distinct edges of the polygon, so that if we go around the edges in clockwise order, at least two
unselected edges lie between every pair of selected edges. In how many different ways can we select
the three edges?

6
MathCount with Proofs AwesomeMath Summer Program 2024

5 Homework #3
1. During football season, 25 teams are ranked by three reporters (Alice, Bob and Cecil). Each reporter
assigned all 25 integers (1 through 25) when ranking the twenty-five teams. A team earns 25 points
for each first-place ranking, 24 points for each second-place ranking, and so on, getting one point for
a 25th place ranking. The Hedgehogs earned 27 total points from the three reporters. How many
different ways could the three reporters have assigned their rankings for the Hedgehogs? One such way
to be included is Alice - 14th place, Bob - 17th place and Cecil - 20th place.

2. A box has ki letters of type i, for 1 ≤ i ≤ n. Count the words (using all letters in the box) that have
no two letters of type n adjacent.

h
3. Esmeralda has a pile of 100 stones. She divides this stack into two new piles and then multiplies the
quantities of stones in these two new piles and writes the product on the board. She then chooses a
stack with more than one stone and repeats this: the stack is divided into two, the amounts of stones

at
in these two piles are multiplied and the product is written on the board. This operation continues
until only piles with 1 stone are obtained. What are the possible values of the sum of all the products
written on the board?

eM
om
es
Aw

7
MathCount with Proofs AwesomeMath Summer Program 2024

PROBLEM SET #3 ANSWERS:

1. Generate Pascal’s Triangle through row 10.
ANSWER:

1
1 1
1 2 1
1 1 3 3
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

h
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

at
1 10 45 120 210 252 210 120 45 10 1

2. Binomial Coefficients
A. What is the x2 y
3 term in the expansion of (x + 2y)5 ?
ANSWER: 53 23 = 80

8


eM
B. What is the x3 y
3 term in the expansion of (2x − 3y)6 ?
ANSWER: 63 23 (−3)3 = −4320
C. What is the x3 y 3 term in the expansion of (x − 2y + 3)8 ?
ANSWER: 3,3,2 (−2)3 32 = −40,320
3. Lattice Grids
om
A. On a 4 by 6 grid, how many paths of length 10 are there from the lower left corner to the upper
right corner?
ANSWER: 10


4 = 210
B. How many of these paths go through the center point of the grid?

2
ANSWER: 52 = 100
es

C. On a 6 by 6 grid, how many paths of length 12 are there from the lower left corner to the upper
right corner?
ANSWER: 12


6 = 924
D. How many of these paths do not touch the park which is a 2 by 2 square in the center of the grid?
Aw

ANSWER:
Such


a path must go through point (0, 6), (1, 5), (5, 1), or (6, 0). Therefore, there are
2 60 60 + 61 61 = 74 such paths.

4. Arranging Plates
A. In how many ways

can you arrange five red plates and three white plates in a row?
ANSWER: 83 = 56
B. In how many of these arrangements are no two of the white plates next to each other?
ANSWER: 3+3


3 = 20
C. In how many ways can you arrange four red plates, three white plates, and two blue plates in a
row?
9


ANSWER: 4,3,2 = 1260
D. In how many of these arrangements are there at least one red and one blue plate between each
pair of the white plates?
ANSWER: The answer is 126 − 65 = 61.

8
MathCount with Proofs AwesomeMath Summer Program 2024

5. How many solutions are there to x + y + z = 10 where

A. the variables are nonnegative integers?
ANSWER: 10+2


2 = 66
B. the variables are positive integers?
ANSWER: 7+2


2 = 36
C. the variables are positive
integers less than 6?
ANSWER: 36 − 3 2+2 2 = 18
D. the variables are integers greater than −3?
16+2


ANSWER: Add 2 to each variable to get 2 = 163.

6. You have a bag with one red, one blue, and one green marble. How many sequences of colors can you

h
get if you select a marble from the bag 4 times with replacement?
ANSWER: 34 = 81

at
7. (2017 AMC 12 B) Call a positive integer monotonous if it is a one-digit number or its digits, when read
from left to right, form either a strictly increasing or a strictly decreasing sequence. For example, 3,
23578, and 987620 are monotonous, but 88, 7434, and 23557 are not. How many monotonous positive
integers are there?
ANSWER: 1524

eM
8. (2020 AIME I) A club consisting of 11 men and 12 women needs to choose a committee from among
its members so that the number of women on the committee is one more than the number of men on
the committee. The committee could have as few as 1 member or as many as 23 members. Let N be
the number of such committees that can be formed. Find the sum of the prime numbers that divide
N.
ANSWER: 81
om
9. (2009 Purple Comet) How many ordered triples (a, b, c) of odd positive integers satisfy a + b + c = 25?
ANSWER: Subtract 1 from each variable and then divide each by 2 to get the new
equation a′ + b′ +
c′ = 11 where a′ , b′ , and c′ are nonnegative integers. This new equations has 11+2
2 = 78 solutions.
10. (1989 AIME) Ten points are marked on a circle. How many distinct convex polygons of three or more
sides can be drawn using some (or all) of the ten points as vertices? (Polygons are distinct unless they
have exactly the same vertices.)
es

ANSWER: 968

11. (2013 Purple Comet) How many ordered triples (a, b, c) of positive integers satisfy a ≤ b ≤ c and
a · b · c = 1000?
ANSWER: The answer is 100−10
6 + 4 = 19.
Aw

12. (2013 Purple Comet) In how many ways can you write 12 as an ordered sum of integers where the
smallest of those integers is equal to 2? For example, 2 + 10, 10 + 2, and 3 + 2 + 2 + 5 are three such
ways.
ANSWER: 12
can be written as a sum of k integers where the smallest of the k integers is 2 is
11−k 11−2k


k−1 − k−1 . Add these for k = 2, 3, 4, 5, 6 to get 70.

13. (2016 AIME II) Find the number of sets {a, b, c} of three distinct positive integers with the property
that the product of a, b, and c is equal to the product of 11, 21, 31, 41, 51, and 61.
ANSWER: 728
14. (2018 AIME II) Find the number of functions f (x) from {1, 2, 3, 4, 5} to {1, 2, 3, 4, 5} that satisfy
f (f (x)) = f (f (f (x))) for all x in {1, 2, 3, 4, 5}.
ANSWER: 756

9
MathCount with Proofs AwesomeMath Summer Program 2024

15. (2018 Purple Comet) The following diagram shows a grid of 36 cells. Find the number of rectangles

h
pictured in the diagram that contain at least three cells of the grid.

ANSWER: The answer is 441 − 36 − 60 = 345.

at
16. (2021 AIME I) Find the number of ways 66 identical coins can be separated into three nonempty piles
so that there are fewer coins in the first pile than in the second pile and fewer coins in the second pile
than in the third pile.
ANSWER: 331

Sn =
eM
17. (2022 AIME I) For any finite set X, let |X| denote the number of elements in X. Define
X
|A ∩ B|,

where the sum is taken over all ordered pairs (A, B) such that A and B are subsets of {1, 2, 3, . . . , n}
with |A| = |B|. For example, S2 = 4 because the sum is taken over the pairs of subsets
om
(A, B) ∈ {(∅, ∅), ({1}, {1}), ({1}, {2}), ({2}, {1}), ({2}, {2}), ({1, 2}, {1, 2})} ,

giving S2 = 0 + 1 + 0 + 0 + 1 + 2 = 4. Let SS2021

2022
= pq , where p and q are relatively prime positive integers.
Find the remainder when p + q is divided by 1000.
ANSWER: 245

18. (2020 Wisconsin Math Talent Search) We are given a 2020-sided convex polygon. We want to select
es

three distinct edges of the polygon, so that if we go around the edges in clockwise order, at least two
unselected edges lie between every pair of selected edges. In how many different ways can we select
the three edges?
2020·2012·2013
ANSWER: 6
Aw

10