Partitioning and Generating Functions

Question

I am trying to solve $$P_k(x) = \sum_{n} p_k(n)x^n$$, which should give the number of ways to partition a set of size $n$ into exactly $k$ parts. So far, I have attempted to solve this simply by writing $$\frac{1}{(1-x)(1-x^2)...(1-x^k)}$$ since this should give the number of ways to partition a set of size $n$ into $k \geq 1$ parts.

How should I add the "exactly $k$ partitions" part of the problem to this question? Thanks!

Answer 1

The generating function $P^{(\leq k)}(x)$ for the number of partitions which consists of parts each $\leq k$ is \begin{align*} P^{(\leq k)}(x)&=(1+x+x^2+x^3+\cdots)\\ &\qquad\cdot(1+x^2+x^4+x^6+\cdots)\\ &\qquad\cdot(1+x^3+x^6+x^9+\cdots)\\ &\qquad\qquad\qquad\cdots\\ &\qquad\cdot(1+x^k+x^{2k}+x^{3k}+\cdots)\\ &=\frac{1}{(1-x)(1-x^2)(1-x^3)\cdots(1-x^k)} \end{align*}

Note: An interesting aspect is the number of partitions having parts each $\leq k$ is the same as the number of partitions having at most $k$ parts.

If we use Ferrer diagrams to visualise the situation (here with $k=3$ and $n=8$) we see that each partition containing parts each $\leq 3$ which is reflected at the main diagonal corresponds with a partition containing at most $3$ parts.

                                

Since this correspondence is bijective the generating function is the same in both cases.

We conclude a generating function $P^{(=k)}(x)$ for the number of partitions with exactly $k$ parts is \begin{align*} \color{blue}{P^{(=k)}(x)}&=P^{(\leq k)}(x)-P^{(\leq k-1)}(x)\\ &=\frac{1}{(1-x)(1-x^2)\cdots(1-x^k)}\\ &\qquad-\frac{1}{(1-x)(1-x^2)\cdots(1-x^{k-1})}\\ &=\frac{1}{(1-x)(1-x^2)\cdots(1-x^{k-1})}\left(\frac{1}{1-x^k}-1\right)\\ &=\color{blue}{\frac{x^k}{(1-x)(1-x^2)\cdots(1-x^k)}}\\ \end{align*}