# Generating function for set partitions

Let $k$ be fixed. For every $n$ denote by $p_{\leq k}(n)$ the number of partitions of the integer $n$, for which each part is at most $k$.

a). Compute $p_{\leq 3}(5)$

b). Compute the generating function for the sequence $p_{\leq k}(0), p_{\leq k}(1),...$

c). Compute the generating function for the sequence $p(0), p(1), p(2), ...$ where $p(n)$ is the number of partitions of $n$.

d). Define a partial order on the set of partitions of $n$, for every $n$. Draw its Hasse Diagram.

The first is simple, just $p_1(5)+p_2(5)+p_3(5)=1+2+1=4$ where $p_k$ means the partition must have $k$ but no higher in it. Then a recurrence relation is that $p_k(n)=S(n,k)-p_{\leq k-1}(n)$

I get lost in (b). Obviously the generating function $G(x)$ would be:

$$G(x)=p_{\leq k}(0)x^0+p_{\leq k}(1)x+p_{\leq k}(2)x^2+...p_{\leq k}(n)x^n$$ $$=p_{\leq k}(0)x^0+p_{\leq k}(1)x+\sum_{i=2}^np_{\leq k}(i)x^i$$

And we know $$p_{\leq k}(n)=p_1(n)+p_2(n)+...p_k(n)=\sum_{j=1}^kp_j(n)$$

Or we can say $p_{\leq k+1}(n)=S(n,k)-p_k(n)$.

I just don't think this is relevant because I don't see how I can plug anything in to simplify the function. I have a feeling I'm letting my thinking get too convoluted, but the more I think about it the more I complicated the process. I just keep going around in circles. I think (c) will follow from (b) using the recursion I described earlier.

You’ve miscalculated $P_{\le 3}(5)$: $p_3(5)=2$, not $1$, the partitions being $3+2$ and $3+1+1$.

For (b), let $x_1,\ldots,x_k$ be distinct indeterminates. A partition of $n$ into $p_i$ parts of size $i$ for $i=1,\ldots,k$ can be represented by $x_1^{p_1}x_2^{2p_2}\ldots x_k^{kp_k}$, where $p_1+2p_2+\ldots+kp_k=n$. Now collapse $x_1,\ldots,x_k$ to a single indeterminate to see that

$$\prod_{i=1}^k\frac1{1-x^i}=\prod_{i=1}^k\left(1+x^i+x^{2i}+x^{3i}+\ldots\right)\tag{1}$$

is the desired generating function for $p_{\le k}(n)$: the coefficient of $x^n$ is the number of integer combinations of $1,2,\ldots,k$ equal to $k$, which is the number of partitions of $n$ into parts of size at most $k$. (You might find this section of the Wikipedia article on partitions at least a little bit helpful.)

Note that if you multiply $(1)$ by $x^k$, you are in effect replacing the factor

$$\frac1{1-x^k}=\sum_{i\ge 0}x^{ki}$$

with the factor

$$\frac{x}{1-x^k}=\sum_{i\ge 1}x^{ki}\;,$$

thereby ensuring that you count exactly the partitions with at least one $k$-part. In other words, you get a generating function for $p_k(n)$.

Looking ahead to (d), think about you using Ferrers diagrams (equivalently, Young tableaux) to define your partial order. If you get stuck, the key term is Young’s lattice.