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](http://en.wikipedia.org/wiki/Partition_function_%28number_theory%29#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.



Faster formula to compute sum over partitions
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](https://mathoverflow.net/questions/127000/partitions-sum-of-divisors-identity) 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$.


