I need a combinatorial proof of $\sum_{n_1+n_2+n_3=n} \binom{n}{n_1, n_2,n_3}(-1)^{n_2} = 1$

Question

$$\sum_{n_1+n_2+n_3=n} \binom{n}{n_1, n_2,n_3}(-1)^{n_2} = 1$$ I tried labeling $n$ objects 1 or 2 or 3 and subtracting even numbers of 2 from odd numbers of 2, but couldn't go further. Is there a combinatorial proof not using multinomial theorem?

Answer 1

You can think about this as follows: $$\sum _{k=0}^n\binom{n}{k}(-1)^k=0,$$ unless $n=0,$ which gives $1.$ Now, your expression in the LHS can be written as $$\sum _{n_1=0}^n\binom{n}{n_1}\sum _{n_2+n_3=n-n_1}\binom{n-n_1}{n_2,n_3}(-1)^{n_2}=\sum _{n_1=0}^n\binom{n}{n_1}\sum _{n_2=0}^{n-n_1}\binom{n-n_1}{n_2}(-1)^{n_2}=\binom{n}{n}=1.$$ The combinatorial interpretation of the first formula is as follows. Imagine you have the following function $$\varphi :P([n])\longrightarrow P([n]),$$ where $P([n])$ is the power set of $[n]$ such that if $\varphi (A)=A\setminus {n}$ if $n\in A$ and $\varphi (A)=A\cup \{n\}$ if $n \not \in A.$

Check that $\varphi \circ \varphi = id.$ So this is an involution. Notice also that you can split $P([n])=P_{0}([n])\cup P_1([n])$ considering the size of the set. If it is even, it belongs to $P_0,$ odd belongs to $P_1.$(This means is a reverse sign involution). Further, check that $\varphi $ does not fix any set unless $n=0$(fixes the emptyset). By the involution principle (Check, for example, Aigners book in enumerative combinatorics) the sum equals the number of fix points($=0$).

Answer 2

The coefficient $\binom{n}{r,g,b}$, with $r+g+b=n$, counts the number of ways of assigning colors red, green, blue to the numbers $1, 2,\ldots,n$ such that $r$ numbers are assigned the color red, $g$ numbers are assigned the color green, and $b$ numbers are assigned the color blue.

If $r+g\ne0$ then a new assignment is produced by changing the assignment of lowest-numbered red or green number to the other color (green or red). The parity of $g$ in this new assignment will be opposite that of the original assignment. By this means, a one-to-one correspondence is established between the set of assignments in which at least one number is red or green and the number of greens is even and the set of assignments in which at least one number is red or green and the number of greens is odd.

Only one assignment remains: the all-blue assignment.