Parity of the sum

Question

How can I decide upon the parity of the expression $N_{n}=\sum_{k=1}^n\sum_{s=0}^k\binom{n}{s}\binom{n-s}{k-s}$? Here, $n,k\in \mathbb{N}$.

I tried it for $n=1,2,3,4,5,6$. I found that it is odd for $n=2,3,5,6$ and even for $n=1,4$.

Answer 1

The expression is a contrived way to write down the number of ways to put $n$ different objects into three boxes, say $A$, $B$ and $C$ so that not all objects land in $C$.

Namely, first choose the number $k, 1\le k \le n$ of objects to put into $A$ or $B$. For every such $k$, choose the number $s$, $0\le s\le k$ of objects to put in $A$ and the rest $(k-s)$ objects will be in $B$. Now choose (in $n\choose s$ ways) those objects for $A$ and then, out of the remaining $n-s$ objects, choose (in ${n-s}\choose{k-s}$ ways) the $k-s$ objects for $B$. All the remaining $n-k$ objects go into $C$.

This procedure is equivalent to just labelling every object with "A", "B" or "C" (which can be done in $3^n$ ways) with avoiding the situation when they are all labelled with "C" (this is where "$-1$" in $3^n-1$ come from).

Thus, the sum $N_n$ is $N_n=3^n-1$, which is always even.

Answer 2

Note that $$ {n \choose s} {n-s \choose k-s}={n \choose k}{k \choose s}$$ Then $$S_n=\sum_{k=1}^{n} \sum_{s=0}^{k} {n \choose s} {n-s \choose k-s}=\sum_{k=1}^{n} \sum_{s=0}^{k}{n \choose k}{k \choose s}=\sum_{k=1}^{n}{n \choose k}\sum_{s=0}^{k} {k \choose s}.$$ $$\implies S_n=\sum_{k=1}^{n} {n \choose k} 2^{k}=(1+2)^n-1=3^n-1$$