Number of partitions with x parts

integer-partitionsnumber theory

I might be wrong, but this is how I define "parts" when talking about partitions:

The partition 1+1+1 has 3 parts. The partition 1+2+2 has 3 parts. The numbers, whether they be distinct or not, do not matter: it is the number of digits that matter.

The partitions of 5 are as follows: 1+1+1+1+1 = 1+1+1+2 = 1+2+2 = 1+1+3 = 2+3 = 1+4 = 5

Of those 7 partitions, two of them consist of 3 parts (1+2+2 and 1+1+3). Two of them consist of 2 parts (2+3 and 1+4).

The number of parts is defined as the variable $x$, and the number being partitioned is defined as the variable $n$. I want an equation that gives the number of partitions with $x$ amount of parts, when $n$ is partitioned. The in-values are $x$ and $n$, and the out-value is the number of partitions with $x$ amount of parts.

Let's say that the no. of partitions consisting of $x$ parts is defined as the variable $y$.

Here's what I know:

There are three constants: If $x = 1, n, (n-1)$ then $y = 1$, regardless of the $n$-value.

To show this, look at the partitions of 5 again. Only one partition has an $x$-value of 1, and that is the partition 5. Only one partition has an $x$-value of $n$, and that is the partition of 1+1+1+1+1. Only one partition has an $x$-value of $n-1$, and that is the partition of 1+1+1+2.

I hope this was clearer. I have edited this question drastically, because I think I worded myself unclearly in the first edition.

EDIT: My question is this: Is there an equation for determining $y$, based off of $n$ and $x$?

Best Answer

It sounds like you are asking for the number $p_k(n)$ of partitions of a number $n$ into exactly $k$ parts. This is a standard type of restricted partition problem and can be solved as follows. Given such a partition, "rotate the Ferrers diagram," which shows that $p_k(n)$ also counts the number of partitions of a number $n$ whose largest part has size exactly $k$. Removing this part produces a partition of $n-k$ whose largest part has size at most $k$, and using this we can show that for fixed $k$ this sequence has a very nice generating function given by

$$P_k(x) = \sum_{n \ge 0} p_k(n) x^n = \frac{x^k}{\prod_{i=1}^k (1 - x^i)}$$

which in principle allows you to write down a closed form for $p_k(n)$ (again, for fixed $k$; it gets more complicated the larger $k$ is), although I won't do so. As a random example, setting $k = 5$ gives

$$\begin{align} \sum_{n \ge 0} p_5(n) x^n &= \frac{x^5}{(1 - x)(1 - x^2)(1 - x^3)(1 - x^4)(1 - x^5)} \\ &= x^5 + x^6 + 2x^7 + 3x^8 + 5x^9 + 7x^{10} + 10x^{11} + 13x^{12} + 18x^{13} + \dots \end{align}$$

which shows, for example, that the number of partitions $p_5(13)$ of $13$ into exactly $5$ parts is $18$. $p_5(n-5)$, which also counts the number $p_{\le 5}(n)$ of partitions of $n$ into at most $5$ parts, turns out to be A001401 on the OEIS.

Among other things, this generating function can be used to deduce the asymptotic growth rate of $p_k(n)$ (for fixed $k$, as $n \to \infty$), which turns out to be

$$p_k(n) \sim \frac{n^{k-1}}{(k-1)! k!}.$$

Edit: Okay, mea culpa - I said I'd write down the closed form you get from the generating function but for large $k$ I am really not sure how to do it even in a messy way. The basic strategy is to compute the partial fraction decomposition of the generating function $P_k(x)$ above. This gets very messy in general; here's what you get for small values of $k$.

For $k = 1$ there is a unique partition of $n$ with $1$ part, namely $n = n$. This corresponds to the generating function

$$P_1(x) = \frac{x}{1 - x} = x + x^2 + x^3 + \dots $$

which gives $\boxed{ p_1(n) = 1 }$ if $n \ge 1$ and $0$ if $n = 0$. Pretty straightforward.

For $k = 2$ the partial fraction decomposition is

$$P_2(x) = \frac{x^2}{(1 - x)(1 - x^2)} = \frac{1}{2(1 - x)^2} - \frac{3}{4(1 - x)} + \frac{1}{4(1 + x)}$$

(this can be done by hand) which gives the already-surprisingly-complicated

$$\boxed{ p_2(n) = \frac{n}{2} + \frac{(-1)^n - 1}{4} }.$$

This can be simplified, and proven, with a little casework as follows. The partitions into two parts are $n = i + j$ where, if $i \ge j$, we have $1 \le j \le \lfloor \frac{n}{2} \rfloor$. So we get $\boxed{ p_2(n) = \left\lfloor \frac{n}{2} \right\rfloor }$ which is equivalent to the above after squinting a bit.

For $k = 3$ the partial fraction decomposition is (according to WolframAlpha)

$$P_3(x) = \frac{-x^2 + 20x - 7}{72(1 - x)^3} - \frac{8}{1 + x} + \frac{x + 2}{9(1 + x + x^2)}$$

which gives, using that $\frac{x + 2}{1 + x + x^2} = \frac{2 - x - x^2}{1 - x^3}$ and $-x^2 + 20x - 7 = - (1 - x)^2 - 18(1 - x) + 12$, and after some simplification,

$$\boxed{ p_3(n) = \frac{6n^2 - 7}{72} - \frac{(-1)^n}{8} + \frac{\omega_3(n)}{9} }$$

where $\omega_3(n)$ is a periodic function with period $3$ that repeats $2, -1, -1, 2, -1, -1, \dots $. Already it's not entirely obvious that this is an integer, and I can't claim not to have made any computational errors, but the result has to look something like this even if I messed something up. It only gets worse from here - $p_k(n)$ has period-$d$ components for every $1 \le d \le k$. You can check out the partial fraction decomposition for $k = 4$ for yourself here.

So there's an important sense in which it's hopeless to expect a closed form for large $k$, although as above the leading-order asymptotic in $n$ for fixed $k$ is easy to calculate and the next few terms might not be so bad either. The good news is that for many purposes it doesn't matter; the generating function is powerful enough to answer many questions you might have about partitions with restricted parts.