How do you find the number of unique parts in a partition of an integer $n$ into $k$ parts? Suppose I have an integer $n$ and I partition it into $k$ parts. The number of ways this can be done is given by $P(n,k)$, and it satisfies the recurrence relation:
$P(n,k) = P(n-1,k-1) + P(n-k,k)$
Now, I'm interested in finding the number of unique parts for a partition of integers into $k$ parts. Suppose $E(n,k)$ denotes this number. For example, when $n=6$ and $k=4$, the unique partitions are:
$3+1+1+1$
$2+2+1+1$
and so $P(6,4)=2$. Each partition has two unique parts, ($\{3,1\}$ for the first, $\{2,1\}$ for the second) giving us $E(6,4)=2+2=4$. I'm looking for a formula or recurrence relation for this quantity, or at least a tight upper bound for it. How do I go about in solving this problem? Thank you.
 A: Consider the generating function $f(x,y,z)=\sum_{nkl}f_{nkl}x^ny^kz^l$, where $f_{nkl}$ is the number of partitions of $n$ into $k$ parts of which $l$ are distinct. This is
\begin{eqnarray}
f(x,y,z)
&=&
\prod_{j=1}^\infty\left(1+z\left(yx^j+\left(yx^j\right)^2+\cdots\right)\right)
\\
&=&
\prod_{j=1}^\infty\left(1+z\left(\frac1{1-yx^j}-1\right)\right)\;.
\end{eqnarray}
Then
\begin{eqnarray}
E(n,k)
&=&
\sum_llf_{nkl}
\\
&=&
\left[x^ny^k\right]\left.\frac\partial{\partial z}f(x,y,z)\right|_{z=1}
\\
&=&
\left[x^ny^k\right]\sum_{m=1}^\infty yx^m\prod_{j=1}^\infty\frac1{1-yx^j}
\\
&=&
\left[x^ny^{k-1}\right]\sum_{m=1}^\infty x^m\prod_{j=1}^\infty\frac1{1-yx^j}
\\
&=&
\left[x^ny^{k-1}\right]\sum_{m=1}^\infty x^m\sum_{r,s}P(r,s)x^ry^s
\\
&=&
\left[x^n\right]\sum_{m=1}^\infty x^m\sum_{r=0}^\infty P(r,k-1)x^r
\\
&=&
\sum_{r=k-1}^{n-1}P(r,k-1)\;.
\end{eqnarray}
This implies the recurrence relation
$$
E(n,k)=E(n-1,k)+P(n-1,k-1)\;.
$$
This is OEIS sequence A092905, and that entry provides the recurrence relation
$$
E(n,k)=\sum_{j=0}^kE(n-k,j)\;.
$$
Note that this implies that $E(k+m,k)$ is independent of $k$ for $k\ge m$, so if you arrange the values of $E(n,k)$ in a triangular array, each diagonal $E(k+m,k)$ is eventually constant.
A: One possible (quadratic) recurrence relation is given as follows: let $E(n,m) = 0$ if $m > n$, $E(n,m) = 1$ if $n=m$ and $n \neq 0 \neq m$, and let the following hold otherwise:
$$
E(n,m) = \sum_{k=1}^{m-1}[E(n-m,k)+P(n-m,k)]+E(n-m,m)
$$
for $n \geq m$.
Given $n$ and $m$, we can place $m$ ones in a row:
$$
\underset{\text{$m$ times}}{\underbrace{1, 1, \dots 1}}
$$
For each $k \in \{1, \dots m\}$, we can allocate the remaining $n-m$ units yielding $E(n-m,k)$ unique elements. Also, for all $k < m$, there are some $1$'s left over contributing to the number of unique elements. The number of such $1$'s is $P(n-m,k)$, accounting for the second factor in the summation.
