A multinomial theorem for polynomials of one variable

Question

Theorem (Multinomial Theorem): For any positive integer $m$ and any non-negative integer $n$, the following formula holds: $$ \left(\sum_{i=1}^m x_n\right)^n = \sum_{\begin{gathered} k_1+k_2+\dots+k_m=n; \\ k_1,k_2,\dots,k_m\geqslant 0\end{gathered}}\binom{n}{k_1,k_2,\dots,k_m}\prod_{t=1}^mx_t^{k_t} $$ where $\binom{n}{k_1,k_2,\dots,k_m}=n!\cdot\prod_{j=1}^m\dfrac{1}{k_j}=\dfrac{n!}{k_1!k_2!\dots k_m!}$.

I am looking for the special case of this theorem which can be applied to a polynomial of one variable. Thus, I need to find the expansion of $n$th degree polynomial $\left(P(x)\right)^n$, which is $P(x)=\sum_{k=0}^na_kx^k$.

I want to use the Multinomial Theorem to determine the coefficient of the $k$th term of the expanded form of polynomial $P(x)$ raised to the power of $n$, but I can't immediately notice something that would allow me to do that just as easily as I would do it with the Binomial Theorem after expanding binomals.

In other words, Binomial Theorem is too specific for my problem, and Multinomial Theorem is too general. I need to know something in between these two.

Answer 1

Let $P(x):=\sum_{k=0}^m a_kx^k$

When multiplying out $P(x)^n$, each summand of the result is created by by selecting from each factor of $P(x)^n$ a summand and multiplying them. Therefore, to get to degree $k$, we need to choose monoms whose degrees sum up to k:

$$ [x^k] P(x)^n = \sum_{i_1+...+i_n=k\\i_1,...,i_n\in\{0,...,m\}} a_{i_1}\cdots a_{i_n} $$ Here, $[x^k]$ denotes the operator which extracts the coefficient of $x^k$.

Answer 2

I've recently developed a closed-form expression which solves this problem for univariate unit polynomials of arbitrary degree $ D $. This work has been submitted as a preprint and is currently under review.

Formula: \begin{align*} [x^k] \left(\frac{x^{D}-1}{x-1}\right)^n = [x^k] (1 + x + \ldots + x^{D-1})^n = \left\lfloor \left(\frac{D^{Dn} - 1}{D^{n+k} - D^k}\right)^n\right\rfloor \bmod D^n, \\ \quad \text{for } n > 0 \text{ and } 0 \leq k \leq n \cdot (D-1) \end{align*}

This formula allows you to compute the $k$-th coefficient in the expansion directly, bypassing the need for summing multinomial coefficients.

For further details, I refer you to my preprint: Joseph M. Shunia, "A Simple Formula for Binomial Coefficients Revealed Through Polynomial Encoding", September 2023, Preprint Available on GitHub.

Answer 3

If I understand your question correctly, you want to apply the multinomial theorem to the case where $x_0 + x_1 +\ldots+x_m = a_0+a_1t+\ldots + a_mt^m$ (and where I should say that I have switched the notation so that the $x_i$ start at $i=0$ rather than $i=1$, so that things match better with the conventions for polynomials in one variable, and just to make it easier to distinguish, I've set the variable to be $t$ not $x$).

If we set $p(t) = \sum_{k=0}^m a_k t^k$, and apply the multinomial theorem with $x_i = a_i t^i$ we obtain

$$ \begin{split} p(t)^{n} = \left(\sum_{k=0}^m a_k t^k \right)^n &= \sum_{\begin{gathered} k_0+k_1+\dots+k_m=n; \\ k_0,k_1,\dots,k_m\geqslant 0\end{gathered}} \binom{n}{k_0, k_1,\ldots,k_m} .\left(\prod_{s=0}^m (a_st^s)^{k_s}\right) \\ & = \sum_{\begin{gathered} k_0+k_1+\dots+k_m=n; \\ k_0,k_1,\dots,k_m\geqslant 0\end{gathered}} \binom{n}{k_0, k_1,\ldots,k_m} .\left(\prod_{s=0}^m a_s^{k_s}\right).t^{\sum_{s=0}^m sk_s} \end{split} $$

If you take $n=m$, then I'm not sure that the above expression simplifies considerably. Since there are $(m+1)$ $a_i$s and $\sum_{s=0}^m k_s = m$ and $k_s \geq 0$, then at least one $k_s$ is always zero. As a polynomial in $t$, we see that $p(t)^m$ has degree $m^2$, and $0\leq \sum_{s=0}^m s.k_s \leq m^2$.

Answer 4

$$P(x)=\sum_{k=0}^da_kx^k$$

$$[x^k]P(x)^n=\sum_{i=0}^n \binom{n}{i}a_0^i\hat{B}_{k,n-i}(a_1,...,a_d)$$

$\hat{B}_{k,n-i}(a_1,...,a_d)$ is the Partial ordinary Bell polynomial. It enumerates the strict/strong compositions (means part $0$ is forbidden) of integer $k$ into exactly $n-i$ parts, with parts less than or equal to $d$.

$[x^k]P(x)^n$ enumerates the weak compositions (means part $0$ is allowed) of integer $k$ into exactly $n$ parts, with parts less than or equal to $d$.

$$P(x)^n=\sum_{k=0}^{nd}\sum_{i=0}^n \binom{n}{i}a_0^i\hat{B}_{k,n-i}(a_1,...,a_d)x^k$$

$P(x)^n$ enumerates the weak compositions of the non-negative integers less than or equal to $nd$ into exactly $n$ parts, with parts less than or equal to $d$.