Central Binomial Coefficients and Multinomial Coefficients

binomial-coefficientscombinatoricsmultinomial-coefficientsmultinomial-theorem

Premise

I was looking at the multinomial coefficients when selecting by a specific rule. Then analyzing the sum.

Given the multinonial theorem ($n > 0$):

$$
(x_1+\ldots+x_n)^n = \sum_{k_1+\ldots+k_n=n\text{; }k_1,\ldots,k_n\geq 0} \binom{n}{k_1,\ldots,k_n} \prod_{t=1}^{n} x_t^{k_t}
$$

We define the following function that selects particular terms when the sum of the powers times their index is equal to $2n-1$.

$$
f\{(x_1+\ldots+x_n)^n\} = \sum _{k_1+2k_2+\ldots+nk_n=2n-1\text{; }k_1,\ldots,k_n\geq 0} \binom{n}{k_1,\ldots,k_n} \prod_{t=1}^{n} x_t^{k_t}
$$

If you sum these coefficients, you will get the central binomial coefficients.

$$
\sum _{k_1+2k_2+\ldots+nk_n=2n-1\text{; }k_1,\ldots,k_n\geq 0} \binom{n}{k_1,\ldots,k_n} = \binom{2n-2}{n-1}
$$

Here are the first five:

$$
f\{(x_1)^1\} = x_1\\
f\{(x_1+x_2)^2\} = 2x_1x_2\\
f\{(x_1+x_2+x_3)^3\} = 3x_1^2x_3 + 3x_1x_2^2\\
f\{(x_1+\ldots+x_4)^4\} = 4x_1^3x_4 + 4x_1x_2^3 + 12x_1^2x_2x_3\\
f\{(x_1+\ldots+x_5)^5\} = 5x_1^4x_5 + 5x_1x_2^4 + 10x_1^3x_3^2 + 20x_1^3x_2x_4 + 30x_1^2x_2^2x_3
$$

Question

There has to be some obvious connection between the coefficients selected and the central binomial coefficients that I am just not seeing. Does anyone know how these are connected or would know how to select these terms from the polynomials?

Best Answer

When considering \begin{align*} \left(x_1+x_2+\cdots+x_n\right)^n \end{align*} we multiply $x_j$ with $t^j$ to track the index of the variable $x_j$. In the following we use the coefficient of operator $[t^k]$ to denote the coefficient of $t^k$ of a series $A(t)$ .

We show the following is valid for $n\geq 2$: \begin{align*} \color{blue}{[t^{2n-1}]\left(x_1t+x_2t^2+\cdots+x_nt^n\right)^n\Big|_{x_1=x_2=\cdots=x_n=1} =\binom{2n-2}{n-1}}\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{[t^{2n-1}]}&\color{blue}{\left(x_1t+x_2t^2+\cdots+x_nt^n\right)^n\Big|_{x_1=x_2=\cdots=x_n=1}}\\ &=[t^{2n-1}]\left(t+t^2+\cdots+t^n\right)^n\tag{2}\\ &=[t^{n-1}]\left(1+t+\cdots+t^{n-1}\right)^n\tag{3}\\ &=[t^{n-1}]\left(\frac{1-t^n}{1-t}\right)^n\tag{4}\\ &=[t^{n-1}]\frac{1}{\left(1-t\right)^n}\tag{5}\\ &=[t^{n-1}]\sum_{k=0}^{\infty}\binom{-n}{k}(-t)^k\tag{6}\\ &=\binom{-n}{n-1}(-1)^{n-1}\tag{7}\\ &\,\,\color{blue}{=\binom{2n-2}{n-1}}\tag{8} \end{align*}

Comment:

  • In (2) we evaluate the expression at $x_1=x_2=\cdots=x_n=1$.

  • In (3) we factor out $t^n$ and apply the rule $[t^{p-q}]A(t)=[t^p]t^qA(t)$.

  • In (4) we apply the finite geometric series formula.

  • In (5) we skip all terms in the numerator $\left(1-t^n\right)^n=\sum_{j=0}^n\binom{n}{j}(-t^n)^j$ besides the constant term $1$ as the other terms do not contribute to $[t^{n-1}]$.

  • In (6) we make a binomial series expansion.

  • In (7) we select the coefficient of $t^{n-1}$.

  • In (8) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

Related Question