# In search of a combinatorial reasoning for a vanishing sum

Assume $s, j \in\mathbb{N}$. Define the set $$\mathcal{A}_{j,s}:=\{(n_1,n_2,\dots,n_j)\in\mathbb{Z}_{\geq0}^j\vert \, n_1+2n_2+\cdots+jn_j=j, \, n_1+n_2+\cdots+n_j=s\}.$$

Question. Is there a combinatorial argument for this? $$\sum_{s=0}^j(-1)^{j-s}\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_j}=0.$$ I've an algebraic proof.

Update. Here is the proof that I mentioned. Below, $[x^k]F(x)$ denotes the coefficient of $x^k$ in $F(x)$.

This Multinomial Theorem with the specializations $a_i=x^i,\, k=j$ and $n=s$ offers $$(x+\cdots+x^j)^s=\sum_{n_1+\cdots+n_j=s}\binom{s}{n_1,\dots,n_j}x^{n_1+2n_2+\cdots+jn_j} =\sum_{j} x^j\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_j}.$$ It follows that the coefficient of $x^j$ in $(x+\cdots+x^j)^s$ equals $\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_j}$. On the other hand, $(x+\cdots+x^j)^s=x^s(1-x^j)^s(1-x)^{-s}$. Consequently, the coefficient of $x^j$ is: \begin{align} [x^j]\,\,\,x^s(1-x^j)^s(1-x)^{-s}&=[x^j]\,\,\,x^s\sum_a(-1)^s\binom{s}ax^{aj}\sum_b\binom{s+b-1}bx^b \\ &=[x^j]\,\,\,x^s\sum_b\binom{s+b-1}bx^b=\binom{j-1}{j-s}=\binom{j-1}{s-1}. \end{align} We proved $\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_k}=\binom{j-1}{s-1}$. Binomial Theorem gives: $\sum_{s=1}^jy^s\binom{j-1}{s-1}=(1+y)^{j-1}$. We conclude that $$\sum_{s=0}^j(-1)^{j-s}\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_k}=\sum_{s=0}^j(-1)^{j-s}\binom{j-1}{s-1}=0.$$

For fixed $s,j>0$, $\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_j}$ enumerates the compositions of $j$ into $s$ positive parts by ordering the corresponding partitions. That is, we have $$\sum_{\mathcal{A}_{j,s}}\binom{s}{n_1,\dots,n_j}=\binom{j-1}{s-1}$$ and the identity in question follows trivially.