A Partition of the Expansion of (1+1+...+1)^n by Multinomial Coefficients

Question

In trying to solve Exercise #12.13.9 (b), p.247, from the textbook "Probability, An Introduction" by Grimmett and Walsh, an exercise about Random Walks on the edges of 3-dimensional cube, I came up with the following identities involving sums of multinomial coefficients: for each $n\in\mathbb{N}$,

$$ \sum_{i_1+i_2+i_3=2n-1 \\ i_1,i_2 \text{ and } i_3 \text{ odd}}\dfrac{(2n-1)!}{i_1! i_2! i_3!} = \dfrac{3^{2n-1}-3}4 \quad \text{and} \sum_{i_1+i_2+i_3=2n-1\\ \text{ exactly one of } \\ i_1, i_2 \text{ or } i_3 \text{ is odd}}\dfrac{(2n-1)!}{i_1! i_2! i_3!} = \dfrac{3^{2n}+3}4 $$

These two sums give a partition of the sum $ \displaystyle\sum_{i_1,i_2,i_3}\dfrac{(2n-1)!}{i_1! i_2! i_3!} = (1+1+1)^{2n-1}=3^{2n-1}$ into two partial sums. Likewise,

$$ \sum_{i_1+i_2+i_3=2n\\ \text{ exactly one of } \\ i_1,i_2 \text{ or }i_3 \text{ is even}}\dfrac{(2n)!}{i_1! i_2! i_3!} = \dfrac{3^{2n+1}-3}4 \quad \text{and} \sum_{i_1+i_2+i_3=2n \\i_1,i_2 \text{ and }i_3 \text{ even}}\dfrac{(2n)!}{i_1! i_2! i_3!} = \dfrac{3^{2n}+3}4 $$

These two sums give a partition of the sum $\displaystyle\sum_{i_1,i_2,i_3}\dfrac{(2n)!}{i_1! i_2! i_3!} = (1+1+1)^{2n}=3^{2n}$ into two partial sums.

The identities above can be proved by induction on $n$, but I wonder if anybody has a better proof, such as a bijective proof or a proof by generating functions. I am interested in generalizations of the identities as well, for example to cubes of arbitrary dimension, from the case of the 3-dimensional cube as given here.

Any comments will be appreciated.

Answer 1

Here is a generating function proof. The multinomial theorem implies $$ (1+x+y)^n=\sum_{\substack{i_1,i_2,i_3\ge 0\\ i_1+i_2+i_2=n}} \frac{n!}{i_1!i_2!i_3!} x^{i_1}y^{i_2} \tag1 $$ By applying this twice, once with $x$ and $y$, once with $-x$ and $y$, and averaging the results, we get $$ {(1+x+y)^n+(1-x+y)^n\over 2}=\sum_{\substack{i_1,i_2,i_3\ge 0\\ i_1+i_2+i_2=n}} \frac{n!}{i_1!i_2!i_3!} y^{i_2}\cdot \frac{x^{i_1}+(-x)^{i_1}}{2} \tag2 $$ How does the RHS of $(2)$ compare to the RHS of $(1)$? Well, note that if $i_1$ is even, then $(-x)^{i_1}=x^{i_1}$, so $\frac{x^{i_1}+(-x)^{i_1}}{2}=x^{i_1}$. However, if $i_1$ is odd, then $ \frac{x^{i_1}+(-x)^{i_1}}{2}=0$. The result is that only the terms where $i_1$ is even survive. I will denote this by saying $$ {(1+x+y)^n+(1-x+y)^n\over 2}=\sum_{\text{$i_1$ is even}}\frac{n!}{i_1!i_2!i_3!} x^{i_1}y^{i_2} $$ This is progress. To get further progress, we apply the same trick to the LHS of $(2)$, but this time average between $y$ and $-y$. The result is $$ \frac{(1+x+y)^n+(1-x+y)^n+(1+x-y)^n+(1-x-y)^n}{4} =\sum_{\substack{\text{$i_1$ is even}\\ \text{$i_2$ is even}}} \frac{n!}{i_1!i_2!i_3!} x^{i_1}y^{i_2} \tag3 $$ Finally, substitute $x\gets 1$ and $y\gets 1$ into $(3)$, and we see that $$ \frac{3^n+1^n+1^n+(-1)^n}{4}=\sum_{\substack{\text{$i_1$ is even,}\\ \text{$i_2$ is even}}} \frac{n!}{i_1!i_2!i_3!} \tag4 $$ Equation $(4)$ explains both of your observations for (even, even, even) and (even, even, odd), depending on the parity of $n$.

For the other two cases, you can instead use the opposite trick; if you instead subtract the $x$ and $-x$ versions before dividing by $2$, the only the odd powers survive. Doing this subtraction trick with both $x$ and $y$, you get $$ {(1+x+y)^n-(1-x+y)^n-(1+x-y)^n+(1-x-y)^n\over 4}=\sum_{\substack{\text{$i_1$ is odd,}\\ \text{$i_2$ is odd}}}\frac{n!}{i_1!i_2!i_3!} $$ Finally, substitute $x=1$ and $y=1$ again to derive the other two formulae, depending on the parity of $n$.

---

All of this generalizes very nicely. For example, if you take the sum of $$\frac{n!}{i_1!\cdot i_2!\cdots i_m!}$$ over all tuples $(i_1,\dots,i_m)$ of nonnegative integers summing to $n$ which are all even, then the result can be proven to be $$ \frac1{2^m}\sum_{k=0}^m\binom{m}k(2k-m)^n $$ using similar methods. However, there is actually a much nicer proof using exponential generating functions; see this answer for that.

Answer 2

#1

The first sum is the coefficient of $x^{2n-1}$ in the expansion of $$(2n-1)!\left(x+\frac{x^3}{3!}+\frac{x^5}{5!}+\ldots\right)^3$$ Using the fact that $e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots$, we can use roots of unity filter to see that $$\frac{e^x-e^{-x}}{2}=x+\frac{x^3}{3!}+\frac{x^5}{5!}+\ldots$$ (If you don't know roots of unity filter, it's not too hard to just expand the taylor series for each of the terms and observe that the above statement is indeed true)

So our generating function is equivalent to $$\frac{(2n-1)!}{8}\left(e^x-e^{-x}\right)^3$$ $$\frac{(2n-1)!}{8}\left(e^{3x}-3e^x+3e^{-x}-e^{-3x}\right)$$ Since the coefficient of $x^{2n-1}$ in $e^{kx}$ is $\frac{k^{2n-1}}{(2n-1)!}$, the coefficient of $x^{2n+1}$ in our generating function is $$\frac{1}{8}(3^{2n-1}-3(1)^{2n-1}+3(-1)^{2n-1}-(-3)^{2n-1})$$ $$\frac{3^{2n-1}-3-3+3^{2n-1}}{8}$$ $$\frac{3^{2n-1}-3}{4}$$

#2 P.S. you might want to include that $i_1,i_2,i_3$ are nonnegative integers.

The second sum can be solved in a similar manner. Just WLOG assume that $i_1$ is odd and $i_2,i_3$ are even. Then multiply by $3$ at the end.

However, there is a faster way to find the result using the expression we found for the first sum.

Consider all the ways to express $2n-1$ as the sum of $3$ nonnegative integers. Using multinomial theorem, $$\sum_{a+b+c=2n-1} \binom{2n-1}{a,b,c}=(1+1+1)^{2n-1}=3^{2n-1}$$

A simple parity argument shows that either exactly $1$ of the summands must be odd, or all $3$ summands must be odd. We know that the sum if all $3$ summands are odd is $$\frac{3^{2n-1}-3}{4}$$

Hence, the sum if exactly $1$ of the summands must be odd is $$3^{2n-1}-\frac{3^{2n-1}-3}{4}$$ $$\frac{4\cdot 3^{2n-1}-3^{2n-1}+3}{4}$$ $$\frac{3\cdot 3^{2n-1}+3}{4}$$ $$\frac{3^{2n}+3}{4}$$