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

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

• Is $m$ fixed in the sum? If so, is the sequence $\{k_i\}$ also fixed? I can't quite tell from your question. – Carl Schildkraut Jul 8 '18 at 2:07
• $m$ is the number of distinct parts of each partition, so over the sum, no $m$ and the sequence $\{k_i\}$ is not fixed over the sum. – tyobrien Jul 8 '18 at 2:09
• It's also similar to the cycle index of the full symmetric group. If $f(k_i)$ is taken as equivalent to the cycle index's bound variable $z_i$ then the difference is a factor of $$\frac{(a_1 + a_2 + \cdots + a_m)!}{k_1{}^{a_1} k_2{}^{a_2} \cdots k_m{}^{a_m}}$$ in the weighting of each term. – Peter Taylor Jul 9 '18 at 11:30
• And on further thought, the denominator there is easily accounted for by identifying $z_i$ with $k_i f(k_i)$. – Peter Taylor Jul 9 '18 at 21:53
• @CarlSchildkraut, $m$ can be taken to be fixed and equal to $n$, and that then allows $k_i$ to be taken to be equal to $i$. It doesn't fundamentally change anything. It's important that the $k_i$ are distinct, but it's not important that the $a_i$ are non-zero. – Peter Taylor Jul 9 '18 at 22:02

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

• At your "We can rewrite your formula as" equation: are you saying that's the same as my equation? My expression specifies some coefficients in it that are like multinomial coefficients but using number of distinct parts. Your equation doesn't account for those coefficients. – tyobrien Jul 8 '18 at 4:05
• I've edited for clarity to use $l$'s instead of $k$'s -- consider the number of times a product $\prod_{i=1}^m f(k_i)^{a_i}$ appears in my sum, for fixed values of $a_1, \dots, a_m$ and $k_1, \dots, k_m$: this is just the number of ways of writing a sequence $(l_1, \dots, l_r)$ using $a_1$ of $k_1$, $a_2$ of $k_2$, $\dots$, $a_m$ of $k_m$. But the number of such sequences is $\frac{(a_1 + a_2 + \cdots + a_m)!}{a_1! \cdot a_2! \cdots a_m!}$, so the sums are the same. The only difference is in how we index the sums. – user125932 Jul 8 '18 at 4:17
• Oh I think I finally see what you're saying. So is your sum over all compositions (ordered partitions) of $n$? – tyobrien Jul 8 '18 at 20:38
• Yes, the sum is over ordered partitions -- sorry if you were just looking for a slightly simpler expression like that – user125932 Jul 9 '18 at 0:33

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.

• One thing that I find confusing about this definition is that after picking $n$ and $k$, it looks like it’s saying that the size of each sequence $j_1, j_2,\dots$ such that they add to $k$ and $j_1, 2j_2,\dots$ such that they add to $n$ is always $n-k+1$. I must be missing something because I find that hard to believe. – tyobrien Jul 14 '18 at 13:46
• What you're missing is that some of the $j_i$ are zero. – Peter Taylor Jul 14 '18 at 14:15
• Oh duh. Appreciate it. – tyobrien Jul 14 '18 at 14:26