Multinomial Expansion

Question

Given $x_0 \ldots x_k$ and $n$, Define $$f(Q)=\sum_{\substack{n_0+\ldots+n_k=n \\ n_0,\ldots,n_k \ >=0 \\n_1+2*n_2+\ldots+k*n_k=Q}} \binom{n}{n_0,\cdots,n_k}x_{0}^{n_0}\ldots x_{k}^{n_k}$$. Note that $$\sum_{Q=0}^{n*k} f(Q)=(\sum_{i=0}^{k}x_i)^n$$ which comes from the multinomial expansion. I was wondering how to calculate $\sum_{Q=0}^{n*k} Q\cdot f(Q)$.

I've checked several small cases, and it seems that $\sum_{Q=0}^{n*k} Q\cdot f(Q) = n(\sum_{i=0}^{k}x_i)^{n-1}(\sum_{i=0}^{k}ix_i)$, but I'm not sure how to prove that.

Answer 1

You can calculate the generating function instead. Define $$ \begin{aligned} F(X,Y)&= \sum_{n=0}^\infty X^n\sum_{Q=0}^\infty Y^Q \sum_{\substack{n_0+\ldots+n_k=n \\ n_0,\ldots,n_k \ >=0 \\n_1+2*n_2+\ldots+k*n_k=Q}} \frac{1}{n_0!n_1!\cdots n_k!}x_{0}^{n_0}\ldots x_{k}^{n_k}\\ &=\sum_{n=0}^\infty X^n\sum_{Q=0}^\infty Y^Q \sum_{n_0, \cdots, n_k\geq 0} \frac{1}{n_0!n_1!\cdots n_k!}x_{0}^{n_0}\ldots x_{k}^{n_k} \delta\left(n-\sum_{j=0}^k n_j\right) \delta\left(Q-\sum_{j=0}^k jn_j\right)\\ &= \sum_{n_0, \cdots, n_k\geq 0} \frac{1}{n_0!n_1!\cdots n_k!}x_{0}^{n_0}\ldots x_{k}^{n_k} X^{\sum_j n_j} Y^{\sum_j jn_j}\\ &=\prod_{m=0}^k \exp(x_m XY^m) \end{aligned} $$ where by $\delta(Z)$ I mean the Kronecker delta equating $Z=0$. What you are looking for the $n!$ times the coefficient of $X^nY^Q$ in the expansion of $F(X,Y)$ (in other words, $(Q!)^{-1}\partial_X^n \partial_Y^Q F\mid_{X=Y=0}$).

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 sum $$\sum_{\substack{n_0+\ldots+n_k=n \\ n_0,\ldots,n_k \ >=0 \\n_1+2n_2+\ldots+kn_k=Q}} \binom{n}{n_0,\cdots,n_k}x_{0}^{n_0}\ldots x_{k}^{n_k}$$ is $$\sum_{n_0=0}^n \binom{n}{n_0} x_{0}^{n_0} \hat{B}_{Q,n-n_0}(x_1, x_2, \ldots, x_k)$$

---

Using $${\hat {B}}_{n,k}(x_{1},x_{2},\ldots ,x_{n-k+1})={\frac {k!}{n!}}B_{n,k}(1!\cdot x_{1},2!\cdot x_{2},\ldots ,(n-k+1)!\cdot x_{n-k+1})$$ we have

$$\frac{n!}{Q!}\sum_{n_0=0}^n \frac{x_{0}^{n_0}}{n_0!} B_{Q,n-n_0}(1!\cdot x_1, 2!\cdot x_2, \ldots, k!\cdot x_k)$$

Then the recurrence relation $$B_{n,k}=\sum_{i=1}^{n-k+1} \binom{n-1}{i-1} x_i B_{n-i,k-1}$$

gives you an evaluation strategy.

Answer 3

Starting from Hamed's answer, we can give a quick proof that $\sum_{Q\ge 0} Qf(Q)$ equals what you think it is. They proved $$ \sum_{n\ge 0}\sum_{q\ge 0}\frac1{n!}f_n(Q)X^nY^q = \exp\Big(\sum_{m=0}^k x_mXY^m\Big) $$ Differentiating both sides with respect to $Y$, and then multiplying by $Y$, you get $$ \sum_{n\ge 0}\sum_{q\ge 0}\frac1{n!}Qf_n(Q)X^nY^q = \big(\sum_{k=0}^m mx_m XY^m\big)\exp\Big(\sum_{m=0}^k x_mXY^m\Big) $$ Notice that we now have a $Qf_n(Q)$. These need to be summed, so set $Y=1$: $$ \sum_{n\ge 0}\sum_{q\ge 0}\frac1{n!}Qf_n(Q)X^n = \big(\sum_{k=0}^m mx_m X\big)\exp\Big(X\sum_{m=0}^k x_m\Big) $$ Finally, extract the coefficient of $X^n$ of both sides. On the left hand side, $X_n$ has a $\frac1{n!}\sum_{q\ge 0}QF_n(Q)$ attached to it. On the right, you get the $X^n$ coefficient by multiplying $\big(\sum_{k=0}^m mx_m\big)$ with the $X^{n-1}$ coefficient of $\exp\Big(X\sum_{m=0}^k x_m\Big)$. This implies $$ \frac1{n!}\sum_{q\ge 0}QF_n(Q)=\big(\sum_{k=0}^m mx_m\big)\cdot \frac1{(n-1)!}\Big(\sum_{k=0}^m x_m\Big)^{n-1} $$ which is what you wanted.

Answer 4

I'm going to provide a secondary generating function which is probably more relevant to your updated question. Let's recall your definition, $$ f(Q):=\sum_{\substack{\sum_{i=0}^k n_i=n \\ n_0,\ldots,n_k \ \geq0 \\\sum_{j=0}^kjn_j=Q}} \binom{n}{n_0,\cdots,n_k}x_{0}^{n_0}\ldots x_{k}^{n_k} $$ and let us calculate $ G(X):=\sum_{Q=0}^{nk} f(Q)X^Q $. Before, we do that note that for any $p\geq 0$, $$\boxed{\sum_{Q=0}^{nk} Q^pf(Q)=\left.\left(X\frac{d}{dX}\right)^p G(X)\right|_{X=1}}$$

First of all, note that under the condition $\sum_{j=0}^k n_j = n$ and $n_0, \cdots, n_k\geq 0$, one has $$ nk -\sum_{j=0}^k jn_j= \sum_{j=0}^k (k-j) n_j\geq 0 $$ As a result, the equation $z-\sum_{j=0}^k jn_j=0$ has exactly one solution for $z$ in the integer range $0\leq z\leq nk$. Using this, we have $$ \begin{aligned} G(X)&=\sum_{Q=0}^{nk} X^{Q} \sum_{\substack{\sum_{i=0}^k n_i=n \\ n_0,\ldots,n_k \ \geq 0}} \binom{n}{n_0,\cdots,n_k}x_{0}^{n_0}\ldots x_{k}^{n_k} \delta\left(Q-\sum_{j=0}^kjn_j\right) \\ &= \sum_{\substack{\sum_{i=0}^k n_i=n \\ n_0,\ldots,n_k \ \geq 0}} \binom{n}{n_0,\cdots,n_k}\prod_{m=0}^k (x_mX^m)^{n_m}=\left(\sum_{m=0}^k x_m X^m\right)^{n} \end{aligned} $$ So to summarize: $$ \boxed{ G(X)=\sum_{Q=0}^{nk} f(Q) X^Q = \left(\sum_{m=0}^k x_m X^m\right)^{n} } $$ This should make the rest obvious.