A multinomial formula?

Question

We know this equality such as multinomial formula: $$\sum_{l_1 + \cdots +l_k =s} \frac{s!}{l_1!\cdots l_k!}. x_1^{l_1}\cdots x_k^{l_k} = (x_1 +\cdots+ x_k)^s$$

Can we deduce a similar formula or is it possible to simplify this sum?: $$\sum_{a_1l_1 + \cdots +a_kl_k =s} \frac{s!}{l_1!\cdots l_k! a_1^{l_1}..a_k^{l_k}}$$ where all the characters are integers (so they commute). The $a_i$ are fixed and given before.

I try to use the multinomial formula to do this but after lot of time, I have not complete. I don't know if it's possible to simplify this sum. What do you think about it?

Best wishes for 2018.

Answer 1

Just a start. Too long for a comment.

We assume the $a_i$ are fixed positive integers.

Letting $g(x)=\exp\left(\frac{x^{a_1}}{a_1}+\cdots+\frac{x^{a_k}}{a_k}\right)$ we see that this is the coefficient of $\frac{1}{s!}x^s$ in $g(x)$. Letting:

$$g_n(x)=\frac{g^{(n)}(x)}{g(x)}$$ we get:

$$g_0(x)=1, g_{n+1}(x)=g_n'(x)+g_n(x)(x^{a_1-1}+x^{a_2-1}+\cdots+x^{a_k-1})$$

Now your sum is $g_s(0)=g^{(s)}(0).$

When all the $a_i=1$, this give $g_{n+1}(x)=g_n'(x)+kg_n(x)$, or $g_n(x)=k^{n}$.

I'm not sure what more can be said here.

If $u+v=k$ and $a_1=\cdots =a_u=1, a_{u+1}=\cdots=a_k=2$ then you get that we are seeking the coefficient of $x^s/s!$ in $\exp\left(ux+vx^2/2\right).$ We can write this as:

$$\left(\sum \frac{1}{j!}u^jx^j\right)\left(\sum \frac{1}{i!}\left(\frac{v}{2}\right)^ix^{2i}\right)$$

So you get: $$\sum_{i=0}^{\lfloor s/2\rfloor} \frac{s!}{i!(s-2i)!2^i}(k-v)^{s-2i}v^i$$

If $c_i$ is the number of $j$ such that $a_j=i$, then the above can be written as:

Let $p(x)=\sum c_ix^{i-1}$, and $$g_0(x)=1, g_{n+1}(x)=g_n'(x)+g_n(x)p(x).$$ and the value you are seeing is $g_s(0).$

This works even for infinitely many values $a_j$, as long as each $c_i<\infty,$ or, equivalently, as long as $a_j\to \infty.$

The value can be written:

$$\sum_{i_1+2i_2+3i_3+\cdots = s} \frac{s!c_1^{i_1}c_2^{i_2}\dots}{i_1!1^{i_1}i_2!2^{i_2}\cdots}$$

This doesn't simplify the problem unless a lot of the $a_i$ are equal. If all the $a_i$ are distinct, then the $c_i$ are all $0$ or $1$, and $i_{a_j}$ functions as $l_i$ in the original formula.

(For the purposes here, $0^0=1$. so if $c_1=0$ then $c_1^{i_1}=0$ unless $i_1=0$.)

If $c_i=i$ for all $i$, then a big part cancels, and you get:

$$s!\sum_{i_1+2i_2+\cdots =s} \frac{1}{i_1!i_2!\cdots}$$

This is the coefficient of $x^s$ in $\exp\left(\frac{1}{1-x}\right)$.

Answer 2

The coefficients in your first equation (multinomial theorem) are the multinomial coefficients (of the first kind). They count integer combinations.

For $a_i=i$, your considered formula is the sum of the multinomial coefficients of the second kind (Stirling numbers of the first kind ($s$) [Abramowitz/Stegun 1970]). They count integer permutations.

$$\sum_{1l_1+...+kl_k=s}\frac{s!}{1^{l_1}l_1!...k^{l_k}l_k!}=\sum_{r=1}^s\left[^s_r\right]=s!$$

The generating function for the coefficients is:

$$\sum_{s=m}^\infty\left(\sum_{1l_1+...+kl_k=s}\frac{s!}{1^{l_1}l_1!...k^{l_k}l_k!}x_1^{l_1}...x_k^{l_k}\right)\frac{t^s}{s!}=\frac{1}{m!}\left(\sum_{i=1}^\infty\frac{1}{i}x_it^i\right)^m.$$

For $a_i=i!$, your considered formula is the sum of the multinomial coefficients of the third kind (Stirling numbers of the second kind [Abramowitz/Stegun 1970]), the Bell number $B_s$. They count set partitions.

$$\sum_{1l_1+...+kl_k=s}\frac{s!}{1!^{l_1}l_1!...k!^{l_k}l_k!}=\sum_{r=1}^s\left\{^s_r\right\}=B_s$$

The generating function for the coefficients is:

$$\sum_{s=m}^\infty\left(\sum_{1l_1+...+kl_k=s}\frac{s!}{1!^{l_1}l_1!...k!^{l_k}l_k!}x_1^{l_1}...x_k^{l_k}\right)\frac{t^s}{s!}=\frac{1}{m!}\left(\sum_{i=1}^\infty\frac{1}{i!}x_it^i\right)^m.$$

[Abramowitz/Stegun 1970] Abramowitz, M.; Stegun, I.: Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. National Bureau of Standard 1970. p. 823