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.
 A: 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$.
A: 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.
$$
