Putnam Problem: Partitioning integers with generating functions

Question

We were given the following A-1 problem from the 2003 Putnam Competition:

Let $n$ be a fixed positive integer. How many ways are there to write $n$ as a sum of positive integers, $$ n= a_1+a_2+ \cdots + a_k$$ With $k$ an arbitrary positive integer, and $a_1 \le a_2 \le \cdots \le a_k \le a_1+1$. For example, with $n=4$ there are 4 ways: 2, 2+2, 1+1+2, 1+1+1+1.

I managed to do this by induction, showing that there are always $n$ ways to partition an integer in such a way. In my combinatorics class however, we always solved integer partitioning problems with generating functions and I have been unable to construct one for this problem. I was wondering if the math.stackexchange community could help me out with this and at least give me a nudge in the right direction.

Thanks

Answer 1

Recall exponential notation for partitions: $a^b$ signifies $b$ occurrences of $a$ in the partition. (Exponential notation can be useful for seeing the generating functions.) In exponential notation, every partition satisfying your constraints are of the form $m^k (m+1)^l$. In your $n = 4$ example, the partitions are $4^1 5^0$, $2^2 3^0$, $1^2 2^1$, and $1^4 2^0$. Notice that the smaller number, $a_1$, must have exponent at least $1$, while successor can have exponent $0$.

For a fixed $m$, the contributions from partitions of the form $m^k (m+1)^l$ are given by the following generating function:

$$(x^m + x^{2m} + x^{3m} + \cdots)(1 + x^{m+1} + x^{2(m+1)} + \cdots)$$

This simplifies to:

$$\frac{x^m}{1-x^m} \frac{1}{1-x^{m+1}}$$

Such contributions come from any $m \geq 1$, and of course, the contributions are disjoint. Thus the full generating function is:

$$\sum_{m \geq 1} \frac{x^m}{1-x^m} \frac{1}{1-x^{m+1}}$$

This might already be too great a nudge, but the point is that you now obtain something you can manipulate. After some obvious $1 - x$ factorings and some telescoping, I get $\frac{x}{(1 - x)^2}$, a generating function for $n$, as desired. Let me know if you get similar results or not.

Answer 2

This does not really answer the question in the sense that it uses no generating functions. But think of the problem of partitioning any positive number $n$ into a given number $k$ of parts, with $1\leq k\leq n$, as equitably as possible, in the sense that no two parts differ by more than $1$ (for if they did, one could make it more equitable by moving a unit from the larger to the smaller part). One solution is to first make $k$ equal parts of size $\lfloor n/k\rfloor$, and then if $k$ does not evenly divide $n$ distribute the remaining $n\bmod k$ units by assigning them randomly to distinct parts, making those $\lceil n/k\rceil$ (since the order of parts are not taken into account, it makes no difference which). Can you see why there are no other such equitable partitions of $n$ into $k$ parts? Once this is established, these are clearly the $n$ possible solutions of your problem, one for every $k$.

Personally, with such a complete description of the solution available, I'm mentally blocked to think how generating functions could be used to find an alternative solution. In fact, I think that the requirement that relates the sizes of different parts (limiting their difference to at most $1$) does not easily translate into the world of generating functions (as one can do for independent conditions on the size of parts, or on multiplicities of a given size).

Answer 3

Consider the integer $n$. How are it's partitions related to the partitions of those of integers $k$ where $1 \le k < n$? Can you find a recursive function that relates these?

(FYI, Project Euler, Problem 76 is a variation of this question.)