# Number of partitions of an integer with a fixed number of parts

Is there an easy way in Mathematica to find the number of partitions of $$n$$ into $$k$$ parts? Or equivalently, the number of partitions of $$n$$ with largest part equal to $$k$$?

I realize the function IntegerPartitions[n,{k}] will return a list of all such partitions, which I could count, but I am wondering if there is a more efficient method.

• There are functions PartitionsP and PartitionsQ that do this, but without the $k$ restriction so this only gives an upper bound. Oct 18 '20 at 14:47
• I do not follow that "or equivalently..." part. Oct 18 '20 at 14:55
• Anyway, it seems like it should just be Binomial[n+k,k] unless I am missing something big (like, UFO-size big). Oct 18 '20 at 14:58
• @DanielLichtblau This gives far too many for n=12,k=7 for example whereas IntegerPartitions[12, {7}] // Length is just 7 due to sorting and de-duplication. I don't think there's an easier way to get the number other than just generating them and taking the length. The only slightly more efficient thing to do would be re-implement an IntegerPartitions-like function and save on memory by not storing the partitions and counting as you go. Oct 18 '20 at 15:33
• @DanielLichtblau The number of partitions of $n$ into $k$ parts is the same as the number of partitions of $n$ into parts where the largest part is $k$. This follow easily from examining the Ferrers diagram of the partition. See en.wikipedia.org/wiki/…. Oct 18 '20 at 17:14

As mentioned in the comments, the wiki page gives a generating function solution for the partition of $$n$$ into exactly $$k$$ parts. For example, partitions of $$n$$ into $$k=5$$ parts correspond to the coefficients of $$z^n$$ in the following polynomial.

With[{k = 5}, Series[z^k Product[1/(1 - z^i), {i, 1, k}], {z, 0, 20}]]

z^5 + z^6 + 2 z^7 + 3 z^8 + 5 z^9 + 7 z^10 + 10 z^11 + 13 z^12 + 18 z^13 + 23 z^14 + 30 z^15 + 37 z^16 + 47 z^17 + 57 z^18 + 70 z^19 + 84 z^20

Define

partition[n_, k_] :=
Block[{z},
Coefficient[Series[z^k Product[1/(1 - z^i), {i, 1, k}], {z, 0, n}], z, n]]

A method which is about 20 times faster is the following partition2[n,k].

partition2[n_, k_] :=
Block[{c, t},
c = ConstantArray[1, n + 1];
t = c;
Do[
Do[t[[Range[i + 1, n + 1]]] += c[[Range[n + 1 - i]]], {i, j, n, j}];
c = t,
{j, 2, k}];
c[[-k - 1]]
]

Timings...

With[{n = 60},
{AbsoluteTiming[Sum[Length[IntegerPartitions[n, {k}]], {k, 1, n}]],
AbsoluteTiming[Sum[partition[n, k], {k, 1, n}]],
AbsoluteTiming[Sum[partition2[n, k], {k, 1, n}]]}
]

{{0.287107, 966467}, {0.945235, 966467}, {0.054166, 966467}}