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
Best Answer
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.