# 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

• I assume that first way should be a 4. – Mike Jul 21 '12 at 19:29

## 3 Answers

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. – Jemmy 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?

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

• But the Euler problem doesn't have the restriction that $a_k \le a_1+1$ – Ross Millikan Jul 22 '12 at 15:40
• @RossMillikan Thus I qualified my statment with the word "variation." – Code-Guru Jul 22 '12 at 17:37