# Faster formula to compute sum over partitions

Let $f$ be a function from the positive integers to the real numbers (or some ring...). Let $$(\star) \quad F(n) = \sum_{n_1 \leq \cdots \leq n_j\atop n_1 + \cdots + n_j = n} f(n_1) \cdots f(n_j),$$ for each positive integer $n$, where the sum runs over all the partitions of $n$, i.e., $n_1 \leq \cdots \leq n_j$ and $n_1 + \cdots + n_j = n$.

Computing $F(n)$ directly from $(\star)$ is computationally expensive since it require to sum $p(n) \sim e^{\pi\sqrt{2n/3}} / (4n\sqrt{3})$ addends, as $n \to \infty$, where $p(n)$ is the partition function.

My question is: Assume that we have computed $F(1), \dots, F(n-1)$, there is some (recursive) formula to find $F(n)$ in a way faster than $(\star)$?

I think the answer is affermative and that $F(n)$ can be expressed as a sum involving $F(k)$, $k < n$ and $f(h)$, $h \leq n$ with fewer addends than $(\star)$, but I am unable to figure out it. Thank you in advance for any suggestion.

• The gf seems to be $\prod_{j\ge 1} (1 - f(j) x^j)^{-1}$. Aug 17, 2014 at 13:19
• @MarkWildon Yes, thanks, that was wrong Aug 17, 2014 at 18:33

## 2 Answers

The identity $np(n) = \sum_{m=1}^n p(n-m)\sigma(m)$, where $\sigma(m)$ is the sum of divisors of $n$ generalizes to this setting. The proof I sketched here shows that

$$nF(n) = \sum_{r=1}^n F(n-r) g(r)$$

where

$$g(r) = \sum_{m \mid r} f(m)^{r/m} m.$$

This should give a more efficient algorithm: first compute the values of $g(r)$ for $r \le N$. Then use the first formula to compute $F(n)$ iteratively for $n \le N$.

• Thank you very much, this is exactly what I was looking for. This result is folklore or there are some references? To completeness: $F(0) := 1$.
– user40023
Aug 17, 2014 at 14:20
• (Update of my earlier comments.) Erdös' paper is 'On an elementary proof of some asymptotic formulas in the theory of partitions', Ann. of Math. (2) 43 (1942), 437–450. My generalization may also be proved using the generating function in Brendan McKay's comment. The special case when $f$ is the indicator function of a union of residue classes modulo some integer is Lemma 8 in arxiv.org/pdf/math/0002171v1.pdf. This paper uses Erdös' method to get asymptotic estimates for the corresponding classes of restricted partitions. Aug 18, 2014 at 8:47

The values of $F$ alone will not suffice for recursion: if $f(0)=\dots=f(n-1)=0$ and $f(n)=1$, then $F(0)=\dots=F(n-1)=0$ and $F(n)=1$. Therefore the recursion formula will contain $f$ as well, at least $f(n)$. (Actually, $f(n)$ will be enough, since you can recover $f(1),\dots,f(n-1)$ from $F(1),\dots,F(n-1)$, though probably not computationally efficiently.)

Let me try to get a recursive expression.

• Many partitions of $n$ include 1, and the partial sum over these is $f(1)F(n-1)$.
• The sum over partitions of $n-2$ that do not contain 1 is $F(n-2)-f(1)F(n-3)$, whence the sum over the partitions of $n$ starting at 2 is $f(2)(F(n-2)-f(1)F(n-3))$.
• The sum over partitions of $n-3$ that do not contain 1 or 2 is $F(n-3)-f(1)F(n-4)-f(2)(F(n-5)-f(1)F(n-6))$, whence the sum over the partitions of $n$ starting at 3 is $f(3)[F(n-3)-f(1)F(n-4)-f(2)(F(n-5)-f(1)F(n-6))]$.

Summing what we have, it seems that $$F(n) = \sum_{k=1}^nF(n-k)[f(k)-\Phi(k)],$$ where $F(0)=1$ and $$\Phi(n) = \sum_{0<n_1<\dots<n_j<n\atop n_1+\dots+n_j=n}f(n_1)\cdots f(n_j).$$ This might make the calculation a little faster.

You can also start at the other end (looking at highest instead of lowest number of the partition): $F(n)=f(n)+f(n-1)F(1)+f(n-2)F(2)+\dots$, but this nice pattern will break down at about $F(n/2)f(n/2)$. I have not been able to write down a manageable expression for this. To illustrate the idea: $$F(6) =f(6) +f(5)f(1) +f(4)F(2) +f(3)F(3) +f(2)f(2)F(2) +f(2)f(1)^4 +f(1)^6.$$