Simplified $\sum_{n=a_1k_1+a_2k_2+\cdots+a_mk_m}\frac{(a_1+a_1+\cdots+a_m)!}{a_1!\cdot a_2!\cdots a_m!}\prod_{i=1}^m \left(f(k_i)\right)^{a_i}$

Question

I'm studying a function of the form

$$b_n=\sum_{n=a_1k_1+a_2k_2+\cdots+a_mk_m}\frac{(a_1+a_2+\cdots+a_m)!}{a_1!\cdot a_2!\cdots a_m!}\prod_{i=1}^m \left(f(k_i)\right)^{a_i}$$

Where the sum is over all partitions of $n$. $a_1k_1+a_2k_2+\cdots+a_mk_m=n$ is one partition of $n$ with $m$ being the number of distinct elements in the partition. Let $k_i$ be the $i$th distinct element of a partition and $a_i$ be how many of that distinct element there is in that partition.

And I am wondering if there is a simplified form of this.

This is similar to the formulae in the Multinomial Theorem or Faa Di Bruno's Theorem or the General Leibniz Rule. Some differences are we are not taking derivatives of $f$ and the coefficient terms are not the usual multinomial coefficients (A036038) which are in terms of the partitions of $n$, but instead they are in terms of only the number of distinct parts in each partition of $n$ (A048996).

Answer 1

I doubt there's a direct formula for $b_n$ in terms of the values $f(k)$ which differs significantly from the one you gave, at least for general $f$. There is a relationship between the generating functions of $f(n)$ and $b_n$ which might be useful though (if you know something about the function $f$), so let $$F(x) = \sum_{n=1}^\infty f(n) x^n$$ and $$B(x) = \sum_{n=1}^\infty b_n x^n.$$

We can re-write the formula you gave as $$b_n = \sum_{l_1 + \cdots + l_r = n} \prod_{i=1}^r f(l_i)$$ where the sum is over all finite sequences of positive integers $(l_1, \dots, l_r)$ which sum to $n$ (and $r$ is not fixed). There are a few ways to proceed from here. Note that we can expand this as $$b_n = f(n) + \sum_{l_1=1}^{n-1} \left( f(l_1) \sum_{l_2 + \cdots + l_r = n-l_1} \prod_{i=2}^r f(l_i) \right) = f(n) + \sum_{l=1}^{n-1} f(l) b_{n-l}$$ which gives $B(x) = F(x) + F(x) B(x)$, hence $$B(x) = \frac{F(x)}{1 - F(x)}.$$

Answer 2

Wikipedia on Bell polynomials:

Likewise, the partial ordinary Bell polynomial, in contrast to the usual exponential Bell polynomial defined above, is given by $$\hat{B}_{n,k}(x_1,x_2,\ldots,x_{n-k+1})=\sum \frac{k!}{j_1! j_2! \cdots j_{n-k+1}!} x_1{}^{j_1} x_2{}^{j_2} \cdots x_{n-k+1}{}^{j_{n-k+1}},$$ where the sum runs over all sequences $j_1, j_2, j_3, \ldots, j_{n−k+1}$ of non-negative integers such that $$ j_1 + j_2 + \cdots + j_{n-k+1} = k, \\ j_1 + 2j_2 + \cdots + (n-k+1)j_{n-k+1} = n.$$

So your $b_n$ is $$b_n = \sum_{k=1}^n \hat{B}_{n,k}(f(1), f(2), \ldots, f(n-k+1))$$

Unfortunately these are ordinary Bell polynomials: the exponential ones seem to be much richer, or perhaps just more studied. But a name is a good starting place for research, so I offer it as an answer in the hope that it will be useful.