1
$\begingroup$

This is a two-part question. (no pun intended)

Part 1

I need to compute the length of each possible partition of an integer $n$. One possible way is to first compute all the partitions and the just count. For instance 4 can be partitioned into {4}, {3,1}, {2,2}, {2,1,1} and {1,1,1,1}, hence the lengths that I need are 1,2,2,3,4.

This method works, but once $n$ is large enough, this task becomes very computational intensive (producing all the partitions of $n$ scales like $O(nP(n))$, where $P(n)$ is the number of possible partitions). It seems plausible that as I don't need all the information contained in the set of all partitions, that there could be a way of achieving the same result without having to produce all the partitions as the first step. Any ideas?

Part 2

This is more tricky. I need to compute the product of the factorial of the multiplicities of the numbers in each partition of an integer $n$. This is more easily done that said: in the same example as in Part 1, the multiplicities of the numbers in each partition are {1}, {1,1}, {2}, {1,2}, {4}, hence I need the numbers 1!, 1!1!, 2!, 1!2!, 4!

Again, starting by computing all the partitions works, because then I would compute the multiplicities, then take the factorials and finally the product. However this method requires calculating the whole set of partitions. I assume the answer here is more likely to be "no" than for Part 1, but is there a way of achieving the same result without having to produce all the partitions as the first step?

EDIT: I made a bubu at explaining part 2, now it's fixed.

EDIT 2: I think that one could make Part 2 easier by re-interpreting the terms in the product of factorials of multiplicities: let's say that we have a partition of the number 31: {1,1,1,1,2,2,3,3,3,4,5,5}. The multiplicities are {4,2,3,1,2}. Then $4!2!3!1!2!=2^43^24^1$, i.e. if we define $m(n,k)$ to be the number of multiplicities of value at least $k$, we can re-write the number we are after by $2^{m(n,2)}3^{m(n,3)}4^{m(n,4)}\cdots n^{m(n,n)}$

$\endgroup$
1
$\begingroup$

I will deal with part 1, which you can solve with a recurrence.

Let $T(n,k)$ be the number of partitions of $n$ into $k$ parts; it is also the number of partitions of $n$ where the largest part is $k$. Then you have $T(0,0)=1$ while for $n \gt 0$ you obviously have $T(n, 1) = T(n, n) = 1$ and for $k \gt n$ you have $T(n, k) = 0$. The main calculation is that for $1 \lt k\lt n$: $$T(n, k) = T(n-1, k-1) + T(n-k, k).$$ For example $T(4,2)=T(3,1)+T(2,2)=1+1=2$ as you have found.

So you can solve part 1 with time and memory $O(n^2)$.

$\endgroup$
  • $\begingroup$ Awesome! So for instance this allows me to say: "the list that I need contains $T(4,1)$ ones, $T(4,2)$ twos, $T(4,3)$ threes and $T(4,4)$ fours", am I correct? $\endgroup$ – Ziofil Sep 18 '14 at 21:19
  • 1
    $\begingroup$ Perhaps less ambiguously "the list of partitions of $4$ has $T(4,1)$ partitions with one part, $T(4,2)$ with two parts, $T(4,3)$ with three parts and $T(4,4)$ with four parts" $\endgroup$ – Henry Sep 18 '14 at 21:29
  • $\begingroup$ Yes, that is what I meant, thanks! By the way, I have re-written Part 2 in a (perhaps) more workable way in terms of $m(n,k)$, which I defined as the number of multiplicities of value at least $k$. Is this a thing? Does it satisfy a beautiful recurrence relation like the one you wrote for $T$? $\endgroup$ – Ziofil Sep 18 '14 at 21:37
  • $\begingroup$ For part 2 I would follow @ Barry Cipra's link and the links from there $\endgroup$ – Henry Sep 18 '14 at 22:10

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.