# Putnam Problem: Partitioning integers with generating functions

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

-
fixed, thank you –  Jeremy Jul 21 '12 at 15:58
I assume that first way should be a 4. –  Mike Jul 21 '12 at 19:29

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.

-

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).

-
This is a very pleasing solution, one that I prefer to a generating function based solution. As noted in the answer I gave, these partitions are uniquely realizable in exponential form as $m^k (m+1)^l$, where $k \geq 1$ and $l \geq 0$. So, there is a generating function approach, and as far as I can tell, the answer can be obtained solely using generating functions. –  Hugh Denoncourt Jul 22 '12 at 17:16
Yes I prefer this as well and is essentially the reasoning I used in my original solution, but I was looking for a different way, really to brush up on generating functions. –  Jeremy Jul 22 '12 at 20:14
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?
But the Euler problem doesn't have the restriction that $a_k \le a_1+1$ –  Ross Millikan Jul 22 '12 at 15:40