The very interesting history of the theory of linear partitions dates back to the Middle Ages, where certain special problems in partitions were encountered. The first major discoveries were made by L. Euler in the 18th century, followed by contributions by Cayley, Gauss, Hardy, Jacobi, Lagrange, Legendre, Littlewoood, Rademacher, Ramanujan, Schur, and Sylvester.
Our history with linear partitions started in Section 3.1. Recall that a partition of the number \(k\) is a tuple of positive integers \(\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_n)\) such that \(\lambda_1 + \lambda_2 + \cdots + \lambda_n = k\) and \(\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n\text{.}\) Taking the terms in the sum to be non-increasing is our way of ensuring that we do not count one partition listed in a different order twice.
We use \(p(k)\) for the number of partitions of \(k\text{,}\) and \(p_n(k)\) for the number of partitions of \(k\) into exactly \(n\) parts. The sequence \((p(k))_{k \ge 1}\) starts,
We can use a recurrence relation for \(p_n(k) = \sum_{i=1}^n p_i(k-n)\) (see Activity 215) to give us a triangle of values for \(p_n(k)\text{,}\) which starts,
| \(k\backslash n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 3 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 4 | 1 | 2 | 1 | 1 | 0 | 0 | 0 |
| 5 | 1 | 2 | 2 | 1 | 1 | 0 | 0 |
| 6 | 1 | 3 | 3 | 2 | 1 | 1 | 0 |
| 7 | 1 | 3 | 4 | 3 | 2 | 1 | 1 |
Let's now take a closer look at integer partitions and discover some properties about them and the numbers \(p(k)\) and \(p_n(k)\text{.}\)
Recall that a Ferrers diagram or Young diagram can be used to visually represent a partition. The partition \(\lambda = (\lambda_1,\lambda_2,\ldots \lambda_n)\text{,}\) is represented with an array of \(n\) left-justified rows, the \(i\)th row consisting of \(\lambda_i\) equally spaced dots or squares. See Figure 3.6.1
Our goal is to use geometric reasoning about these diagrams (we will generally use the Young diagram with squares) to uncover properties of partitions.
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).
Draw a line through the top-left corner and bottom-right corner of the top-left box.
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.6.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{?}\)
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?
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.
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.
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).
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.
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\)).
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?
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.6.4.
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?
Consider two cases, \(m' \gt m\) and \(m' = m\text{.}\)
What conditions on \(m'\) and \(n'\) guarantee that the complement has the same largest part as the original one?
Consider two cases, \(n' \gt n\) and \(n' = n\text{.}\)
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?
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?
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.
Often \(q_n(k)\) is used to denote the number of partitions of \(k\) into distinct parts, that is, parts that are different from each other.
Show that
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?
Show that the number of partitions of 7 into 3 parts equals the number of partitions of 10 into three distinct parts.
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.
There is a relationship between \(p_n(k)\) and \(q_n(m)\) for some other number \(m\text{.}\) Find the number \(m\) that gives you the nicest possible relationship.
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{.}\)
Find a recurrence that expresses \(q_n(k)\) as a sum of \(q_m(k-n)\) for appropriate values of \(m\text{.}\)
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?
Show that the number of partitions of \(k\) into distinct parts equals the number of partitions of \(k\) into odd parts.
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.
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.
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.
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.
This is a good place to apply the product principle for picture enumerators.
Recall that a partition of an integer \(k\) is a multiset of numbers that adds to \(k\text{.}\) In Activity 316 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. Write your answers in this notation. 9 The reason for this change in the notation relates to the subject of finite fields in abstract algebra, where \(q\) is the standard notation for the size of a finite field. While we will make no use of this connection, it will be easier for you to read more advanced work if you get used to the different notation.
Give the generating function for the number partitions of an integer into parts of size one through ten.
The product principle for generating functions helps you break the generating function into a product of ten simpler ones.
Give the generating function for the number of partitions of an integer \(k\) into parts of size at most \(m\text{,}\) 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.)
\(m\) was 10 in the previous part of this problem.
In Task 317.b you gave the generating function for the number of partitions of an integer into parts of size at most \(m\text{.}\) 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\text{.}\)
Think about conjugate partitions.
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\text{.}\)
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.
Don't be afraid of writing down a product of infinitely many power series.
Find the coefficient of \(q^4\) in this generating function.
From the fifth factor on, there is no way to choose a \(q^i\) that has \(i\) nonzero and less than five from the factor.
Find the coefficient of \(q^5\) in this generating function.
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.
Describe to yourself how to get the coefficient of a given power of \(q\text{.}\)
Rewrite any power series that appear in your product as quotients of polynomials or as integers divided by polynomials.
In Activity 319, we multiplied together infinitely many power series. Here are two notations for infinite products that look rather similar:
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 a product of the form
where each \(p_i(x)\) is a nonzero polynomial in \(x\) to make sense, 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.)
If infinitely many of the polynomials had a nonzero coefficient for \(q\text{,}\) would the product make any sense?
What is the generating function (using \(q\) for the variable) for the number of partitions of an integer in which each part is even?
\((1 + q^2 + q^4 )(1 + q^3 + q^9 )\) is the generating function for partitions of an integer into at most two twos and at most two threes.
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?
\((1 + q^2 + q^4 )(1 + q^3 + q^9 )\) is the generating function for partitions of an integer into at most two twos and at most two threes. (This is intentionally the same hint as in the previous problem, but it has a different point in this problem.)
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 number of partitions of an integer in which each part is even.
In the power series \(\sum_{j=0}^\infty q^{2ij}\text{,}\) the \(2ij\) has a different interpretation if you think of it as \((2i) \cdot j\) or if you think of it as \(i \cdot (2j)\text{.}\)
Use the fact that
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.
Note that
Prove that
What does this tell us about numbers?
Prove that every non negative integer \(n\) has a unique binary representation.
Find a simple expression for
How can you interpret this result?
Write down the generating function for the number of ways to partition an integer into parts of size no more than \(m\text{,}\) 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\text{,}\) 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.
Note that \(q^i + q^{3i} + q^{5i} + \cdots = q^i (1 + q^2 + q^4 + \cdots)\text{.}\)
In Task 317.b and Activity 318 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\text{.}\) That is we will analyze \(\sum_{i=0}^\infty a_kq^k\) where \(a_k\) is the number of partitions of \(k\) into at most \(n\) parts, the largest of which is at most \(m\text{.}\) Geometrically, it is the generating function for partitions whose Young diagram fits into an \(m\) by \(n\) rectangle, as in Activity 307. This generating function has significant analogs to the binomial coefficient \(\binom{m+n}{n}\text{,}\) and so it is denoted by \(\qchoose{m+n}{n}\text{.}\) It is called a \(q\)-binomial coefficient.
Compute \(\qchoose{4}{2}=\qchoose{2+2}{2}\text{.}\)
We want to calculate the number of partitions whose Young diagrams fit into a two by two square. These partitions have at most two parts and the parts have size at most two. Thus they are partitions of 1, 2, 3, or 4. However not all partitions of 3 or 4 have diagrams that fit into a two by two square. Try writing down the relevant diagrams.
Find explicit formulas for \(\qchoose{n}{1}\) and \(\qchoose{n}{n-1}\text{.}\)
They are the generating function for the number of partitions whose Young diagram fits into a rectangle \(n - 1\) units wide and 1 unit deep or into a rectangle 1 unit wide and \(n - 1\) units deep respectively.
How are \(\qchoose{m+n}{n}\) and \(\qchoose{m+n}{n}\) related? Prove it. (Note this is the same as asking how \(\qchoose{r}{s}\) and \(\qchoose{r}{r-s}\) are related.)
How can you get a diagram of a partition counted by partition is counted by \(\qchoose{m+n}{n}\) from one whose partition is counted by \(\qchoose{m+n}{m}\text{?}\)
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 \(\qchoose{m+n}{n}= \qchoose{m+n-1}{n-1}+\qchoose{m+n-1}{n}\text{?}\)
Recall the two operations we studied in Activity 215.
The largest part of a partition counted by \(\qchoose{m+n}{n}\) is either \(m\) or is less than or equal to \(m-1\text{.}\) 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\text{?}\) What recurrence relation does this give you?
What recurrence do you get from the other operation we studied in Activity 215?
It is quite likely that the two recurrences you got are different. One would expect that they might give different values for \(\qchoose{m+n}{n}\text{.}\) Can you resolve this potential conflict?
Think about geometric operations on Young Diagrams
Define \([n]_q\) to be \(1+q+\cdots+q^{n-1}\) for \(n>0\) and \([0]_q =1\text{.}\) We read this simply as \(n\)-sub-\(q\text{.}\) Define \([n]!_q\) to be \([n]_q[n-1]_q\cdots [3]_q[2]_q[1]_q\text{.}\) We read this as \(n\) cue-torial, and refer to it as a \(q\)-ary factorial. Show that
How would you use the Pascal recurrence to prove the corresponding result for binomial coefficients?
Now think of \(q\) as a variable that we will let approach \(1\text{.}\) Find an explicit formula for
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\text{?}\) Can you explain bijectively why this quantity equals the formula you got?
For finding a bijection, think about lattice paths.
What happens to \(\qchoose{m+n}{n}\) if we let \(q\) approach \(-1\text{?}\)
If you could prove \(\qchoose{m+n}{n}\) is a polynomial function of \(q\text{,}\) what would that tell you about how to compute the limit as \(q\) approaches \(-1\text{?}\)
Try computing a table of values of \(\qchoose{m+n}{n}\) with \(q=-1\) by using the recurrence relation. Make a pretty big table so you can see what is happening.