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 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. Write your answers in this notation. 5 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 Problem 201.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 Problem 203, 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 generating function for 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
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 Problem 201.b 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\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 Problem 167. 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}{m}\) 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 Problem 171.
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 Problem 171?
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.
