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$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.