The partition function $p(n)$ measures the number of partitions of $n$, or the number of ways in which natural numbers can be summed to produce $n$, without regard to order. For example, the partitions of $4$ are $$\begin{array}{} 4 \\ 3+1 \\ 2+2 \\ 2+1+1 \\ 1+1+1+1,\end{array}$$ so $p(4)=5$.

We can restrict the partitions by number of elements or, equivalently, by largest element: we write $p_k(n)$ to denote the number of partitions of $n$ into $k$ or fewer elements, or equivalently, with no element larger than $k$. Thus, $p_3(4)=4$.

If we consider a similar function $P_k(n)$, which we define to be the ordered partition function bounded by $k$, or the number of partitions of $n$ into exactly $k$ elements of $\mathbb N_0$ counting, for instance, $2+1+1$ as separate from $1+2+1$, then what is the correlation between $P_k(n)$ and $p_k(n)$ (or $p(n)$)?

The ordered partitions of $4$ bounded by $3$, as so defined, are $$\begin{aligned}[c] 4+0+0 \\ 0+4+0 \\ 0+0+4 \\ 3+1+0 \\ 3+0+1 \end{aligned} \qquad\qquad \begin{aligned}[c] 1+3+0 \\ 1+0+3 \\ 0+3+1 \\ 0+1+3 \\ 2+2+0 \end{aligned} \qquad \qquad \begin{aligned}[c] 2+0+2 \\ 0+2+2 \\ 2+1+1 \\ 1+2+1 \\ 1+1+2, \end{aligned}$$ so $P_3(4)=15$.

We can find a formula for $P_k(n)$ fairly easily: $$\sum_{m=0}^\infty P_k(m)x^m=\prod_{j=1}^k \sum_{m=0}^\infty x^m=\frac 1{(1-x)^k}=\sum_{m=0}^\infty \binom {m+k-1}{k-1}x^m,$$ so $$P_k(n)=\binom{n+k-1}{k-1}.$$ Does such a link between $p_k(n)$ and $P_k(n)$ exist?


Your Answer

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

Browse other questions tagged or ask your own question.