Why do Bell Polynomial coefficients show up here?

Question

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.

Answer 1

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.