# 3.3: Partitions of Integers

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

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 \(tao = 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\) 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\) 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\) 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}\)?

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\) 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?

162. How does the number of partitions of \(k\) relate to the number of partitions of \(k + 1\) whose smallest part is one? Online 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.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 3.1: The Ferrers and Young diagrams of the partition \((5,3,3,2)\).*

\(\bullet\) 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)\). Online hint.

\(\bullet\) 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.2 for an example. What is the conjugate of \((4,4,3,1,1)\)? How is the largest part

*Figure 3.2: The Ferrers diagram the partition \((5,3,3,2)\) and its conjugate.*

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\)? Online hint.

\(\rightarrow\) 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. Online hint.

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

\(\rightarrow\) 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\)). Online hint.

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.

*Figure 3.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.*

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

170. Show that \(P(k, n)\) is at least \(\frac{1}{n!}\binom{k-1}{n-1}\). Online 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\) 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

- 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? Online hint.
- 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.) Online hint.
- 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.) Online hint.
- 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. Online hint.
- What is \(P(k, 1)\) for a positive integer \(k\)?
- What is \(P(k, k)\) for a positive integer \(k\)?
- Use your recurrence to compute a table with the values of P(k, n)

for values of \(k\) between 1 and 7. - 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)\)? Online 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 Figure 3.2. 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.2. It would be worthwhile to try to write them all down! The methods we used to complete Figure 3.2 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.2: The number of ways to distribute \(k\) objects to \(n\) recipients, with restrictions on how the objects are received*

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

172. Show that

\[Q(k,n) \leq \frac{1}{n!}\binom{k-1}{n-1}\].

\(\rightarrow\) 173. Show that the number of partitions of seven into three parts equals

the number of partitions of 10 into three distinct parts. Online hint.

\(\rightarrow \cdot\) 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. Online hint.

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

\(\rightarrow *\) 176. Show that the number of partitions of \(k\) into distinct parts equals the number of partitions of \(k\) into odd parts. Online hint.

\(\rightarrow *\) 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. Online hint.

### 3.3.5 Supplementary Problems

1. Answer each of the following questions with \(n^{k}, k^{n}, n!, k!, \binom{n}{k}, \binom{k}{n}, n^{\underline{k}}, k^{\underline{n}}, n^{\bar{k}}, k^{\bar{n}}, \binom{n+k-1}{k}, \binom{n+k-1}{k}, \binom{n-1}{k-1}, \binom{k-1}{n-1}, or “none of the above.”

- In how many ways may we pass out \(k\) identical pieces of candy to \(n\) children?
- In how many ways may we pass out \(k\) distinct pieces of candy to \(n\) children?
- In how many ways may we pass out \(k\) identical pieces of candy to \(n\) children so that each gets at most one? (Assume \(k \leq n\).)
- In how many ways may we pass out \(k\) distinct pieces of candy to \(n\) children so that each gets at most one? (Assume \(k \leq n\).)
- In how many ways may we pass out \(k\) distinct pieces of candy to \(n\) children so that each gets at least one? (Assume \(k \geq n\).)
- In how many ways may we pass out \(k\) identical pieces of candy to \(n\) children so that each gets at least one? (Assume \(k \geq n\).)

2. The neighborhood betterment committee has been given \(r\) trees to distribute to \(s\) families living along one side of a street. Unless otherwise specified, it doesn’t matter where a family plants the trees it gets.

- In how many ways can they distribute all of them if the trees are distinct, there are more families than trees, and each family can get at most one?
- In how many ways can they distribute all of them if the trees are distinct and any family can get any number?
- In how many ways can they distribute all the trees if the trees are identical, there are no more trees than families, and any family receives at most one?
- In how many ways can they distribute them if the trees are distinct, there are more trees than families, and each family receives at most one (so there could be some leftover trees)?
- In how many ways can they distribute all the trees if they are identical and anyone may receive any number of trees?
- In how many ways can all the trees be distributed and planted if the trees are distinct, any family can get any number, and a family must plant its trees in an evenly spaced row along the road?
- Answer the question in Part 2f assuming that every family must get a tree.
- Answer the question in Part 2e assuming that each family must get at least one tree.

3. In how many ways can n identical chemistry books, \(r\) identical mathematics books, \(s\) identical physics books, and \(t\) identical astronomy books be arranged on three bookshelves? (Assume there is no limit on the number of books per shelf.)

\(\rightarrow\) 4. One formula for the Lah numbers is

\[L(k,n) = \binom{k}{n}(k-1)^{\underline{k-n}}\]

Find a proof that explains this product.

5. What is the number of partitions of \(n\) into two parts?

\(\cdot\) 6. What is the number of partitions of \(k\) into \(k − 2\) parts?

7. Show that the number of partitions of \(k\) into \(n\) parts of size at most \(m\) equals the number of partitions of \(mn − k\) into no more than \(n\) parts of size at most \(m − 1\).

8. Show that the number of partitions of \(k\) into parts of size at most \(m\) is equal to the number of partitions of \(k + m\) into \(m\) parts.

9. You can say something pretty specific about self-conjugate partitions of \(k\) into distinct parts. Figure out what it is and prove it. With that, you should be able to find a relationship between these partitions and partitions whose parts are consecutive integers, starting with 1. What is that relationship?

10. What is \(s(k, 1)\)?

11. Show that the Stirling numbers of the second kind satisfy the recurrence

\[S(k,n) = \sum\limits^{k}_{i=1} S(k-i,n-1)\binom{k-1}{i-1}\].

\(\rightarrow\) 12. Let \(c(k, n)\) be the number of ways for \(k\) children to hold hands to form \(n\) circles, where one child clasping his or her hands together and holding them out to form a circle is considered a circle. (Having Mary hold Sam’s right hand is different from having Mary hold Sam’s left hand.) Find a recurrence for \(c(k, n)\). Is the family of numbers \(c(k, n)\) related to any of the other families of numbers we have studied? If so, how?

\(\rightarrow\) 13. How many labeled trees on \(n\) vertices have exactly four vertices of degree 1?

\(\rightarrow\) 14. The degree sequence of a graph is a list of the degrees of the vertices in non-increasing order. For example the degree sequence of the first graph in Figure 2.4 is \((4, 3, 2, 2, 1)\). For a graph with vertices labeled 1 through \(n\), the ordered degree sequence of the graph is the sequence \(d_{1}, d_{2}, . . . d_{n}\) in which \(d_{i}\) is the degree of vertex \(i\). For example the ordered degree sequence of the first graph in Figure 2.2 is \((1, 2, 3, 3, 1, 1, 2, 1)\).

- How many labeled trees are there on \(n\) vertices with ordered degree sequence \(d_{1}, d_{2}, . . . ,d_{n}\)?
- * How many labeled trees are there on \(n\) vertices with with the degree sequence in which the degree \(d\) appears \(i_{d}\) times?