8
$\begingroup$

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.$$

$\endgroup$

1 Answer 1

16
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.