2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ There are functions PartitionsP and PartitionsQ that do this, but without the $k$ restriction so this only gives an upper bound. $\endgroup$
    – flinty
    Oct 18 '20 at 14:47
  • $\begingroup$ I do not follow that "or equivalently..." part. $\endgroup$ Oct 18 '20 at 14:55
  • $\begingroup$ Anyway, it seems like it should just be Binomial[n+k,k] unless I am missing something big (like, UFO-size big). $\endgroup$ Oct 18 '20 at 14:58
  • $\begingroup$ @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. $\endgroup$
    – flinty
    Oct 18 '20 at 15:33
  • 2
    $\begingroup$ @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/…. $\endgroup$
    – awkward
    Oct 18 '20 at 17:14
1
$\begingroup$

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}}

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .