University of Toronto
Faculty of Arts and Sciences
MAT315H1 - F: Introduction to Number Theory
Fall 2023
Homework 10
1 Problems to be submitted
• Make sure you follow all the indications as stated in the syllabus.
• This is the last homework of the course!
• Partitions of integers are objects full of life. Their properties are incredibly diverse and the
theories that have appeared for their study are incredible. In the course we mainly see two:
generating functions and combinatorics of the Ferrer’s Diagrams.
• In this homework we will study the power of these two methods to deduce properties that are
not obvious and that are not easy to do with one of the methods, but accessible with the other.
Part of the goal of this is to understand the concept of these ideas, as they will mix very nicely
in the Pentagonal Number Theorem.
• Problem 1 and 2 are to familiarize ourselves with the way in which the Pentagonal Number
Theorem is used to compute the values p(n).
• In problem 3 we study a partition identity proven by arguments in the Ferrer Diagram. This
is due to Bressoud. The problem itself is based on material of the book ”Integer Partition” by
George E. Andrews and Kimmo Eriksson (section 3.4)
• In problem 4 we study another partition identity that is proven by comparing different gener-
ating functions.
1. In lecture we will find the Pentagonal Numbers. They are defined as
Dj := j(3j − 1)
2
.
for nonnegative integers j. The generalized pentagonal numbers are defined in the same way but
allowing j to be any integer (i.e. including negative ones).
Consider the following figure (modified from the picture of math.net):
1
This shows how to create a pentagon with dots. At each step you add an extra layer to the pentagons.
(a) (2 points) Prove that Dj is the number of points in the j − th step. For example, D3 = 12 and
there are 12 points in the third step.
(b) (2 points) Prove that the generalized pentagon numbers obtained by putting j negative are obtained
by counting the number of interior points in the |j| + 2 step (the red dots). For example, when
j = −2 we obtain the generalized pentagon number 7 and 7 is the number of red dots in the fourth
step.
(c) (1 point) We organize the sequence of Generalized Pentagonal Numbers according to j = 1,−1, 2,−2,
3,−3, ....
Compute the first 10 generalized pentagonal numbers, according to the previous ordering of j (i.e.
up to j = ±5 =), and verify they are obtained as the number of dots described in the previous
parts.
2. (5 points) The following table shows the number of partitions P (n) of the number n for n = 1, 2, ..., 10.
n 1 2 3 4 5 6 7 8 9 10
P (n) 1 2 3 5 7 11 15 22 30 42
Use the recurrence relationship of Euler, deduced from the Pentagonal Number Theorem, to find the
value of P (n) for n = 11, ..., 15. Show your computations.
3. In lecture, when we prove the Pentagonal Number Theorem, we will have to do ”operations” to the
Ferrer’s Diagrams to prove identities. In this problem we practice this idea for another partition identity
problem.
Let N be a positive integer. Consider the following two types of partitions:
1. We say a partition λ of N is evenly excessive if all of its parts are distinct and each of its even
terms is more than twice its number of odd parts.
For example, 2+3+4+3 is not evenly excessive because its number of odd parts is 1 and 2 = 2×1.
However, 3 + 5 + 12 is evenly excessive because all of its parts are distinct and its only even part
is 12 which is bigger than twice the number of odd parts (i.e. bigger than 4).
2. We say a partition is into super distinct parts if all its terms are distinct and their difference is at
least 2.
For example, 2 + 3 + 5 is not into super distinct parts because 2 and 3 do not differ by at least 2
since 3− 2 = 1. However, 2 + 5 + 7 is into super distinct parts.
(a) (1 point) List all partitions of 9. Determine which ones are evenly excessive and which ones are
into super distinct parts.
Page 2
(b) (2 points) Consider a partition λ into super distinct parts and its Ferrer Diagram.
Do the following operation:
1. Starting from the first row until the last one, slide each row to the right so that its beginning
point is exactly two dot spaces below the first point of the previous row.
2. Draw a vertical line in such a way that the last row has exactly one point to the left of this
line, the next row has three, the next five, and so on.
To the right of the line the dots form the Ferrer diagram of some partition λ1 for some integer.
3. Rearrange the rows of this partition λ1 by doing the following: first put the rows with an odd
number of points in descending order and then put the rows with an even number of points
also in descending order. What remains might not be a Ferrers Diagram.
Note: Descending order for how they appeared from the first row to the bottom row.
4. Disappear the vertical line and slide all the rows to the left and align their first dots. Rearrange
the rows so that we obtain a Ferrers Diagram of some parition λ2.
With this process we have constructed out of λ a new partition λ2.
Do this process, step by step, for the following partition of n = 11 :
14 + 11 + 6 + 4 + 1.
(c) (3 points) Explain why if λ is a partition into super distinct parts then λ2 is a partition that is
evenly excessive.
(d) (3 points) Explain the inverse process, that is, if you start from a partitions λ2 that is evenly
excessive, construct a partition λ into super distinct parts by explaining how to construct its Ferrer’s
Diagram by doing the steps in the other direction.
Hint: This is tricky if you do not pay attention. There is akin to detective work and you must
answer three questions: (1) where was the vertical line? (2) What was the order in which the rows
of λ2 were found first, before you arranged them? (3) What was the Ferrer Diagram to the right
of the line of λ? To answer these questions you have to decipher how the choices being made (i.e.
the reordering according to parity) remember the original partition.
(e) (1 point) Prove that the number of partitions of n into super distinct parts equals the number of
partitions of n that are evenly excessive.
Remark: Notice that in both type of partitions, the different parts influence the other parts’ size
or its number of appearance. Hence, it is not easy to write down generating functions for either of
the sequences. Combinatorics of the Ferrer’s Graphs instead work nicely!
4. Let N be a positive integer. Consider the following two types of partitions:
1. We say a partition λ of N is abundant if whenever a part appears in λ then it appears at least
twice.
For example, 2 + 2 + 3 + 3 is abundant but 2 + 3 + 3 is not.
2. We say a partition is good if all its parts are either even or multiples of 3 (possibly both).
For example, 2 + 2 + 3 is good but 2 + 3 + 5 is not good.
(a) (2 points) Justify carefully that the generating function for abundant partitions is
(1 +X2 +X3 + · · · )(1 +X4 +X6 + · · · )(1 +X6 +X9 + · · · ) · · · ,
that is,
∞∏
k=1
(
1 +X2k +X3k +X4k + · · · ) .
(b) (2 points) Prove that we can rewrite the above generating function as
∞∏
k=1
1 +X3k
1−X2k .
Page 3
(c) (4 points) Prove that for each positive integer n, the number of abundant partitions coincides with
the number of good partitions.
Hint: Using the previous part result, cancel each factor of the numerator with an appropriate term
of the denominator.
(d) (2 points) How many good partitions are there for N = 11?
Page 4