Number of integer partitions with at most a parts and each with a size of at most b, where a and b are positive integers

Question

Partitions of integers. Let π(n) count the ways that the integer n can be expressed as the sum of positive integers, written in non-increasing order. Thus π(4) = 5, since 4 can be expressed as 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1. Prove that the number of integer partitions with at most a positive parts, all of which are at most b, is $$\binom{a+b}{a}$$ (Example: When a = 2, b = 3, the ten partitions are: 3 + 3, 3 + 2, 3 + 1, 3, 2 + 2, 2 + 1, 2, 1 + 1, 1, empty partition)

According to the book this is from it can be proven by considering each partition as a path from (0,0) to (a,b) but I still can't figure it out

Answer 1

We write every partition in increasing order and with zeroes (i.e. the list in your example would then be $3+3, 2+3, 1+3, 0+3, 2+2, 1+2, 0+2, 1+1, 0+1, 0+0$.)

Then all partitions would have the form $\alpha_1 + \alpha_2 + \ldots + \alpha_a$, where $0 \le \alpha_1 \le \alpha_2 \le \ldots \le \alpha_a \le b$.

For any partition, we create a path from $(0,0)$ to $(a,b)$ as follows:

• Start from $(0,0)$, move up (if necessary) to $(0,\alpha_1)$.
• Move right one unit to $(1,\alpha_1)$.
• Move up (if necessary) to $(1,\alpha_2)$.
• Move right one unit to $(2,\alpha_2)$.

$\kern{100px} \vdots$

• Move right one unit to $(a,\alpha_a)$.
• Move up (if necessary) to $(a,b)$.

The diagram below shows four partitions for $a=3, b=5$ and their corresponding paths. From there it shouldn't be difficult to see that there is a $1$-to-$1$ correspondence between the partitions and the paths. $$ \\ $$