Skip to main content
Mathematics LibreTexts

4.2: Generating Functions for Integer Partitions

  • Page ID
    6111
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\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]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \(\bullet\) Exercise \(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. (Hint).

    \(\bullet\) Exercise \(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 notation1.

    1. Give the generating function for the number of partitions of an integer into parts of size one through ten. (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.) (Hint).

    \(\bullet\) Exercise \(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\). (Hint).

    \(\bullet\) Exercise \(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. (Hint).
    2. Find the coefficient of \(q^{4}\) in this generating function. (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. (Hint).
    5. Rewrite any power series that appear in your product as quotients of polynomials or as integers divided by polynomials.

    \(\rightarrow\) Exercise \(204\)

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

    \[\prod\limits^{\infty}_{i=1}1+x+x^{2}+\dotsc+x^{i} \text{ and } \prod\limits^{\infty}_{i=1}1+x^{i}+x^{2i}+\dotsc+x^{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^{\infty}_{i=1}1+p_{i}(x),\]

    where each \(p_{i}(x)\) is a nonzero polynomial in \(x\), describe a relatively simple assumption about the polynomials \(p_{i}(x)\) that will make the product make sense. If we assumed the terms \(p_{i}(x)\) 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.) (Hint).

    \(\bullet\) Exercise \(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? (Hint).

    \(\bullet\) Exercise \(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? (Hint).

    \(\bullet\) Exercise \(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? (Hint).

    \(\rightarrow \; \bullet\) Exercise \(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. (Hint).

    Exercise \(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. (Hint).

    \(\rightarrow\) Exercise \(210\)

    In Problem 201b and Problem 202 you gave the generating functions 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^{\infty}_{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}\). (Hint).
    2. Find explicit formulas for \(\begin{bmatrix} n \\ 1 \end{bmatrix}_{q}\) and \(\begin{bmatrix} n \\ n-1 \end{bmatrix}_{q}\). (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 \\ s \end{bmatrix}_{q}\) and \(\begin{bmatrix} r \\ r-s \end{bmatrix}_{q}\) are related.) (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? (Hint).
    6. Define \([n]_{q}\) to be \(1+q+\dotsc +q^{n-1}\) for \(n > 0\) and \([0]_{q} = 1\). We read this simply as \(n\)-sub-\(q\). Define \([n]!_{q}\) to be \([n]_{q}[n-1]_{q} \dotsc [3]_{q}[2]_{q}[1]_{q}\). Show that \[\begin{bmatrix} m+n \\ n \end{bmatrix}_{q} = \frac{[m+n]!_{q}}{[m]!_{q}[n]!_{q}}.\] (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? (Hint).
    8. * What happens to \(\begin{bmatrix} m+n \\ n \end{bmatrix}_{q}\) if we let \(q\) approach \(-1\)? (Hint).

    This page titled 4.2: Generating Functions for Integer Partitions is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Kenneth P. Bogart.

    • Was this article helpful?