MAT315_Fall_2023_Homework_10_Solutions
pdf
keyboard_arrow_up
School
University of Toronto *
*We aren’t endorsed by this school
Course
348
Subject
Mathematics
Date
Nov 24, 2024
Type
Pages
10
Uploaded by HappyStudying7
University of Toronto
Faculty of Arts and Sciences
MAT315H1 - S: Introduction to Number Theory
Winter 2023
Homework 10 Solutions
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 generating functions.
1. In lecture we will find the
Pentagonal Numbers
. They are defined as
KEK
j
:=
j
(3
j
−
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
KEK
j
is the number of points in the
j
−
th
step. For example,
KEK
3
= 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.
Solution:
We do each part separately.
Part (a):
At stage
j
+ 1 we add to the
j
-th figure the outer layer consisting of three sides. Each of these sides has
j
+ 1
dots, but the middle two vertices are counted twice. With this observation we now proceed by induction:
KEK
j
+1
=
KEK
j
+ 3(
j
+ 1)
−
2 =
j
(3
j
−
1)
2
+ 3
j
+ 1 =
3
j
2
+ 5
j
+ 2
2
=
(
j
+ 1)(3(
j
+ 1)
−
1
2
.
This concludes the induction and this part.
Part (b):
From the
KEK
|
j
|
+2
points in the
|
j
|
+ 2 drawing, we must remove the number of points of the outer layer. Each
of these layers has
|
j
|
+ 2 points, but the vertices get counted twice. We thus remove 5 from the count, as there are five
vertices. We thus have that the
j
-generalized pentagonal number is
KEK
|
j
|
+2
−
(5(
|
j
|
+ 2)
−
5) =
(
|
j
|
+ 2)(3(
|
j
|
+ 2)
−
1)
2
−
5
|
j
| −
5
To do this computation, we now write
|
j
|
=
−
j
(recall that the generalized pentagonal numbers are obtained by allowing
j
to be negative). Then we get the count is
(
−
j
+ 2)(3(
−
j
+ 2)
−
1)
2
+ 5
j
−
5 =
(
−
j
+ 2)(
−
3
j
+ 5)
2
+ 5
j
−
5 =
3
j
2
−
5
j
−
6
j
+ 10 + 10
j
−
10
2
=
j
(3
j
−
1)
2
.
Notice this is exactly what we want, as this is the formula for the pentagonal numbers but with
j
negative.
Remark:
If in this formula we now put
−
j
, and put
j
positive, then we get
−
j
(3(
−
j
)
−
1)
2
=
−
j
(
−
3
j
−
1)
2
=
j
(3
j
+ 1)
2
,
which explains why we also say generalized pentagonal numbers/pentagonal numbers are obtained by the formula
j
(3
j
±
1)
2
, j
= 1
,
2
,
3
, ...
Part (c):
We only have to compute
j
= 1
,
−
1
,
2
,
−
2
,
3
,
−
3
,
4
,
−
4
,
5
,
−
5 (which give the first ten, as they alternate). We
get these numbers are given in the following table by using the formula
j
= 1
j
=
−
1
j
= 2
j
=
−
2
j
= 3
j
=
−
3
j
= 4
j
=
−
4
j
= 5
j
=
−
5
1
2
5
7
12
15
22
26
35
40
What we need to verify with a drawing are
j
=
−
4 and
j
=
−
5 since the above pictures do not have the sixth and seventh
pentagons. These pentagons are
Page 2
Now by counting the red dots we indeed see there are 26 and 40.
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.
Solution:
The Pentagonal Number theorem states
(1
−
X
)(1
−
X
2
)(1
−
X
3
)
· · ·
= 1 +
∞
X
j
=1
(
−
1)
j
X
j
(3
j
−
1)
2
+
X
j
(3
j
+1)
2
.
The left hand side is the denominator of the generating function of the partitions. That is,
(
1 +
P
(1)
X
+
P
(2)
X
2
+
P
(3)
X
3
+
· · ·
)
1 +
∞
X
j
=1
(
−
1)
j
X
j
(3
j
−
1)
2
+
X
j
(3
j
+1)
2
= 1
.
Thus, if we want to compute any value of
P
(
n
), we compute the coefficient of
X
n
in the product of the left hand side and
solve for
P
(
n
). This leads to a recursion that we have studied in class.
We put all the details of its deduction for
n
= 11 only. For the other values we will simply use it directly. For
n
= 11,
we need the coefficient of
X
11
. Since no power of
X
whose exponent is greater than 11 can produce an
X
11
, we only care
about the finite part of this product using such powers. Concretely, we care about
(1 +
P
(1)
X
+
P
(2)
X
2
+
· · ·
)(1
−
X
−
X
2
+
X
5
+
X
7
− · · ·
) = 1
.
We ignore what follows in the second parenthesis since the next power is
X
12
, which cannot contribute. Then, to compute
the coefficient of
X
11
, we complete each power of
X
in
1
−
X
−
X
2
+
X
5
+
X
7
,
to
X
11
using
1 +
P
(1)
X
+
P
(2)
X
2
+
· · ·
We get the coefficient is
P
(11)
−
P
(10)
−
P
(9) +
P
(6) +
P
(4)
.
Since this must be 0, we deduce
P
(11) =
P
(10) +
P
(9)
−
P
(6)
−
P
(4) = 42 + 30
−
11
−
5 = 56
.
Page 3
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
For
n
= 12
,
13
,
14 we get the contribution of
X
12
, so we get the recursion for them is
P
(
n
) =
P
(
n
−
1) +
P
(
n
−
2)
−
P
(
n
−
5)
−
P
(
n
−
7) +
P
(
n
−
12)
.
That is,
P
(12) =
P
(11) +
P
(10)
−
P
(7)
−
P
(5) +
P
(0) = 56 + 42
−
15
−
7 + 1 = 77
,
P
(13) =
P
(12) +
P
(11)
−
P
(8)
−
P
(6) +
P
(1) = 77 + 56
−
22
−
11 + 1 = 101
,
P
(14) =
P
(13) +
P
(12)
−
P
(9)
−
P
(7) +
P
(2) = 101 + 77
−
30
−
15 + 2 = 135
.
Finally, for
n
= 15 we also have the contribution of
X
15
. Thus, the recursion is
P
(15) =
P
(14) +
P
(13)
−
P
(10)
−
P
(8) +
P
(3) +
P
(0) = 135 + 101
−
42
−
22 + 3 + 1 = 176
.
In summary, the table gets extended to
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
P
(
n
)
1
2
3
5
7
11
15
22
30
42
56
77
101
135
176
The yellow cells are the new ones we computed in this problem.
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.
(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
= 36 :
14 + 11 + 6 + 4 + 1
.
Page 4
(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!
Solution:
We do each part separately.
Part (a):
There are 30 partitions of 9. We list them in the following table. We put a check if the partitions is evenly
excessive (EE) or into super distinct parts (SDP). We leave the box empty otherwise.
Partition
EE
SDP
Partition
EE
SDP
Partition
EE
SDP
9
✓
✓
5+2+1+1
3+3+1+1+1
8+1
✓
✓
5+1+1+1+1
3+2+2+2
7+2
✓
4+4+1
3+2+2+1+1
7+1+1
4+3+2
3+2+1+1+1+1
6+3
✓
✓
4+3+1+1
3+1+1+1+1+1+1
6+2+1
4+2+2+1
2+2+2+2+1
6+1+1+1
4+2+1+1+1
2+2+2+1+1+1
5+4
✓
4+1+1+1+1+1
2+2+1+1+1+1+1
5+3+1
✓
✓
3+3+3
2+1+1+1+1+1+1+1
5+2+2
3+3+2+1
1+1+1+1+1+1+1+1+1
Notice that there are a lot of empty boxes because many partitions have repeated terms, which rules them out immediately.
We see that of each type of partition there are only 5 of each type.
Part (b):
The partition 14 + 11 + 6 + 4 + 1 has the following Ferrers Diagram
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
When we slide to the right we get the following
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Then we rearrange what is to the right of the vertical line:
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
When we disappear and slid back to the left we get the following Diagram, which is not a Ferrer’s Diagram:
Page 5
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
We rearrange it to become a Ferrer’s Diagram. We get
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
The partition we obtain is 14 + 8 + 7 + 6 + 1, which is an evenly excessive partition.
Part (c):
Let us begin by describing what is at the left of the vertical line. It is always an inverted stair shape, whose
bottom line has 1 dot, the next one 3, the next one 5, etc. If the stair has
j
rows, then the upper row of it has 2
j
−
1 dots.
Concretely, a stair with
j
rows has, respectively, in each row from top to bottom: 2
j
−
1
,
2
j
−
3
, ...,
5
,
3
,
1 dots.
For example, the following drawing shows a stair with 4 rows:
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Notice it has 7
,
5
,
3
,
1 dots in each descending row. Importantly, in each on of these stairs all the rows have an
odd
number
of dots.
What we want to prove is that the twice the number of odd parts is less than the smallest even part. Notice we can do
this without the last rearrangement. That is, the arrangement we get in step 3 which might not be a Ferrer’s Diagram is
still good enough for us to decide whether the partition produced in part 4 is or not evenly excessive. The reason is that
the number and parity of parts does not change by the rearrangement.
Thus, we focus on this. As we have said, the stair has an odd number of points in each row, which means that the part of
the final partition that corresponds to that row will have the parity opposite to that of the number of points that appear
after the vertical line.
Since in step 3 we have put the odd ones first andd the even ones after (counting points after the vertical part), we see
that the even parts of
λ
2
are the rows that appear on top, while the odd ones are the ones that appear on the bottom.
Let us say that there are
m
rows with an odd number of points (appearing on top in descending order) after the vertical
line. Call them from smallest to bigger:
b
1
, b
2
, ..., b
m
.
Similarly, let us suppose there are
k
even parts, including those that are empty (since 0 is even, this doesn’t change our
arguments). Call the parts, starting from the bottom one
a
1
, a
2
, ..., a
k
.
We have that
m
+
k
=
j
, where
j
is the number of rows of the inverted stair, since every row has some points (possible
none) after the vertical line.
For example, in the example we did in the previous part we have:
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
In here:
j
= 5 because there are 5 layers in the stair. We have
m
= 3 since there are 3 odd parts (after the vertical line)
and we have
b
1
= 1
, b
2
= 1
, b
3
= 5
.
Page 6
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Similarly,
k
= 2 and
a
1
= 0
, a
2
= 4
.
Now, we understand everything: the odd parts of the final partition
λ
2
are obtained from
a
1
, a
2
, ..., a
k
by adding the number
of points of the corresponding row of the stair. Thus, they are:
a
1
+ 1
, a
2
+ 3
, ..., a
k
+ 2
k
−
1
.
Similarly, the even parts of
λ
2
are obtained from
b
1
, ..., b
m
by adding the number of points of the corresponding row of the
stair. We have they are
b
1
+ 2
k
+ 1
, b
2
+ 2
k
+ 3
, ..., b
m
+ 2
j
−
1
.
From this we deduce: the number of odd parts of
λ
2
is
k
. Also, the smallest even part is
b
1
+ 2
k
+ 1, because both the
number of points in sucessive layer of the stairs and the
b
1
, b
2
, ...
increase.
So, to be evenly excessive means that
b
1
+ 2
k
+ 1
>
2(
k
)
,
which is equivalent to
b
1
+ 1
>
0
,
This is a true statement, so the inequality we need holds. Also, notice all the produces parts are different, since among
those of the same parity, one is always at least two points smaller than the next one since the stair’s rows increases in this
quantity.
This concludes this part.
Part (d):
To do the inverse we must deduce what are all the parameters of the previous part. That is
m, k
and
a
1
, ..., a
k
,
b
1
, ..., b
m
.
To do this realize that, before the final rearrangement we have that the even rows appear from larger to smallest first, and
the odd rows appear from larger to smallest. There is a unique way to do this for any partition.
So, suppose we are given a partition that is evenly excessive. Then organize the rows as above: put the even ones first,
from larger to smallest. Then the odd ones, from largest to smallest. After doing that slide to the right to get a stair of
j
layers where
j
is the number of part. The vertical line is at the right of the last layer (so that this last layer has a single
point to the left ot the line).
This configuration is what we must have obtained in stage three, before disappearing the vertical line, after making step
1, 2 and 3 to the partition into super distinct parts we are looking for.
From here thus we can read:
k
and
m
, as well as
a
1
, ..., a
k
,
b
1
, ..., b
m
. What we must do is to rearrange
a
1
, ..., b
m
, to undo
what happened in step 3. Notice that in step 2 we obtained a Ferrers Diagram (which we called
λ
1
. There is a unique way
to arange
a
1
, ..., a
k
,
b
1
, ..., b
m
so that they give a Ferrer’s Diagram. So we do that!
What we obtain now has a star to the left ot the line and a Ferrers Diagram to the right. Thus, if the partition is defined
by the total number of points in each row (i.e. on both sides of the line), we get from one row to the next they must differ
from at least 2, since the stair side decreases in this quantity! That is, this partition is into super distinct parts.
Notice that we are undoing the rules we gave above, so these processes are inverses!
Part (e):
What we have done in the two previous parts is to prove there is a bijective correspondence between partitions
into super distinct parts and evenly excessive partitions. Thus, there must be the same in number since bijections preserve
cardinality!
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 +
X
2
+
X
3
+
· · ·
)(1 +
X
4
+
X
6
+
· · ·
)(1 +
X
6
+
X
9
+
· · ·
)
· · ·
,
Page 7
that is,
∞
Y
k
=1
(
1 +
X
2
k
+
X
3
k
+
X
4
k
+
· · ·
)
.
(b) (2 points) Prove that we can rewrite the above generating function as
∞
Y
k
=1
1 +
X
3
k
1
−
X
2
k
.
(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?
Solution:
We do each part separately.
Part (a):
Let us recall that in the genrating function for partitions the term that corresponds to the part
k
is
1 +
X
k
+
X
2
k
+
X
3
k
+
X
4
k
+
...,
where the term
X
mk
corresponds to the terk
k
appearing
m
times, that is, to
k
+
k
+
...
+
k
|
{z
}
m
times
being part of the partition. If we don’t want it to appear once we must take away the term
X
k
. Hence, we get that
1 +
X
2
k
+
X
3
k
+
X
4
k
+
...,
corresponds to every possible appearance of the term
k
in the partition except it appearing exactly once.
Hence, multiplying all of these factors for each possible
k
we obtain the desired generating function. That is, we obtain
∞
Y
k
=1
(
1 +
X
2
k
+
X
3
k
+
X
4
k
+
· · ·
)
,
as desired.
Part (b):
This is just an algebraic manipulation. Indeed, for a fixed
k
, we have
1 +
X
2
k
+
X
3
k
+
X
4
k
+
· · ·
= 1 +
X
2
k
(1 +
X
k
+
X
2
k
+
· · ·
)
= 1 +
X
2
k
1
−
X
k
=
1
−
X
k
+
X
2
k
1
−
X
k
.
To transform the denominator from 1
−
X
k
to 1
−
X
2
k
we recall that, by difference of squares, we have
1
−
X
2
k
= (1 +
X
k
)(1
−
X
k
)
.
Thus, we multiply numerator and denominator by 1 +
X
k
and get
1
−
X
k
+
X
2
k
1
−
X
k
=
(1
−
X
k
+
X
2
k
)(1 +
X
k
)
(1
−
X
k
)(1 +
X
k
)
=
1 +
X
3
k
1
−
X
2
k
.
Notice that in the numerator we have used the sum of cubes factorization, that is,
1 +
y
3
= (1 +
y
)(1
−
y
+
y
2
)
,
Page 8
with
y
=
X
k
. Substituting this, for each
k
, we obtain the generating function is
∞
Y
k
=1
1 +
X
3
k
1
−
X
2
k
,
as desired.
Remark:
This process of multiplying above and below in a fraction to transform what we have for other factor, that might
mean a different thing from the perspective of generating functions, is very common. Keep in mind classical factorizations!
Part (c):
Let us now expand the above product instead of writing it in condensed form. We get
∞
Y
k
=1
1 +
X
3
k
1
−
X
2
k
=
1 +
X
3
1
−
X
2
|
{z
}
k
= 1
×
1 +
X
6
1
−
X
4
|
{z
}
k
= 2
×
1 +
X
9
1
−
X
6
|
{z
}
k
= 3
×
1 +
X
12
1
−
X
8
|
{z
}
k
= 4
×
1 +
X
15
1
−
X
10
|
{z
}
k
= 5
×
1 +
X
18
1
−
X
12
|
{z
}
k
= 6
· · · ·
Notice that when
k
is a multiple of 3, that is when
k
= 3
m
, we get in the denominator
1
−
X
2(3
m
)
= 1
−
X
6
m
= (1 +
X
3
m
)(1
−
X
3
m
)
,
and the factor 1 +
X
3
m
cancels with a term in the numerator (for the case when
k
=
m
). We show this for the first two
cancellations in the next product: with matching colors:
∞
Y
k
=1
1 +
X
3
k
1
−
X
2
k
=
1 +
X
3
1
−
X
2
|
{z
}
k
= 1
×
1 +
X
6
1
−
X
4
|
{z
}
k
= 2
×
1 +
X
9
1
−
X
6
|
{z
}
k
= 3
×
1 +
X
12
1
−
X
8
|
{z
}
k
= 4
×
1 +
X
15
1
−
X
10
|
{z
}
k
= 5
×
1 +
X
18
1
−
X
12
|
{z
}
k
= 6
· · · ·
The next term, that is 1 +
X
9
would cancel with a term of 1
−
X
18
, and so on. What remains after all the cancellations
have been performed is:
∞
Y
k
=1
1 +
X
3
k
1
−
X
2
k
=
1
1
−
X
2
×
1
1
−
X
4
×
1
1
−
X
3
×
1
1
−
X
8
×
1
1
−
X
10
×
1
1
−
X
6
· · · ·
Upon rearrangement what we get are terms of the form
1
1
−
X
a
,
for some
a
. The
a
that appear are either from denominators that did not get a factor cancelled, that is, from
a
= 2
k
with
k
not a multiple of 3. The other possibility is that
a
= 6
m
, if
k
= 3
m
, in which case what remained was 1
−
X
3
m
. We
obtain here, multiples of 3.
However, notice that we do not have repetitions: that is because if a term appeared after some cancellation is because it
corresponded to a term whose
k
was a multiple of 3 and what remain as exponent is a multiple of 3. While those that
appeared without being cancelled are those whose exponent is not a multiple of 3. Since a number cannot be simultaneously
a multiple of 3 and a non-multiple of 3, we see that no term repeats.
In conclusion, the above product is
∞
Y
k,
2
|
k
or
3
|
k
1
1
−
X
k
,
which is precisely the generating function of the partitions of
n
whose terms are either multiples of 2 or multiples of 3
(make sure you understand why!).
Part (d):
We must find the coefficient of
X
11
in the above generating function. We have two versions of the generating
function and we must pick the one where the product is easier.
We choose the one for abundant partitions:
(1 +
X
2
+
X
3
+
· · ·
)(1 +
X
4
+
X
6
+
· · ·
)(1 +
X
6
+
X
9
+
· · ·
)
· · ·
,
and since we only care about
X
11
we ignore every term whose exponent is bigger than 11. We get that the product we
care about is
(1 +
X
2
+
X
3
+
...
+
X
11
)(1 +
X
4
+
X
6
+
X
8
+
X
10
)(1 +
X
6
+
X
9
)(1 +
X
8
)(1 +
X
10
)
.
Page 9
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
We now multiply, taking into account, we only care about terms whose exponent does not exceed 11. The other terms we
write them as
...
since we wont consider them.
(1 +
X
8
)(1 +
X
10
) = 1 +
X
8
+
X
10
+
...
Then we get
(1 +
X
6
+
X
9
)(1 +
X
8
+
X
10
) = 1 +
X
6
+
X
8
+
X
9
+
X
10
+
...
Then we get
(1 +
X
4
+
X
6
+
X
8
+
X
10
)(1 +
X
6
+
X
8
+
X
9
+
X
10
+
...
) = 1 +
X
4
+ 2
X
6
+ 2
X
8
+
X
9
+ 3
X
10
+
...
Finally, for the final product we just compute the coefficient of
X
11
by matching the appropriate values of
X
. We consider
the product
(1 +
X
2
+
X
3
+
...
+
X
11
)(1 +
X
4
+ 2
X
6
+ 2
X
8
+
X
9
+ 3
X
10
+
...
)
,
and the coefficient of
X
11
(following the terms of the second factor) is
(1)(1) + (1)(1) + (2)(1) + (2)(1) + (1)(1) = 7
.
Notice that the term 3
X
10
does not contribute because the other factor doesn’t have an
X
term.
We conclude there are 7 good partitions of
N
= 11.
Page 10