1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.