Assume $j$ is fixed, prove the following: $$\sum_{i}\binom{n}{i, j, n-i-j} = 2^{n-j}\binom{n}{j}$$ So the left hand side reminds me the multinomial theorem and we can think of a long sequence word that made with $3$ types of letter. The number of first type is $i$, second is $j$ and third is $n - i - j.$ But I'm not sure how the summation and $j$ is fixed matters here and to made the LHS equal to RHS by some tricks.
Any help would be really appreciate.
On
For an algebriac proof: \begin{eqnarray*} \binom{n}{i,j,n-i-j} = \binom{n}{j} \binom{n-j}{i} \end{eqnarray*} and use the binomial theorem.
For a combinatorial proof: The RHS counts words of length $n$ on the alphabet $\{0,1,2 \}$ with exactly $j$ $0$'s.
The LHS counts words with $j$ $0$'s and $i$ $1$'s ... and $i$ varies from $0$ to $n-j$.
I think you're most of the way there. Let's count the number of words of length $n$ in the alphabet $\{a,b,c\}$, with $a$ occurring $j$ times. One way to do this is to first fix the $a$'s, which contributes a factor of $\binom{n}{j}$, and all remaining characters can be either $b$ or $c$, contributing a factor of $2^{n-j}$, giving us the right hand side.
Another way to count this is to sum over all possible number of $b$'s that occur. If $b$ occurs $i$ times, there are $\binom{n}{i,j,n-i-j}$ such strings, and summing over all $i$, we have the left hand side.