Unordered multinomial coefficients

630 Views Asked by At

Let $\{n_1,\ldots,n_k\}$ be a partition of the integer $m$, that is $m=n_1+\ldots+n_k$, and denote by $\mathcal{P}_m$ the set of all such partitions.

For a partition $\pi\in\mathcal{P}_m$, the unordered multinomial coefficient $c_\pi$ is defined as $$ c_\pi = \frac{m!}{r_1!\, 1^{r_1}\cdot r_2!\, 2^{r_2}\cdot\ldots\cdot r_m!\, m^{r_m}}, $$ where $r_i=\#\{\kappa:n_\kappa=i\}$ is the number of $i$'s in the partition $\pi$.

Given real numbers $x_1,\ldots,x_m$, is there a closed form expression (or interpretation) for the sum $$ \sum_{\pi\in\mathcal{P}_m}{c_\pi\; x_1^{r_1}}\cdot\ldots\cdot x_m^{r_m} $$ similar to the formula $$ \sum_{r_1+\ldots+r_n=m}{\frac{m!}{r_1!\cdot\ldots\cdot r_n!}x_1^{r_1}\cdot\ldots\cdot x_n^{r_n}}=\left(x_1+\ldots+x_n\right)^m. $$

1

There are 1 best solutions below

0
On BEST ANSWER

Here's the best that I came up with: $$ \sum_{\pi\in\mathcal{P}_m}c_{\pi}x_1^{r_1}\cdots x_m^{r_m}=m!\,[y^m]\,\exp\left[\sum_{k=1}^{m}\frac{x_k}{k}y^k\right]. $$ Where did this come from? Rewrite the summation as $$ m!\sum_{r_1+2r_2+\cdots+mr_m=m}\prod_{k=1}^{m}\frac{x_k^{r_k}}{r_k!\cdot k^{r_k}}. $$ This is precisely the coefficient by $y^m$ in $$ m!\prod_{k=1}^{m}\left(\sum_{r=0}^{\infty}\frac{x_k^r}{r!\,k^r}y^{kr}\right)=m!\prod_{k=1}^{m}\left(\sum_{r=0}^{\infty}\frac{\left(\frac{x_k y^k}{k}\right)^r}{r!}\right)=m!\prod_{k=1}^{m}\exp\left[\frac{x_k y^k}{k}\right]. $$