Skip to main content

Section 2.4 Partitions of Integers

In Example 1.3.5, we counted the compositions of an integer \(n\text{,}\) by counting the number of solutions to the equation \(x_1 + x_2 + \cdots + x_k = n\) where each \(x_i\) is a positive integer. Put another way, we asked how many lists of \(k\) positive integers have sum \(n\text{.}\) The order in which we listed the sum mattered. What if it didn't?

Subsection 2.4.1 Partition numbers

A multiset of positive integers that add to \(n\) is called a partition of \(n\text{.}\) Thus the partitions of 3 are 1+1+1, 1+2 (which is the same as 2+1) and 3. The number of partitions of \(k\) is denoted by the partition number \(p(k)\text{;}\) in computing the partitions of 3 we showed that \(p(3) = 3\text{.}\) It is traditional to use Greek letters like \(\lambda\) to stand for partitions; we might write \(\lambda = 1,1,1\text{,}\) \(\gamma= 2,1\) and \(\tau = 3\) to stand for the three partitions we just described. We also write \(\lambda = 1^3\) as a shorthand for \(\lambda = 1,1,1\text{,}\) and we write \(\lambda \dashv 3\) as a shorthand for “\(\lambda\) is a partition of three.”

Example 2.4.1.
There are 5 partitions of 4 (so \(p(4) = 5\)). They are \(4=1+1+1+1\text{,}\) \(4=2+1+1\text{,}\) \(4=2+2\text{,}\) \(4=3+1\text{,}\) and \(4=4\text{.}\)
Activity 233.

Write out all partitions of 5, to compute \(p(5)\text{.}\)

A partition of the integer \(k\) into \(n\) parts is a multiset of \(n\) positive integers that add to \(k\text{.}\) We use \(p_n(k)\) to denote the number of partitions of \(k\) into \(n\) parts. Thus \(p_n(k)\) is the number of ways to distribute \(k\) identical objects to \(n\) identical recipients so that each gets at least one.

Example 2.4.2.

Here are the partitions of 7 into two parts: \(6+1\text{,}\) \(5+2\text{,}\) \(4+3\text{.}\) Thus \(p_2(7) = 3\text{.}\)

Activity 234.

Find \(p_3(6)\) by finding all partitions of 6 into 3 parts. What does this say about the number of ways to put six identical apples into three identical bags so that each bag has at least one apple?

Exercise 235.

How many solutions are there in the positive integers to the equation \(x_1+x_2+x_3 =7\) with \(x_1\ge x_2\ge x_3\text{?}\)

Exercise 236.

Explain the relationship between partitions of \(k\) into \(n\) parts and lists \(x_1,x_2,\ldots,x_n\) of positive integers with \(x_1 + x_2 + \cdots + x_n = k\) and \(x_1\ge x_2\ge\ldots \ge x_n\text{.}\) Such a representation of a partition is called a decreasing list representation of the partition.

Exercise 237.

Show that \(p_n(k)\) is at least \(\frac{1}{n!}\binom{k-1}{n-1}\text{.}\)

Hint

How many compositions are there of \(k\) into \(n\) parts? What is the maximum number of compositions that could correspond to a given partition of \(k\) into \(n\) parts?

Exercise 238.

Describe the relationship between partitions of \(k\) and lists of vectors \((x_1,x_2,\ldots,x_n)\) such that \(x_1+2x_2+\ldots kx_k = k\text{.}\) Such a representation of a partition is called a type vector representation of a partition, and it is typical to leave the trailing zeros out of such a representation; for example \((2,1)\) stands for the same partition as \((2,1,0,0)\text{.}\) What is the decreasing list representation for this partition, and what number does it partition?

Exercise 239.

How does the number of partitions of \(k\) relate to the number of partitions of \(k+1\) whose smallest part is one?

Hint

How can you start with a partition of \(k\) and make it into a new partition of \(k+1\) that is guaranteed to have a part of size one, even if the original partition didn't?

When we write a partition as \(\lambda = \lambda_1,\lambda_2,\ldots,\lambda_n\text{,}\) it is customary to write the list of \(\lambda_i\)s as a decreasing list. When we have a type vector \((t_1,t_2,\ldots,t_m)\) for a partition, we write either \(\lambda = 1^{t_1}2^{t_2}\cdots m^{t_m}\) or \(\lambda = m^{t_m}(m-1)^{t_{m-1}}\cdots 2^{t_2}1^{t_1}\text{.}\) Henceforth we will use the second of these. When we write \(\lambda=\lambda_1^{i_1}\lambda_2^{i_2}\cdots\lambda_n^{i_n}\text{,}\) we will assume that \(\lambda_i>\lambda_i+1\text{.}\)

It is remarkable that there is no known formula for \(p_n(k)\text{,}\) nor is there one for \(p(k)\text{.}\) We have computed a few values of \(p_n(k)\) by listing partitions. If we continue to do so, we could build a triangle of partition numbers as follows.

\(k\backslash n\) 1 2 3 4 5 6 7
1 1
2 1 1
3 1 1 1
4 1 2 1 1
5 1 2 2 1 1
6 1 3 3 2 1 1
7 1 3 4 3 2 1 1
Figure 2.4.3. The triangle of partition numbers through 7.

So for example, \(p_3(7) = 4\text{:}\) \((5,1,1)\text{,}\) \((4,2,1)\text{,}\) \((3,3,1)\text{,}\) and \((3,2,2)\text{.}\) It sure would be nice to find the next row without having to list out all the partitions. Perhaps we could use some sort of recursion!

With the binomial coefficients, with Stirling numbers of the second kind, and with the Lah numbers, we were able to find a recurrence by asking what happens to our subset, partition, or broken permutation of a set \(S\) of numbers if we remove the largest element of \(S\text{.}\) Thus it is natural to look for a recurrence to count the number of partitions of \(k\) into \(n\) parts by doing something similar. Unfortunately, since we are counting distributions in which all the objects are identical, there is no way for us to identify a largest element. However if we think geometrically, we will be able to “see” how to get smaller partitions from larger.

Subsection 2.4.2 Using Geometry

The decreasing list representation of partitions leads us to a handy way to visualize partitions. Given a decreasing list \((\lambda_1,\lambda_2,\ldots \lambda_n)\text{,}\) we draw a figure made up of rows of dots that has \(\lambda_1\) equally spaced dots in the first row, \(\lambda_2\) equally spaced dots in the second row, starting out right below the beginning of the first row and so on. Equivalently, instead of dots, we may use identical squares, drawn so that a square touches each one to its immediate right or immediately below it along an edge. See Figure 2.4.4 for examples. The figure we draw with dots is called the Ferrers diagram of the partition; sometimes the figure with squares is also called a Ferrers diagram; sometimes it is called a Young diagram. At this stage it is irrelevant which name we choose and which kind of figure we draw; in more advanced work the squares are handy because we can put things like numbers or variables into them. From now on we will use squares and call the diagrams Young diagrams.

Figure 2.4.4. The Ferrers and Young diagrams of the partition (5,3,3,2)
Activity 240.
We will soon start manipulating Young diagrams, so having some examples will be useful. Keep these in a safe place.
(a)

Draw all the Young diagrams for the partitions of 4 and 5, grouping (i.e., partitioning) them by the number of parts.

(b)

Draw all \(p_2(6)\) Young diagrams for the partitions of 6 into 2 parts.

(c)

Draw all \(p_3(7)\) Young diagrams for the partitions of 7 into 3 parts.

(d)

Draw all \(p_4(9)\) Young diagrams for the partitions of 9 into 4 parts.

The natural way to get a partition of a smaller integer from a partition of \(n\) is to remove some of the squares from the Young diagram. We lots of choices here.

  1. We could remove the entire top row.

  2. We could remove the entire left-most column.

  3. We could remove a single box somewhere. But from where?

Removing the top row corresponds to removing the largest part of the partition. Removing the left-most column corresponds to subtracting 1 from each part. Removing a single box will reduce one part by 1. Some of these might be more useful than others.

Activity 241.

Let's see what happens when we remove the top row and whether this is helfpul.

(a)

Look at your partitions of 7 into 3 parts. Which partitions of what into how many parts do you get if you remove the top row? Looking at the partition number triangle, does this allow you to calculate \(p_3(7) = 4\text{?}\)

(b)

Not so fast! Repeat the previous task with your partitions of \(9\) into 4 parts. What goes wrong here?

Activity 242.

Now consider what happens when we remove the left-most column.

(a)

Remove the left most column from each of your partitions of \(7\) into 3 parts. Which partitions of what into how many parts do you get? Comparing to the partition number triangle, does this allow you to compute \(p_3(7) = 4\text{?}\)

Hint

Note that you get partitions always of the same number (which?) but into a different number of parts (why?).

(b)

Repeat the previous task with partitions of \(9\) into 4 parts. Do we run into the same problem as when we removed the top row?

The previous activity suggests a recurrence for \(p_n(k)\text{.}\) We might guess

\begin{equation*} p_n(k) = \sum_{i=1}^n p_i(k-n) = p_1(k-n) + p_2(k-n) + \cdots + p_n(k-n)\text{.} \end{equation*}

For example,

\begin{equation*} p_4(9) = p_1(5) + p_2(5) + p_3(5)+ p_4(5) = 1+2+2+1 = 6 \end{equation*}

(note we do not add the entire row, just up until the column we are interested in).

Exercise 243.

Complete the 8th row of the partition number triangle using the recurrence.

Exercise 244.

Prove the recurrence for \(p_n(k)\) is correct.

Hint

Since the recurrence is a sum of smaller partition numbers, we are claiming that we can break the partitions of \(k\) into \(n\) parts into different groups, and each group will correspond to a different collection of smaller partitions. How can you describe these groups geometrically?

Wikipedia (and almost every other textbook) gives another recursion for \(p_n(k)\text{:}\)

\begin{equation*} p_n(k) = p_n(k-n) + p_{n-1}(k-1)\text{.} \end{equation*}

Let's call this the short recursion for partition numbers (and we will call our original recurssion the “long” one).

Activity 245.

Does the short recursion really work?

(a)

Verify the short recursion using numbers in the triangle. In particular, check \(p_4(9)\text{.}\)

(b)

Use your Young diagrams you drew above to see what is going on with the short recursion. What geometric operations do the two parts of the sum represent?

(c)

Generalize your observations in the previous task to explain why the short recursion is correct.

Activity 246.

Suppose we wanted to compute \(p_5(13)\text{.}\) Since we have the 8th row of the partition number triangle, we should be able to do this with the long recursion. What if we wanted to use the short recursion?

Use the short recursion to compute \(p_5(13)\text{.}\) If you get a partition number that you don't yet know, use the short recursion to compute that as well (you know, the way you use recursions).

As you see above, the short recursion is nothing more than grouping all but the first term in the sum into a single partition number, using the long recursion again. This should make sense based on the geometry of the Young digrams.

More Geometry.

Our goal is to use geometric reasoning about these diagrams (we will generally use the Young diagram with squares) to uncover properties of partitions.

Activity 247.

Draw the Young diagram of the partition (4,4,3,1,1). Describe the geometric relationship between the Young diagram of (5,3,3,2) and the Young diagram of (4,4,3,1,1).

Hint

Draw a line through the top-left corner and bottom-right corner of the top-left box.

Activity 248.

The partition \((\lambda_1,\lambda_2,\ldots, \lambda_n)\) is called the conjugate of the partition \((\gamma_1,\gamma_2,\ldots, \gamma_m)\) if we obtain the Young diagram of one from the Young diagram of the other by flipping one around the line with slope -1 that extends the diagonal of the top left square. (Equivalently, simply interchanging rows and columns, like taking the transpose of a matrix.) See Figure 2.4.5 for an example.

Figure 2.4.5. The Young diagram for the partition (5,3,3,2) and its conjugate.

What is the conjugate of (4,4,3,1,1)? How is the largest part of a partition related to the number of parts of its conjugate? What does this tell you about the number of partitions of a positive integer \(k\) with largest part \(m\text{?}\)

Hint

The largest part of a partition is the maximum number of boxes in a row of its Young diagram. What does the maximum number of boxes in a column tell us?

Activity 249.

A partition is called self-conjugate if it is equal to its conjugate. Find a relationship between the number of self-conjugate partitions of \(k\) and the number of partitions of \(k\) into distinct odd parts.

Hint

Draw all self conjugate partitions of integers less than or equal to 8. Draw all partitions of integers less than or equal to 8 into distinct odd parts (many of these will have just one part). Now try to see how to get from one set of drawings to the other in a consistent way.

Example 2.4.7.

Restricting the number or type of parts often leads to interesting relationships.

We must be careful about what we mean. For example, here are three different sorts of “even” partitions for \(k = 10\text{:}\)

Even parts:

\begin{gather*} (10) \\ (8, 2)\\ (6, 4)\\ (6, 2, 2)\\ (4,4,2)\\ (4,2,2,2)\\ (2,2,2,2,2) \end{gather*}

Even number of parts:

\begin{gather*} (9,1) \\ (8,2) \\ (7,3) \\ (6,4) \\ (5,5) \\ (4,3,2,1) \end{gather*}

Parts with even multiplicity:

\begin{gather*} (5,5) \\ (4,4,1,1) \\ (3,3,2,2) \\ (3,3,1,1,1,1) \\ (2,2,2,2,1,1) \\ (2,2,1,1,1,1,1,1) \\ (1,1,1,1,1,1,1,1,1,1) \end{gather*}
Activity 250.

Explain the relationship between the number of partitions of \(k\) into even parts and the number of partitions of \(k\) into parts of even multiplicity, i.e. parts which are each used an even number of times as in (3,3,3,3,2,2,1,1).

Hint

Draw the partitions of six into even parts. Draw the partitions of six into parts used an even number of times. Look for a relationship between one set of diagrams and the other set of diagrams. If you have trouble, repeat the process using 8 or even 10 in place of 6.

Exercise 251.

Show that the number of partitions of \(k\) into four parts equals the number of partitions of \(3k\) into four parts of size at most \(k-1\) (or \(3k-4\) into four parts of size at most \(k-2\) or \(3k-4\) into four parts of size at most \(k\)).

Hint

Draw a partition of ten into four parts. Assume each square has area one. Then draw a rectangle of area 40 enclosing your diagram that touches the top of your diagram, the left side of your diagram and the bottom of your diagram. How does this rectangle give you a partition of 30 into four parts?

Exercise 252.

The idea of conjugation of a partition could be defined without the geometric interpretation of a Young diagram, but it would seem far less natural without the geometric interpretation. Another idea that seems much more natural in a geometric context is this. Suppose we have a partition of \(k\) into \(n\) parts with largest part \(m\text{.}\) Then the Young diagram of the partition can fit into a rectangle that is \(m\) or more units wide (horizontally) and \(n\) or more units deep. Suppose we place the Young diagram of our partition in the top left-hand corner of an \(m'\) unit wide and \(n'\) unit deep rectangle with \(m'\ge m\) and \(n' \ge n\text{,}\) as in Figure 2.4.8.

Figure 2.4.8. To complement the partition \((5,3,3,2)\) in a 6 by 5 rectangle: enclose it in the rectangle, rotate, and cut out the original Young diagram.
(a)

Why can we interpret the part of the rectangle not occupied by our Young diagram, rotated in the plane, as the Young diagram of another partition? This is called the complement of our partition in the rectangle.

(b)

What integer is being partitioned by the complement?

(c)

What conditions on \(m'\) and \(n'\) guarantee that the complement has the same number of parts as the original one?

Hint

Consider two cases, \(m' \gt m\) and \(m' = m\text{.}\)

(d)

What conditions on \(m'\) and \(n'\) guarantee that the complement has the same largest part as the original one?

Hint

Consider two cases, \(n' \gt n\) and \(n' = n\text{.}\)

(e)

Is it possible for the complement to have both the same number of parts and the same largest part as the original one?

(f)

If we complement a partition in an \(m'\) by \(n'\) box and then complement that partition in an \(m'\) by \(n'\) box again, do we get the same partition that we started with?

Exercise 253.

Suppose we take a partition of \(k\) into \(n\) parts with largest part \(m\text{,}\) complement it in the smallest rectangle it will fit into, complement the result in the smallest rectangle it will fit into, and continue the process until we get the partition 1 of one into one part. What can you say about the partition with which we started?

Hint 1

Suppose we take two repetitions of this complementation process. What rows and columns do we remove from the diagram?

Hint 2

To deal with an odd number of repetitions of the complementation process, think of it as an even number plus 1. Thus ask what kind of partition gives us the partition of one into one part after this complementation process.

Subsection 2.4.3 Partitions into distinct parts

Often \(q_n(k)\) is used to denote the number of partitions of \(k\) into distinct parts, that is, parts that are different from each other.

Example 2.4.9.

Show that the number of partitions of 7 into three parts equals the number of partitions of 10 into three distinct parts.

Solution

To get a feel for this, list them out:

\begin{align*} (5,1,1) \qquad \amp \qquad (7,2,1)\\ (4,2,1) \qquad \amp \qquad (6,3,1)\\ (3,3,1) \qquad \amp \qquad (5,4,1)\\ (3,2,2) \qquad \amp \qquad (5,3,2) \end{align*}

There are four of each sort, which shows what we want. But what is the connection? It's to add 210!

Given a partition \(\lambda\) of 7 in decreasing list form \(\lambda_1,\lambda_2,\lambda_3\text{,}\) if we add 0 to \(\lambda_3\text{,}\) \(1\) to \(\lambda_2\) and 2 to \(\lambda_1\) the resulting partition of 10 has distinct parts. If we take a partition \(\lambda'\) of 10 with distinct parts, then \(\lambda'_1\ge\lambda'_2+1\text{,}\) \(\lambda'_1\ge\lambda'_3+2\text{,}\) and \(\lambda'_2\ge \lambda'_3+1\text{.}\) Therefore if we subtract 2 from \(\lambda'_1\) to get \(\lambda_1\text{,}\) subtract 1 from \(\lambda'_2\) to get \(\lambda_2\) and let \(\lambda_3= \lambda'_3\text{,}\) then \(\lambda_1,\lambda_2,\lambda_3\) is the decreasing list representation of a partition of \(10-3=7\text{.}\) Thus there is a bijection between partitions of \(7\) into three parts and partitions of \(10\) into three distinct parts.

Exercise 254.

Show that the number of partitions of \(10\) into three parts equals the number of partitions of 13 into three distinct parts.

Exercise 255.

There is a relationship between \(p_n(k)\) and \(q_n(m)\) for some other number \(m\text{.}\) Find the number \(m\) that gives you the nicest possible relationship.

Hint

In the case \(k=4\) and \(n=2\text{,}\) we have \(m=5\text{.}\) In the case \(k = 7\) and \(n = 3\text{,}\) we have \(m = 10\text{.}\)

Activity 256.

Find a recurrence that expresses \(q_n(k)\) as a sum of \(q_m(k-n)\) for appropriate values of \(m\text{.}\)

Hint

What can you do to a Young diagram for a partition of \(k\) into \(n\) distinct parts to get a Young diagram of a partition of \(k-n\) into some number of distinct parts?

The following exercise is interesting, but difficult. The adventurous reader can try it directly here. We will establish the same result using generating functions in the next section.

Exercise 257.

Show that the number of partitions of \(k\) into distinct parts equals the number of partitions of \(k\) into odd parts.

Hint

For any partition of \(k\) into parts \(\lambda_1\text{,}\) \(\lambda_2\text{,}\) etc. we can get a partition of \(k\) into odd parts by factoring the highest power of two that we can from each \(\lambda_i\text{,}\) writing \(\lambda_i = \gamma_i\cdot 2^k_i\text{.}\) Why is \(\gamma_i\) odd? Now partition \(k\) into \(2^{k_1}\) parts of size \(\gamma_1\text{,}\) \(2^{k_2}\) parts of size \(\gamma_2\text{,}\) etc. and you have a partition of \(k\) into odd parts.

Here is another challenging exercise.

Exercise 258.

Euler showed that if \(k\not= \frac{3j^2+j}{2}\text{,}\) then the number of partitions of \(k\) into an even number of distinct parts is the same as the number of partitions of \(k\) into an odd number of distinct parts. Prove this, and in the exceptional case find out how the two numbers relate to each other.

Hint

Suppose we have a partition of \(k\) into distinct parts. If the smallest part, say \(m\text{,}\) is smaller than the number of parts, we may add one to each of the \(m\) largest parts and delete the smallest part, and we have changed the parity of the number of parts, but we still have distinct parts. On the other hand, suppose the smallest part, again say \(m\text{,}\) is larger than or equal to the number of parts. Then we can subtract 1 from each part larger than \(m\text{,}\) and add a part equal to the number of parts larger than \(m\text{.}\) This changes the parity of the number of parts, but if the second smallest part is \(m+1\text{,}\) the resulting partition does not have distinct parts. Thus this method does not work. Further, if it did always work, the case \(k \ne \frac{3j^2+j}{2}\) would be covered also. However you can modify this method by comparing \(m\) not to the total number of parts, but to the number of rows at the top of the Young diagram that differ by exactly one from the row above. Even in this situation, there are certain slight additional assumptions you need to make, so this hint leaves you a lot of work to do. (It is reasonable to expect problems because of that exceptional case.) However, it should lead you in a useful direction.

And finally, a much simpler, purely combinatorial result.

Exercise 259.

Show that

\begin{equation*} q_n(k) \le \frac{1}{n!}\binom{k-1}{n-1}. \end{equation*}
Hint

How does the number of compositions of \(k\) into \(n\) distinct parts compare to the number of compositions of \(k\) into \(n\) parts (not necessarily distinct)? What do compositions have to do with partitions?

Subsection 2.4.4 Using Generating Functions

I this final section we will see that generating functions are especially well suited for the study of integer partitions. We will start with a classic example.

Activity 260.

If we have five identical pennies, five identical nickels, five identical dimes, and five identical quarters, give the picture enumerator for the combinations of coins we can form and convert it to a generating function for the number of ways to make \(k\) cents with the coins we have. Do the same thing assuming we have an unlimited supply of pennies, nickels, dimes, and quarters.

Hint

This is a good place to apply the product principle for picture enumerators. Don't be afraid to use technology to finish the problem.

Activity 261.

In Activity 260 we found the generating function for the number of partitions of an integer into parts of size 1, 5, 10, and 25.

(a)

Give the generating function for the number partitions of an integer into parts of size one through ten.

Hint

The product principle for generating functions helps you break the generating function into a product of ten simpler ones.

(b)

Give the generating function for the number of partitions of an integer \(k\) into parts of size at most \(m\text{,}\) where \(m\) is fixed but \(k\) may vary. Notice this is the generating function for partitions whose Young diagram fits into the space between the line \(x=0\) and the line \(x=m\) in a coordinate plane. (We assume the boxes in the Young diagram are one unit by one unit.)

Hint

\(m\) was 10 in the previous part of this problem.

Activity 262.

In Task 261.b you gave the generating function for the number of partitions of an integer into parts of size at most \(m\text{.}\) Can you see why this is also the generating function for partitions of an integer into at most \(m\) parts.

Hint

Think about conjugate partitions.

Example 2.4.10.

The generating function for the number of partitions of an integer into parts of any size is

\begin{equation*} \frac{1}{(1-x)(1-x^2)(1-x^3) \cdots} = (1+x+x^2+x^3+\cdots)(1+x^2+x^4+\cdots)(1+x^3+\cdots)\cdots\text{.} \end{equation*}

The coefficient of \(x^4\) is 5. Where does this come from exactly?

First notice that the \(x^4\) in the second factor is really \(x^{2\cdot 2}\text{.}\) That is, while the first factor's \(x^4\) represents using four 1's, the second factor's \(x^4\) comes from \((x^2)^2\) so represents using two 2's. The fourth factor's \(x^4\) means one 4.

Here are all the ways of forming \(x^4\) using the first four factors (we would never need anything beyond this), and their corresponding partition.

\begin{align*} 1\cdot1 \cdot 1 \cdot x^4 \amp \leftrightarrow (4) \\ x\cdot 1 \cdot x^3\cdot 1 \amp \leftrightarrow (3,1) \\ 1 \cdot x^4 \cdot 1\cdot 1 \amp \leftrightarrow (2,2) \\ x^2\cdot x^2\cdot 1 \cdot 1 \amp \leftrightarrow (2,1,1) \\ x^4 \cdot 1\cdot 1 \cdot 1 \amp \leftrightarrow (1,1,1,1) \end{align*}
Exercise 263.

Illustrate the partitions of 5 and their correspondence to the ways to get \(x^5\) in the generating function for the number of partitions of an integer.

Hint

Note that \(1+x^2+x^4+x^6+\cdots\) in the generating function is really \(1+x^2 + x^{2\cdot 2}\)

Example 2.4.11.

The generating function for the number of partitions of an integer in which each part is even is

\begin{equation*} \frac{1}{(1-x^2)(1-x^4)(1-x^6)\cdots} \end{equation*}
Example 2.4.12.

Explain why the generating function for the number of partitions of an integer into exactly \(m\) parts is

\begin{equation*} \frac{x^m}{(1-x)(1-x^2)\cdots(1-x^m)}\text{.} \end{equation*}
Solution

By considering a Young diagram and its compliment, we saw that there is a one to one correspondence between partitions that have exactly \(m\) parts and partitions that have \(m\) as their largest part.

The generating function for the number of partitions of integers having largest part \(m\) is

\begin{equation*} \frac{1}{(1-x)(1-x^2)\cdots (1-x^m)}\text{.} \end{equation*}

Thus this is also the number of partitions of integers having at most \(m\) parts. Now subtract those having at most \(m-1\) parts:

\begin{equation*} \frac{1}{(1-x)\cdots (1-x^m)} - \frac{1}{(1-x)\cdots (1-x^{m-1})} = \frac{x^m}{(1-x)\cdots(1-x^m)}\text{.} \end{equation*}

Alternatively, instead of doing the algebra on the last step, we can use Young diagrams again. There is a bijection between partitions of \(k\) into exactly \(m\) parts and partitions of \(k-m\) into at most \(m\) parts. The bijection is: remove the first column! So look at the infinite series for \(\frac{1}{(1-x)(1-x^2)\cdots (1-x^m)}\text{.}\) The coefficient of \(x^{k-m}\) is the number of partitions of \(k-m\) into at most \(m\) parts. So if we multiply each term by \(x^m\text{,}\) then the coefficient of \(x^{k-m+m} = x^{k}\) is the number of partitions of \(k-m\) into at most \(m\) parts. But this is the number of partitions of \(k\) into exactly \(m\) parts, as required.

Exercise 264.

Show that the generating function for the number of partitions of integers into exactly \(m\) distinct parts is

\begin{equation*} \frac{x^{\frac{m(m+1)}{2}}}{(1-x)(1-x^2)\cdots(1-x^m)}\text{.} \end{equation*}
Example 2.4.13.

Let's illustrate these last few results with \(m = 3\text{.}\)

First,

\begin{equation*} \frac{1}{(1-x)(1-x^2)(1-x^3)} = 1 + x + 2x^2 + 3x^3 + 4x^5 + 7x^6 + \cdots\text{.} \end{equation*}

This shows that the number of partitions of \(n = 6\) into at most 3 parts is \(7\text{.}\) The are

\begin{gather*} (6) \\ (5,1) \\ (4,2) \\ (4,1,1) \\ (3,3) \\ (3,2,1) \\ (2,2,2) \text{.} \end{gather*}

Now multiply the series by \(x^3\text{.}\) The term \(3x^6\) shows that there are \(3\) partitions of \(n=6\) into exactly 3 parts.

Finally, multiply instead by \(x^{\frac{m(m+1)}{2}} = x^6\) (when \(m = 3\)) to get \(x^6 + x^7 + 2x^8 + 3x^9+ 4x^{10} + \cdots\text{.}\) This shows that only one of the partitions of \(n=6\) into 3 parts has its parts distinct. Further, there are \(4\) partitions of \(n = 10\) into exactly 3 distinct parts:

\begin{gather*} (7,2,1) \\ (6,3,1) \\ (5,4,1) \\ (5,3,2) \text{.} \end{gather*}
Exercise 265.

Give the generating function for the number of partitions of \(n\) with each of the following restrictions

(a)

Each part is used at most once (i.e., a partition into distinct parts).

(b)

No part is larger than 3.

(c)

All parts are odd.

(d)

All parts are distinct and odd.

(e)

Only even parts may be repeated.

(f)

No part appears more than twice.

(g)

All parts are in the set \(\{3,8\}\text{.}\) (This might remind you of a stamp problem.)

Exercise 266.

Use generating functions to explain why the number of partitions of an integer in which each part is used an even number of times equals the number of partitions of an integer in which each part is even.

Hint

In the power series \(\sum_{j=0}^\infty x^{2ij}\text{,}\) the \(2ij\) has a different interpretation if you think of it as \((2i) \cdot j\) or if you think of it as \(i \cdot (2j)\text{.}\)

Exercise 267.

Use the fact that

\begin{equation*} \frac{1-x^{2i}}{1-x^i}= 1+x^i \end{equation*}

and the generating function for the number of partitions of an integer into distinct parts to show how the number of partitions of an integer \(k\) into distinct parts is related to the number of partitions of an integer \(k\) into odd parts.

Hint

Note that

\begin{equation*} \frac{1-x^2}{1-x}\cdot \frac{1-x^4}{1-x^2}\cdot \frac{1-x^6}{1-x^3}\cdot \frac{1-x^8}{1-x^4} = \frac{(1-x^6)(1-x^8)}{(1-x)(1-x^3)} \text{.} \end{equation*}
Exercise 268.

Verify that the number of partitions of \(n=5\) is equal to the number of partitions of \(10\) into exactly 5 parts. Generalize.

Exercise 269.

Write down the generating function for the number of ways to partition an integer into parts of size no more than \(m\text{,}\) each used an odd number of times. Write down the generating function for the number of partitions of an integer into parts of size no more than \(m\text{,}\) each used an even number of times. Use these two generating functions to get a relationship between the two sequences for which you wrote down the generating functions.

Hint

Note that \(x^i + x^{3i} + x^{5i} + \cdots = x^i (1 + x^2 + x^4 + \cdots)\text{.}\)

Exercise 270.

Show algebraically that

\begin{equation*} (1+x)(1+x^2)(1+x^4)(1+x^8)\cdots = \frac{1}{(1-x)(1-x^3)(1-x^5)\cdots}\text{.} \end{equation*}

What does this identity tell you about partitions of integers?

Exercise 271.
(a)

Prove that

\begin{equation*} \frac{1}{1-x} = (1 + x + x^2 +\cdots + x^9)(1 + x^{10} + \cdots + x^{90})(1 + x^{100} + \cdots + x^{900})\cdots. \end{equation*}

What does this tell us about numbers?

(b)

Prove that every non negative integer \(n\) has a unique binary representation.

(c)

Find a simple expression for

\begin{equation*} (1+x+x^2)(1+x^3+x^6)(1+x^9+x^{18})(1+x^{27}+x^{54})\cdots. \end{equation*}

How can you interpret this result?