computing length of integer partitions

Question

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

Answer 1

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)$.