Skip to main content
$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.2: Generating Functions for Integer Partitions

• • Contributed by Kenneth P. Bogart
• Professor (Mathematics) at Dartmouth University

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\bullet$$ 200. 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. Online hint.

$$\bullet$$ 201. Recall that a partition of an integer $$k$$ is a multiset of numbers that
adds to $$k$$. In Problem 200 we found the generating function for the number of partitions of an integer into parts of size 1, 5, 10, and 25. When working with generating functions for partitions, it is becoming standard to use $$q$$ rather than $$x$$ as the variable in the generating function. From now on, write your answers to problems involving generating functions for partitions of an integer in this notation.

1. Give the generating function for the number of partitions of an integer into parts of size one through ten. Online hint.
2. Give the generating function for the number of partitions of an integer $$k$$ into parts of size at most m, 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.) Online hint.

$$\bullet$$ 202. In Problem 201b you gave the generating function for the number of
partitions of an integer into parts of size at most $$m$$. Explain why this is also the generating function for partitions of an integer into at most $$m$$ parts. Notice that this is the generating function for the number of partitions whose Young diagram fits into the space between the line $$y = 0$$ and the line $$y = m$$. Online hint.

$$\bullet$$ 203. When studying partitions of integers, it is inconvenient to restrict ourselves to partitions with at most $$m$$ parts or partitions with maximum part size $$m$$.

1. Give the generating function for the number of partitions of an integer into parts of any size. Don’t forget to use $$q$$ rather than $$x$$ as your variable. Online hint.
2. Find the coefficient of $$q^{4}$$ in this generating function. Online hint.
3. Find the coefficient of $$q^{5}$$ in this generating function.
4. This generating function involves an infinite product. Describe the process you would use to expand this product into as many terms of a power series as you choose. Online hint.
5. Rewrite any power series that appear in your product as quotients of polynomials or as integers divided by polynomials.

$$\rightarrow$$ 204. In Problem 203b, we multiplied together infinitely many power series. Here are two notations for infinite products that look rather similar:

$\prod\limits^{\inf}_{i=1}1+q+q^{2}+\dotsc+q^{i} \text{ and } \prod\limits^{\inf}_{i=1}1+q^{i}+q^{2i}+\dotsc+q^{i^{2}}.$

However, one makes sense and one doesn’t. Figure out which one
makes sense and explain why it makes sense and the other one doesn’t.
If we want to make sense of a product of the form

$\prod\limits^{\inf}_{i=1}1+p_{i}(q),$

where each $$p_{i}(q)$$ is a nonzero polynomial in $$q$$, describe a relatively simple assumption about the polynomials $$p_{i}(q)$$ that will make the product make sense. If we assumed the terms $$p_{i}(q)$$ were nonzero power series, is there a relatively simple assumption we could make about them in order to make the product make sense? (Describe such a condition or explain why you think there couldn’t be one.) Online hint.

$$\bullet$$ 205. What is the generating function (using q for the variable) for the number of partitions of an integer in which each part is even? Online hint.

$$\bullet$$ 206. What is the generating function (using $$q$$ as the variable) for the number of partitions of an integer into distinct parts, that is, in which each
part is used at most once? Online hint.

$$\bullet$$ 207. 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 generating function for the number of partitions of an integer in which each part is even. How does this compare to Problem 166? Online hint.

$$\rightarrow \bullet$$ 208. Use the fact that

$\frac{1-q^{2i}}{1-q^{i}} = 1+q^{i}$

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. Online hint.

209. Write down the generating function for the number of ways to partition an integer into parts of size no more than $$m$$, 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$$, 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. Online hint.

$$\rightarrow$$ 210. for, respectively, the number of partitions of $$k$$ into parts the largest of which is at most $$m$$ and for the number of partitions of $$k$$ into at most $$m$$ parts. In this problem we will give the generating function for the number of partitions of $$k$$ into at most $$n$$ parts, the largest of which is at most $$m$$. That is, we will analyze $$\sum^{\inf}_{i=0}a_{k}q^{k}$$ where $$a_{k}$$ is the number of partitions of k into at most n parts, the largest of which is at most $$m$$. Geometrically, it is the generating function for partitions whose Young diagram fits into an m by n rectangle, as in Problem 168. This generating function has significant analogs to the
binomial coefficient $$\binom{m+n}{n}$$, and so it is denoted by $$\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}$$. It is called a $$q$$-binomial coefficient.

1. Compute $$\begin{bmatrix} 4 \\ 2 \end{bmatrix}_{q} = \begin{bmatrix} 2+2 \\ 2 \end{bmatrix}_{q}$$. Online hint.
2. Find explicit formulas for $$\begin{bmatrix} n \\ 1 \end{bmatrix}_{q}$$ and $$\begin{bmatrix} n \\ n-1 \end{bmatrix}_{q}$$. Online hint.
3. How are $$\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}$$ and $$\begin{bmatrix} m+n \\ m \end{bmatrix}_{q}$$ related? Prove it. (Note this is the same as asking how $$\begin{bmatrix} r \\ a \end{bmatrix}_{q}$$ and $$\begin{bmatrix} r \\ r-a \end{bmatrix}_{q}$$ are related.) Online hint.
4. So far the analogy to $$\binom{m+n}{n}$$ is rather thin! If we had a recurrence
like the Pascal recurrence, that would demonstrate a real analogy. Is $$\begin{bmatrix} m+n \\ n \end{bmatrix}_{q} = \begin{bmatrix} m+n-1 \\ n-1 \end{bmatrix}_{q} + \begin{bmatrix} m+n-1 \\ n \end{bmatrix}_{q}$$?
5. Recall the two operations we studied in Problem 171
1. The largest part of a partition counted by $$\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}$$ is either $$m$$ or is less than or equal to $$m − 1$$. In the second case, the partition fits into a rectangle that is at most $$m − 1$$ units wide and at most $$n$$ units deep. What is the generating function for partitions of this type? In the first case, what kind of rectangle does the partition we get by removing the largest part sit in? What is the generating function for partitions
that sit in this kind of rectangle? What is the generating function for partitions that sit in this kind of rectangle after we remove a largest part of size $$m$$? What recurrence relation does this give you?
2. What recurrence do you get from the other operation we studied in Problem 171?
3. It is quite likely that the two recurrences you got are different. One would expect that they might give different values for $$\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}$$. Can you resolve this potential conflict? Online hint.
6. Define $$[n]_{q}$$ to be $$1+q+\dotsc +q^{n-1}$$ for $$n > 0$$ and $$_{q} = 1$$. We read this simply as $$n$$-sub-$$q$$. Define $$[n]!_{q}$$ to be $$[n]_{q}[n-1]_{q} \dotsc _{q}_{q}_{q}$$. Show that
$\begin{bmatrix} m+n \\ n \end{bmatrix}_{q} = \frac{[m+n]!_{q}}{[m]!_{q}[n]!_{q}}.$
Online hint.
7. Now think of $$q$$ as a variable that we will let approach 1. Find an explicit formula for
1. $$\displaystyle{lim_{q \to 1}[n]_{q}}$$.
2. $$\displaystyle{lim_{q \to 1}[n]!_{q}}$$.
3. $$\displaystyle{lim_{q \to 1}[n]_{q}} \begin{bmatrix} m+n \\ n \end{bmatrix}_{q}$$.
Why is the limit in Part iii equal to the number of partitions (of any number) with at most $$n$$ parts all of size most $$m$$? Can you explain bijectively why this quantity equals the formula you got? Online hint.
8. * What happens to $$\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}$$ if we let $$q$$ approach -1? Online hint.