# Why do Bell Polynomial coefficients show up here?

The multinomial theorem allows us to expand expressions of the form $${\left( {{x_1} + {x_2} + {x_3} + {x_4} + ...} \right)^n}$$. I am interested in the coefficients when expanding $${\left( {\sum\limits_{k = 1}^\infty {{x_k}} } \right)^n}$$ in a particular way which I'll demonstrate below in the case where $$n = 5$$. In the following sums, the indices run through positive integers such that $${k_i} \ne {k_j}$$ for all $$i,j$$.

$${\left( {{x_1} + {x_2} + {x_3} + ...} \right)^5} = {a_1}\sum\limits_{k \geqslant 1} {x_k^5} + {a_2}\sum\limits_{\scriptstyle {k_1},{k_2} \geqslant 1 \atop \scriptstyle {k_1} \ne {k_2}} {x_{{k_1}}^4{x_{{k_2}}}} + {a_3}\sum\limits_{\scriptstyle {k_1},{k_2} \geqslant 1 \atop \scriptstyle {k_1} \ne {k_2}} {x_{{k_1}}^3x_{{k_2}}^2} + {a_4}\sum\limits_{\scriptstyle {k_i} \ne {k_j} \atop \scriptstyle {k_1},{k_2},{k_3} \geqslant 1} {x_{{k_1}}^3{x_{{k_2}}}{x_{{k_3}}}} + {a_5}\sum\limits_{\scriptstyle {k_i} \ne {k_j} \atop \scriptstyle {k_1},{k_2},{k_3} \geqslant 1} {x_{{k_1}}^2x_{{k_2}}^2{x_{{k_3}}}} + {a_6}\sum\limits_{\scriptstyle {k_i} \ne {k_j} \atop \scriptstyle {k_1},...,{k_4} \geqslant 1} {x_{{k_1}}^2{x_{{k_2}}}{x_{{k_3}}}{x_{{k_4}}}} + {a_7}\sum\limits_{\scriptstyle {k_i} \ne {k_j} \atop \scriptstyle {k_1},...,{k_4} \geqslant 1} {{x_{{k_1}}}{x_{{k_2}}}{x_{{k_3}}}{x_{{k_4}}}{x_{{k_5}}}}$$ When calculating the coefficients $${a_1},...,{a_7}$$, the multinomial coefficients are involved. However, since the summation goes through certain combinations of indices multiple times, a correction factor will need to be added to account for the duplicates produced by some of these sums. For example, in the 6th sum, the term $$x_{{k_1}}^2{x_{{k_2}}}{x_{{k_3}}}{x_{{k_4}}}$$ is the same under any permutation of $${k_1},{k_2},{k_3}$$, so $${a_6} = \frac{1}{{3!}}\left( \begin{array}{c}5\\2,1,1,1\end{array} \right) = 10$$. The rest of the coefficients can be found similarly:

$${a_1} = \left( \begin{array}{l}5\\5\end{array} \right) = 1,\quad {a_2} = \left( \begin{array}{c}5\\4,1\end{array} \right) = 5\quad {a_3} = \left( \begin{array}{c}5\\2,3\end{array} \right) = 10\quad {a_4} = \frac{1}{{2!}}\left( \begin{array}{c}5\\3,1,1\end{array} \right) = 10\quad {a_5} = \frac{1}{{2!}}\left( \begin{array}{c}5\\2,2\end{array} \right) = 15\quad {a_6} = \frac{1}{{3!}}\left( \begin{array}{c}5\\2,1,1,1\end{array} \right) = 10\quad {a_7} = \frac{1}{{5!}}\left( \begin{array}{c}5\\1,1,1,1\end{array} \right) = 1$$

The coefficients 1, 5, 10, 10, 15, 10, 1 are exactly the coefficients of the 5th complete Bell polynomial: $${B_n}\left( {{x_1},...,{x_5}} \right) = x_1^5 + 10x_1^3{x_2} + 10{x_3}x_1^2 + 15x_2^2{x_1} + 5{x_1}{x_4} + 10{x_2}{x_3} + {x_5}$$ For each $$n$$ I've tried, the $${a_1},{a_2},{a_3},...$$ end up being coefficients of the nth complete Bell polynomial.

I am interested in proving (if it is in fact true):

For all $$n$$, not just $$n=5$$, that these coefficients $${a_1},{a_2},,{a_3}...$$ are the same as the coefficients of the nth complete Bell polynomial.

I would appreciate if someone can provide me with a proof or additional information about this apparent relationship. I prefer a proof with generating functions but I will be happy with any proof.

My unsuccessful attempt:

I have tried proving this relation using generating functions but with no success. In particular, I wrote a partition based formula: $${\left( {{x_1}t + {x_2}{t^2} + {x_3}{t^3} + ...} \right)^n} = \sum\limits_{\scriptstyle{u_i} \ne {u_j}\atop\scriptstyle{P_{\ell,n} }:{k_1} + ... + {k_n} = n} {\left( {{a_{\ell,n} }\prod\limits_{r = 1}^n {x_{{u_r}}^{{k_r}}{t^{{k_r}{u_r}}}} } \right)}$$
where $${P_{\ell,n} }$$ is the $${\ell ^{{\rm{th}}}}$$ partition of $$n$$, so that the coefficients $${a_{\ell,n} }$$ are based on the chosen order of the partitions. The generating function for the incomplete Bell polynomials is $$\sum\limits_{n = 0}^\infty {\frac{1}{{n!}}{{\left( {\sum\limits_{j = 1}^\infty {{x_j}\frac{{{t^j}}}{{j!}}} } \right)}^n}} = \sum\limits_{n = 0}^\infty {\frac{{{t^n}}}{{n!}}\sum\limits_{k = 0}^n {{B_{n,k}}\left( {{x_1},...,{x_{n - k + 1}}} \right)} }$$

So I substituted the partition formula into the generating function:

$$\sum\limits_{n = 0}^\infty {\frac{{{t^n}}}{{n!}}\sum\limits_{k = 0}^n {{B_{n,k}}\left( {{x_1},...,{x_{n - k + 1}}} \right)} } = \sum\limits_{n = 0}^\infty {\frac{1}{{n!}}\sum\limits_{\scriptstyle{u_i} \ne {u_j}\atop\scriptstyle{P_{\ell,n} }:{k_1} + ... + {k_n} = n} {\left( {{a_{\ell,n} }\prod\limits_{r = 1}^n {\frac{{x_{{u_r}}^{{k_r}}}}{{{{\left( {{u_r}!} \right)}^{{k_r}}}}}{t^{{k_r}{u_r}}}} } \right)} }$$

I tried equating coefficients of $${t^m}$$ by having $${k_1}{u_1} + ... + {k_n}{u_n} = m$$ on the right-hand side to obtain

$$\sum\limits_{k = 0}^m {{B_{m,k}}\left( {{x_1},...,{x_{m - k + 1}}} \right)} = m!\sum\limits_{n = 0}^\infty {\frac{1}{{n!}}\sum\limits_{\scriptstyle{u_i} \ne {u_j}\atop{\scriptstyle{P_{\ell,n} }:{k_1} + ... + {k_n} = n\atop\scriptstyle{k_1}{u_1} + ... + {k_n}{u_n} = m}} {\left( {{a_{\ell,n} }\prod\limits_{r = 1}^n {\frac{{x_{{u_r}}^{{k_r}}}}{{{{\left( {{u_r}!} \right)}^{{k_r}}}}}} } \right)} }$$

Where the left-hand side is an equivalent expression for the mth complete Bell polynomial. However, I must have made a mistake - although the right-hand side gives indices which do indeed match the Bell polynomial, this equation does not give the correct values for the coefficients.

I think it is a coincidence that the coefficients of the bell polynomial are the same as the $$a_j$$'s above. The coefficients in Bell polynomial are the number of ways of partitioning $$n$$ object into blocks of given sizes. However, given those coefficients, there are infinite many ways to construct polynomials that have those coefficients.

For instance, the coefficient of $$x_1^3 x_2 x_3$$ in $$(x_1+...)^5$$ is 10, but it is however the coefficient of a different term $$x_3x_1^2$$ in Bell polynomial.

I think you just need to convince yourself that $$a_j$$'s are the number of ways to partition $$n$$ into given sizes.

For example, the term $$x_1^3 x_2 x_3$$ is obtained by multiplying three $$x_1$$'s, one $$x_2$$ and one $$x_3$$. (Note, both terms $$x_1^3 x_2 x_3$$ and $$x_1^3 x_3 x_2$$ exist in the expansion. To avaoid double count, we could enforce ordering on $$x_2$$ and $$x_3$$, say $$x_2$$ first, then $$x_3$$) .

$$(x_1+...)^5 = (x_1+...) \times (x_1+...) \times (x_1+...) \times (x_1+...) \times (x_1+...)$$. Imagine there are 5 boxes $$b_1,b_2,...,b_5$$ and we want to choose three $$x_1$$'s, one $$x_2$$ and one $$x_3$$ ($$x_2$$ and $$x_3$$ in order). The number of ways is exactly the number of ways to group $$b_1,b_2,...,b_5$$ into blocks of sizes (3,1,1)..

For example:

1. $$\{\{b_1,b_2,b_3\},\{b_4\},\{b_5\}\}$$ corresponds to $$x_1 \times x_1 \times x_1 \times x_2 \times x_3$$
2. $$\{\{b_1,b_2,b_4\},\{b_3\},\{b_5\}\}$$ corresponds to $$x_1 \times x_1 \times x_2 \times x_1 \times x_3$$

You could continue to list all the remaining 8 ways.

It shows that $$a_j$$'s are the number of ways to partitioning 5 into the given block sizes, thus they are the same coefficients with Bell polynomial.