Problem set 6: Integer Partitions
1 Partitions
1.1 Definition: Integer Partitions
A partition of a positive integer \(n\) is a representation
\[ n=x_1+x_2+\cdots+x_t, \]
where \(x_1,\ldots,x_t\) are positive integers.
A partition is called unordered if two representations are considered identical whenever they differ only in the order of their summands.
For example, the partitions
\[ 5=3+2 \qquad\text{and}\qquad 5=2+3 \]
are identical as unordered partitions.
Otherwise, the partitions are called ordered partitions (also known as compositions).
1.2 Problems
(a) Find the number of ordered partitions of a positive integer \(n\) into exactly \(k\) positive summands.
(b) Find the total number of ordered partitions of \(n\) into positive summands.
(c) How do the answers to parts (a) and (b) change if we allow the summands to be zero?
1.3 Restricted Partitions
Let
\[ f(n;n_1,\ldots,n_k) \]
denote the number of ordered partitions of \(n\) using summands from the set
\[ \{n_1,\ldots,n_k\}. \]
Similarly, let
\[ F(n;n_1,\ldots,n_k) \]
denote the number of unordered partitions of \(n\) using summands from the same set.
Prove the following recurrence relations.
(a)
\[ \begin{aligned} f(n;n_1,\ldots,n_k) &=f(n-n_1;n_1,\ldots,n_k)\\ &\quad+f(n-n_2;n_1,\ldots,n_k)\\ &\quad+\cdots\\ &\quad+f(n-n_k;n_1,\ldots,n_k). \end{aligned} \]
(b)
\[ \begin{aligned} F(n;n_1,\ldots,n_k) &=F(n-n_1;n_1,\ldots,n_k)\\ &\quad+F(n;n_2,\ldots,n_k). \end{aligned} \]
(c) What initial conditions are required for these recurrence relations?
Consider the quantities
\[ f(20;1,4,6,9) \qquad\text{and}\qquad F(20;1,4,6,9). \]
(a) Which of these two quantities is greater?
(b) Calculate both quantities using the recurrence relations from Problem 2.
1.4 Young Diagrams
A Young diagram is a finite collection of cells arranged in left-aligned rows such that the row lengths form a non-increasing sequence.
In other words, each row is no longer than the preceding row.
The weight of a Young diagram is the total number of cells it contains.
The sequence of row lengths determines an unordered partition of the weight of the diagram.
Thus, there is a one-to-one correspondence between:
- Unordered partitions of a positive integer \(n\).
- Young diagrams of weight \(n\).
How many Young diagrams of arbitrary weight have
- at most \(p\) rows;
- at most \(q\) columns?
Several positive integers are written on a blackboard:
\[ a_0,a_1,a_2,\ldots,a_n. \]
On a second blackboard, we write the following numbers:
- \(b_0\): the total number of integers on the first blackboard;
- \(b_1\): the number of integers greater than \(1\);
- \(b_2\): the number of integers greater than \(2\);
- and so on.
We continue as long as the resulting numbers are positive. We stop before writing any zeros.
On a third blackboard, we write the numbers
\[ c_0,c_1,c_2,\ldots, \]
obtained from the numbers on the second blackboard by applying exactly the same procedure.
Prove that the collections of numbers written on the first and third blackboards are identical.
Prove that the number of unordered partitions of
\[ a-b \]
into exactly \(c-1\) positive summands, each not exceeding \(b\), equals the number of unordered partitions of
\[ a-c \]
into exactly \(b-1\) positive summands, each not exceeding \(c\).
Is it true that the number of unordered partitions of \(n\) into exactly \(k\) positive summands equals the number of unordered partitions of \(n\) whose largest summand is exactly \(k\)?
Prove your answer or provide a counterexample.
Prove that the number of unordered partitions of \(n\) into distinct odd positive summands equals the number of symmetric Young diagrams of weight \(n\).
A Young diagram is symmetric if it coincides with its transpose (reflection across the main diagonal).
Which positive integers can be represented as a sum of at least two consecutive positive integers?
In other words, characterize all positive integers \(n\) for which there exist integers
\[ a\geq 1,\qquad k\geq 2, \]
such that
\[ n=a+(a+1)+\cdots+(a+k-1). \]