3.3: Partitions of Integers

We have now completed all our distribution problems except for those in which both the objects and the recipients are identical. For example, we might be putting identical apples into identical paper bags. In this case, all that matters is how many bags get one apple (how many recipients get one object), how many get two, how many get three, and so on. Thus, for each bag, we have a number, and the multiset of numbers of apples in the various bags is what determines our distribution of apples into identical bags. A multiset of positive integers that add to \(n\) is called a partition of \(n\). 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 \(P(k)\); in computing the partitions of \(3\) we showed that \(P(3) = 3\). It is traditional to use Greek letters like \(\lambda\) (the Greek letter \(\lambda\) is pronounced LAMB duh) to stand for partitions; we might write \(\lambda = 1, 1, 1\), \(\rho = 2, 1\) and \(\tau = 3\) to stand for the three partitions of three. We also write \(\lambda = 1^{3}\) as a shorthand for \(\lambda = 1, 1, 1\), and we write a \(3\) as a shorthand for “\(\lambda\) is a partition of three.”

\(\circ\) Exercise \(157\)

Find all partitions of \(4\) and find all partitions of \(5\), thereby computing \(P(4)\) and \(P(5)\).

3.3.1: The Number of Partitions of \(k\) into \(n\) parts

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

\(\circ\) Exercise \(158\)

Find \(P(6, 3)\) 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?

3.3.2: Representations of Partitions

\(\circ\) Exercise \(159\)

How many solutions are there in the positive integers to the equation \(x_{1} + x_{2} + x_{3} = 7\) with \(x_{1} \geq x_{2} \geq x_{3}\)?

Exercise \(160\)

Explain the relationship between partitions of \(k\) into \(n\) parts and lists \(x_{1}, x_{2},. . . , x_{n}\) of positive integers that add to \(k\) with \(x_{1} \geq x_{2} \geq . . . \geq x_{n}\). Such a representation of a partition is called a decreasing list representation of the partition.

\(\circ\) Exercise \(161\)

Describe the relationship between partitions of k and lists or vectors \((x_{1}, x_{2}, . . . , x_{n})\) such that \(x_{1}+2x_{2}+. . . kx_{k} = k\). 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)\). What is the decreasing list representation for this partition, and what number does it partition?

Exercise \(162\)

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

When we write a partition as \(\lambda = \lambda_{1}, \lambda_{2}, . . . , \lambda_{n}\), 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}, . . . , t_{m})\) for a partition, we write either \(\lambda = 1^{t_{1}}2^{t_{2}} · · ·m^{t_{m}}\) or \(\lambda = m^{t_{m}}(m−1)t^{m−1} · · · 2^{t_{2}}1^{t_{1}}\). Henceforth we will use the second of these. When we write \(\lambda = \lambda^{i1}_{1}\lambda^{i2}_{2} · · · \lambda^{in}_{n}\), we will assume that \(\lambda_{i} > \lambda_{i+1}\).

3.3.3: Ferrers and Young Diagrams and the Conjugate of a Partition

The decreasing list representation of partitions leads us to a handy way to visualize partitions. Given a decreasing list \((\lambda_{1}, \lambda_{2}, . . . \lambda_{n})\), 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 3.3.1 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 \(\PageIndex{1}\): The Ferrers and Young diagrams of the partition \((5,3,3,2)\). (Copyright; author via source)

\(\bullet\) Exercise \(163\)

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).

\(\bullet\) Exercise \(164\)

The partition \((\lambda_{1}, \lambda_{2}, . . . , \lambda_{n})\) is called the conjugate of the partition \((\rho_{1}, \rho_{2}, . . . , \rho_{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. See Figure 3.3.2 for an example.

Figure \(\PageIndex{2}\): The Ferrers diagram the partition \((5,3,3,2)\) and its conjugate. (Copyright; author via source)

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

\(\rightarrow\) Exercise \(165\)

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).

Exercise \(166\)

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).

\(\rightarrow\) Exercise \(167\)

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).

Exercise \(168\)

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\). 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` \geq m\) and \(n` \geq n\), as in Figure 3.3.3.

Figure \(\PageIndex{3}\): 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. (Copyright; author via source)

1. 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.
2. What integer is being partitioned by the complement?
3. What conditions on \(m'\) and \(n'\) guarantee that the complement has the same number of parts as the original one? (Hint).
4. What conditions on \(m'\) and \(n'\) guarantee that the complement has the same largest part as the original one? (Hint).
5. Is it possible for the complement to have both the same number of parts and the same largest part as the original one?
6. 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?

\(\rightarrow\) Exercise \(169\)

Suppose we take a partition of \(k\) into \(n\) parts with largest part \(m\), 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).

Exercise \(170\)

Show that \(P(k, n)\) is at least \(\frac{1}{n!}\binom{k-1}{n-1}\). (Hint).

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 of numbers if we remove the largest element of \(S\). 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 can ask what we could remove from a Young diagram to get a Young diagram. Two natural ways to get a partition of a smaller integer from a partition of \(n\) would be to remove the top row of the Young diagram of the partition and to remove the left column of the Young diagram of the partition. These two operations correspond to removing the largest part from the partition and to subtracting \(1\) from each part of the partition respectively. Even though they are symmetric with respect to conjugation, they aren’t symmetric with respect to the number of parts. Thus one might be much more useful than the other for finding a recurrence for the number of partitions of \(k\) into \(n\) parts.

\(\rightarrow \; \cdot\) Exercise \(171\)

In this problem, we will study the two operations and see which one seems more useful for getting a recurrence for \(P(k, n)\). Part of the reason

1. How many parts does the remaining partition have when we remove the largest part (more precisely, we reduce its multiplicity by one) from a partition of \(k\) into \(n\) parts? (A geometric way to describe this is that we remove the first row from the Young diagram of the partition.) What can you say about the number of parts of the remaining partition if we remove one from each part? (Hint).
2. If we remove the largest part from a partition, what can we say about the integer that is being partitioned by the remaining parts of the partition? If we remove one from each part of a partition of \(k\) into \(n\) parts, what integer is being partitioned by the remaining parts? (Another way to describe this is that we remove the first column from the Young diagram of the partition.) (Hint).
3. The last two questions are designed to get you thinking about how we can get a bijection between the set of partitions of \(k\) into \(n\) parts and some other set of partitions that are partitions of a smaller number. These questions describe two different strategies for getting that set of partitions of a smaller number or of smaller numbers. Each strategy leads to a bijection between partitions of \(k\) into \(n\) parts and a set of partitions of a smaller number or numbers. For each strategy, use the answers to the last two questions to find and describe this set of partitions into a smaller number and a bijection between partitions of \(k\) into \(n\) parts and partitions of the smaller integer or integers into appropriate numbers of parts. (In one case the set of partitions and bijection are relatively straightforward to describe and in the other case not so easy.) (Hint).
4. Find a recurrence (which need not have just two terms on the right hand side) that describes how to compute \(P(k, n)\) in terms of the number of partitions of smaller integers into a smaller number of parts. (Hint).
5. What is \(P(k, 1)\) for a positive integer \(k\)?
6. What is \(P(k, k)\) for a positive integer \(k\)?
7. Use your recurrence to compute a table with the values of P(k, n) for values of \(k\) between \(1\) and \(7\).
8. What would you want to fill into row \(0\) and column \(0\) of your table in order to make it consistent with your recurrence? What does this say \(P(0, 0)\) should be? We usually define a sum with no terms in it to be zero. Is that consistent with the way the recurrence says we should define \(P(0, 0)\)? (Hint).

It is remarkable that there is no known formula for \(P(k, n)\), nor is there one for \(P(k)\). This section is devoted to developing methods for computing values of \(P(n, k)\) and finding properties of \(P(n, k)\) that we can prove even without knowing a formula. Some future sections will attempt to develop other methods.

We have seen that the number of partitions of \(k\) into \(n\) parts is equal to the number of ways to distribute \(k\) identical objects to \(n\) recipients so that each receives at least one. If we relax the condition that each recipient receives at least one, then we see that the number of distributions of \(k\) identical objects to \(n\) recipients is \(\sum^{n}_{i=1}P(k,i)\) because if some recipients receive nothing, it does not matter which recipients these are. This completes rows \(7\) and \(8\) of our table of distribution problems. The completed table is shown in Table 3.3.1. Every entry in that table tells us how to count something. There are quite a few theorems that you have proved which are summarized by Table 3.3.1. It would be worthwhile to try to write them all down! The methods we used to complete Figure 3.3.1 are extensions of the basic counting principles we learned in Chapter 1. The remaining chapters of this book develop more sophisticated kinds of tools that let us solve more sophisticated kinds of counting problems.

Table 3.3.1: The number of ways to distribute \(k\) objects to \(n\) recipients, with restrictions on how the objects are received.
The Twentyfold Way: A Table of Distribution Problems
\(k\) objects and conditions on how they are received	\(n\) recipients and mathematical model for distribution
	Distinct	Identical
1. Distinct no conditions	\(n^k\) functions	\(\sum_{i=1}^{k} S(n,i)\) set partitions (\(≤ n\) parts)
2. Distinct Each gets at most one	\(n^{\underline{k}}\) \(k\)-element permutations	\(1\) if \(k ≤ n\); \(0\) otherwise
3. Distinct Each gets at least one	\(S(k, n)n!\) onto functions	\(S(k, n)\) set partitions (\(n\) parts)
4. Distinct Each gets exactly one	\(k! = n!\) permutations	\(1\) if \(k = n\); \(0\) otherwise
5. Distinct, order matters	\((k + n − 1)^{\underline{k}}\) ordered functions	\(\sum_{i=1}^{n} L(k,i)\) broken permutations (\(≤ n\) parts)
6. Distinct, order matters Each gets at least one	\((k)^{\underline{n}}(k − 1)^{\underline{k−n}}\) ordered onto functions	\(L(k, n) = \binom{k}{n} (k − 1)^{\underline{k−n}}\) broken permutations (\(n\) parts)
7. Identical no conditions	\( \binom{n+k−1}{k} \) multisets	\(\sum_{i=1}^{n} P(k, i)\) number partitions (\(≤ n\) parts)
8. Identical Each gets at most one	\( \binom{n}{k} \) subsets	\(1\) if \(k ≤ n\); \(0\) otherwise
9. Identical Each gets at least one	\( \binom{k−1}{n−1} \) compositions (\(n\) parts)	\(P(k, n)\) number partitions (\(n\) parts)
10. Identical Each gets exactly one	\(1\) if \(k = n\); \(0\) otherwise	\(1\) if \(k = n\); \(0\) otherwise

3.3.4: Partitions Into Distinct Parts

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

Exercise \(172\)

Show that \(Q(k,n) \leq \frac{1}{n!}\binom{k-1}{n-1}\). (Hint).

\(\rightarrow\) Exercise \(173\)

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

\(\rightarrow \; \cdot\) Exercise \(174\)

There is a relationship between \(P(k, n)\) and \(Q(m, n)\) for some other number \(m\). Find the number \(m\) that gives you the nicest possible relationship. (Hint).

\(\cdot\) Exercise \(175\)

Find a recurrence that expresses \(Q(k, n)\) as a sum of \(Q(k − n,m)\) for appropriate values of \(m\). (Hint).

\(\rightarrow *\) Exercise \(176\)

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

\(\rightarrow *\) Exercise \(177\)

Euler showed that if \(k \neq \frac{3j^{2}+j}{2}\), 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).