Partitions with at most k parts, each of at most l

Question

I'm taking a course on Analytics Combinatorics (based on Flajolet's and Sedwick's book), and i'm trying to solve note I.16 of the book, that is, verify:

$$ P^{(\leq l, \{1,\ldots,k\})}(z) = \frac{(1-z)\ldots(1-z^{k+l})}{((1-z)\ldots(1-z^{k}))\cdot((1-z)\ldots(1-z^{l}))} $$ Where the left hand means the generating function of the class of partitions with at most k parts, each $ \leq l $ Truth is I already tried by multiple ways, but with no success:

First, looking at the formula I guessed that: $$ P^{(\leq l, \{1,\ldots,k\})} \times P^{(\{1,\ldots,k +l\})} \tilde = P^{(<l)} \times P^{(\{1,\ldots,k\})} $$ but i couldn't understand why.

Secondly, using the same reasoning as to find that p(k,l,n) = p(l,k-1,n) + p(l-1,k,n -k), I thought that:

$$ P^{(\leq l, \{1,\ldots,k\})} \tilde = P^{(\leq l, \{1,\ldots,k-1\})} +\mathcal Z^k \times P^{(\leq l - 1, \{1,\ldots,k\})} $$

but i could't solve the recurrence.

and so on...

As you can see, I'm quite confused... can someone give a tip that put me in my way? thank you in advanced!

Answer 1

Let $p(l,k,n)$ denote the number of partitions of $n$ into at most $k$ parts each $\leq l$. Observe that \begin{align*} p(l,k,n)&=0\qquad\qquad\text{if } n>kl\\ p(l,k,kl)&=1 \end{align*} Therefore the generating function \begin{align*} P^{(\leq l, \{1,\ldots,k\})}(z)=\sum_{n\geq 0}p(l,k,n)z^n\tag{1} \end{align*} is a polynomial in $z$ of degree $kl$.

Introducing the short-hand notation $(z)_p=(1-z)(1-z^2)\cdots (1-z^p)$, we want to show for $k,l\geq 0$ \begin{align*} P^{(\leq l, \{1,\ldots,k\})}(z)=\frac{(z)_{l+k}}{(z)_l(z)_k}\tag{2} \end{align*}

Recurrence relation for $p(l,k,n)$:

We observe $$p(l,k,n)-p(l,k-1,n)$$ enumerates the number of partitions of $n$ into exactly $k$ parts, each $\leq l$. We transform each of these partitions by deleting every $1$ that is a part, and subtracting $1$ from each part larger than $1$. The resulting partitions of $n-k$ have at most $k$ parts and each part is $\leq l-1$.

Since this transformation is reversible, it establishes a bjiection between the partitions enumerated by $p(l,k,n)-p(l,k-1,n)$ and those enumerated by $p(l-1,k,n-k)$. Therefore \begin{align*} p(l,k,n)-p(l,k-1,n)=p(l-1,k,n-k)\tag{3} \end{align*} Thus (3) corresponds with respect to the generating function in (1) to \begin{align*} P^{(\leq l, \{1,\ldots,k\})}(z)-P^{(\leq l, \{1,\ldots,k-1\})}(z)=z^kP^{(\leq l-1, \{1,\ldots,k\})}(z)\tag{4} \end{align*}

We have the boundary conditions \begin{align*} p(l,0,n)=p(0,k,n)= \begin{cases} 1&\qquad \text{ if } k=l=n=0\\ 0&\qquad \text{ otherwise} \end{cases} \end{align*} since the empty partition of $0$ is the only partition in which no part is positive and is also the only partition in which the number of parts is nonpositive.

This corresponds with respect to (1) to \begin{align*} P^{(\leq l, \{0\})}(z)=P^{(0, \{1,\ldots,k\})}(z)=1 \end{align*}

We want to show that the right hand side of (2) fulfils the same recurrence relation as (4). We introduce the short-hand notation $Q^{(l,k)}(z)$ and define \begin{align*} Q^{(l,k)}(z):=\frac{(z)_{l+k}}{(z)_l(z)_k} \end{align*}

Recurrence relation for $Q^{(l,k)}(z)$:

We obtain \begin{align*} Q^{(l,k)}(z)-Q^{(l,k-1)}(z)&=\frac{(z)_{l+k}}{(z)_l(z)_k}-\frac{(z)_{l+k-1}}{(z)_l(z)_{k-1}}\\ &=\frac{(z)_{l+k-1}}{(z)_l(z)_k}\left[\left(1-z^{l+k}\right)-\left(1-z^k\right)\right]\\ &=\frac{(z)_{l+k-1}}{(z)_l(z)_k}z^k\left(1-z^l\right)\\ &=z^k\frac{(z)_{l+k-1}}{(z)_{l-1}(z)_k}\\ &=z^kQ^{(l-1,k)}(z) \end{align*}

We also have \begin{align*} Q^{(l,0)}(z)=Q^{(0,k)}(z)=1 \end{align*}

Conclusion: Since $Q^{(l,k)}(z)$ and $P^{(\leq l, \{1,\ldots,k\})}(z)$ satisfy the same initial conditions and the same defining recurrence they are identical and the claim follows.

Note: This answer is more or less verbatim Theorem 3.1 of The Theory of Partitions by G.E. Andrews.

Answer 2

These are the partitions whose Ferrers diagrams fit into a $k$-by-$l$ rectangle. Their generating functions are the Gaussian binomial coefficients or "$q$-binomial coefficients" as given by your formula.