Problem 157
Find all partitions of 4 and find all partitions of 5, thereby computing \(P(4)\) and \(P(5)\text{.}\)
Section 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\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 \(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\) (the Greek letter \(\lambda\) is pronounced LAMB duh) to stand for partitons; 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."
Subsection 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\text{.}\) 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.
Problem 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?
Subsection 3.3.2 Representations of partitions
¶Problem 159
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{?}\)
Problem 160
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.
Problem 161
Describe the relationship between partitions of \(k\) and lists or 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?
Problem 162
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{.}\)
Subsection 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,\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 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.
Problem 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
Draw a line through the top-left corner and bottom-right corner of the topleft box.
Problem 164
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. See Figure 3.3.2 for an example.
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?
Problem 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
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.
Problem 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
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.
Problem 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
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?
Problem 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\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 3.3.4.
(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?
Problem 169
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
Hint 2
Suppose we take two repetitions of this complementation process. What rows and columns do we remove from the diagram?
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.
Problem 170
Show that \(P(k,n)\) 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?
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 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.
Problem 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)\text{.}\)
(a)
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? What can you say about the number of parts of the remaining partition if we remove one from each part?
Hint
These two operations do rather different things to the number of parts, and you can describe exactly what only one of the operations does. Think about the Young diagram.
(b)
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
Think about the Young diagram. In only one of the two cases can you give an exact answer to the question.
(c)
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
Here the harder part requires that, after removal, you consider a range of possible numbers being partitioned and that you give an upper bound on the part size. However it lets you describe the number of parts exactly.
(d)
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
One of the two sets of partitions of smaller numbers from the previous part is more amenable to finding a recurrence than the other. The resulting recurrence does not have just two terms though.
(e)
What is \(P(k,1)\) for a positive integer \(k\text{?}\)
(f)
What is \(P(k,k)\) for a positive integer \(k\text{?}\)
(g)
Use your recurrence to compute a table with the values of \(P(k,n)\) for values of \(k\) between 1 and 7.
(h)
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)\text{?}\)
Hint
If there is a sum equal to zero, there may very well be a partition of zero.
It is remarkable that there is no known formula for \(P(k,n)\text{,}\) nor is there one for \(P(k)\text{.}\) This section was are 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_{i=1}^n 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.5. There are quite a few theorems that you have proved which are summarized by Table 3.3.5. It would be worthwhile to try to write them all down!
| 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}^n S(k,i)\) set partitions (\(\le n\) parts) |
| 2. Distinct Each gets at most one |
\(n^{\underline{k}}\) \(k\)-element permutations |
1 if \(k\le n\text{;}\) 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\text{;}\) 0 otherwise |
| 5. Distinct, order matters |
\((k+n-1)^{\underline{k}}\) ordered functions |
\(\sum_{i=1}^n L(k,i)\) broken permutations (\(\le 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}^nP(k,i)\) number partitions (\(\le n\) parts) |
| 8. Identical Each gets at most one |
\(\binom{n}{k}\) subsets |
1 if \(k\le n\text{;}\) 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\text{;}\) 0 otherwise |
1 if \(k=n\text{;}\) 0 otherwise |
Subsection 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.
Problem 172
Show that
\begin{equation*}
Q(k,n) \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?
Problem 173
Show that the number of partitions of 7 into 3 parts equals the number of partitions of 10 into three distinct parts.
Hint
While you could simply display partitions of 7 into three parts and partitions of 10 into three parts, we hope you won't. Perhaps you could write down the partitions of 4 into two parts and the partitions of 5 into two distinct parts and look for a natural bijection between them. So the hope is that you will discover a bijection from the set of partitions of 7 into three parts and the partitions of 10 into three distinct parts. It could help to draw the Young diagrams of partitions of 4 into two parts and the partitions of 5 into two distinct parts.
Problem 174
There is a relationship between \(P(k,n)\) and \(Q(m,n)\) 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{.}\)
Problem 175
Find a recurrence that expresses \(Q(k,n)\) as a sum of \(Q(k-n,m)\) 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?
Problem 176
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.
Problem 177
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.