Proof $\left|N\right|=\left|M\right|$ with $M=(n_1,…n_s) \mid n_i$ and $N=(n_1,…,{n_s+1}) \mid n_i$

I have to solve the following and I don't know where to start:

Let $w \in \mathbb{N}_0$, where $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$. Furthermore, let

$M=\{ (n_1,...,n_s) \mid n_i \in \mathbb{N}_0, \; \sum_{i=1}^s n_i \leq w \}$

and

$N=\{ (n_1,...,n_s,n_{s+1}) \mid n_i \in \mathbb{N}, \; \sum_{i=1}^{s+1} n_i = w+s+1 \}$.

Prove:

a) $\left|N\right|=\left|M\right|$

b) $\left|N\right|=\binom{w+s}{s}$

Hint: $\left|N\right|$ is the number of possibilities to put s crosses in the gaps between w+s+1 points on a line. Any help is appreciated. (Sorry for the bad english)

Edit: The problem is from a german textbook, you can have a look here:

• Is $\mathbb{N}_0$ the set of nonnegative integers? – Dimitrije Kostic Dec 21 '11 at 23:50
• thanks for the commands: I added the link to the textbook and removed a mistake: The upper limit of the 2nd sum is s+1 not s, sorry for that. – ulead86 Dec 22 '11 at 0:08

Look in Wikipedia under Stars and Bars. The discussion there is quite clear. The bars correspond to your crosses.

Your problem is a little different from the one described there. For your $M$, you can think of the problem as follows. You have $w$ identical candies, and you want to distribute some (including the possibility of $0$) or all of them between $s$ (not identical!) children. Then $|M|$ counts the number of ways of doing this. The problem discussed in Wikipedia envisages giving away all the candies. But this can be dealt with by adding an abstract new "child" who will get the rest of the $w$ candies, if the real children don't get them all.

Or else, in terms of equations and inequalities, $|M|$ counts the number of solutions $(x_1,\dots, x_s)$ of the inequality $x_1+\cdots +x_s\le w$ in non-negative integers. This is the same as the number of solutions of the equation $x_1+\cdots+x_s+y=w$ in non-negative integers. Although it is equations that the Wikipedia article deals with, their treatment can be transferred to your inequality setting.

With the above way of dealing with $\le w$, the rest should be straight "Stars and Bars." To continue the candy analogy, the number of ways to distribute $w$ candies between $n$ children, with some kids getting possibly $0$ candies, is the same as the number of ways to distribute $w+n$ candies among $n$ children, with each child getting at least $1$. (Distribute the $w+n$ candies, at least $1$ to each kid. Then take away $1$ candy from each kid.)

Addendum: We describe an explicit bijection $\varphi$ from $M$ to $N$. The verification that $\varphi$ is indeed a bijection is routine, but we will do all the details! The downside is that the presentation is somewhat lengthy, and makes an intuitively clear procedure (say one described in terms of candies and kids) seem more difficult than it really is.

Let $(n_1,n_2,\dots,n_s) \in M$. Define $\varphi(n_1,n_2,\dots,n_s)$ by $$\varphi(n_1,n_2,\dots,n_s)=(n_1+1,n_2+1,\dots,n_s+1, w+1 -(n_1+n_2+\cdots+n_s)). \qquad\qquad(\ast)$$ Note that $\varphi(n_1,n_2,\dots,n_s)$ is an $(s+1)$-tuple. Since $n_1,n_2,\dots, n_s$ are in $\mathbb{N}_0$, that is, $\ge 0$, it follows that $n_1+1,n_2+1,\dots,n_s+1$ are all $\ge 1$, that is, they are in $\mathbb{N}$. What about the last component $w+1-(n_1+n_2+\cdots+n_s)$ of $\varphi(n_1,n_2,\dots,n_s)$? The sum $n_1+n_2+\cdots+n_s$ is $\le w$, since $(n_1,n_2,\dots,n_s)\in M$, so $w+1-(n_1+n_2+\cdots+n_s) \ge 1$.

We need to show that $\varphi(n_1,n_2,\dots,n_s)\in N$. This means that we need to show that $$(n_1+1)+(n_2+1)+\cdots +(n_s+1) +(w+1-(n_1+n_2+\cdots+n_s))=w+s+1.$$ Note that the $n_i$ cancel. We get $s$ $1$'s from the first $s$ terms, plus $w+1$ from the last term, for a total of $w+s+1$.

Next we show that $\varphi$ is injective. Suppose that $\varphi(a_1,a_2,\dots,a_s)=\varphi(b_1,b_2,\dots,b_s)$. We need to show that $(a_1,a_2,\dots,a_s)=(b_1,b_2,\dots,b_s)$. So we know that the $(s+1)$-tuple $$(a_1+1,a_2+1,\dots ,a_s+1, w+1-(a_1+a_2+\cdots+a_s))$$ is the same as the $(s+1)$-tuple $$(b_1+1,b_2+1,\dots ,b_s+1, w+1-(b_1+b_2+\cdots+b_s)).$$ It is immediate that $a_1=b_1$, $a_2=b_2$, and so on, and thus $(a_1,a_2,\dots,a_s)=(b_1,b_2,\dots,b_s)$.

Finally, we show that $\varphi$ is surjective. Suppose that the $(s+1)$-tuple $(c_1,c_2,\dots, c_s,c_{s+1})\in N$. Define $(a_1,a_2,\dots,a_s)$ by $a_i=c_i-1$. So $c_i=a_i+1$.

Since the $c_i$ are by definition $\ge 1$, the $a_i$ are $\ge 0$. Since $c_1+c_2+\cdots+c_s+c_{s+1}=w+s+1$, we have $c_1+c_2+\cdots+c_s\le w+s$, and therefore $a_1+a_2+\cdots+a_s \le w$. Finally, $$c_{s+1}=w+s+1-(c_1+c_2+\cdots+c_s)=w+1-(a_1+a_2+\cdots+a_s),$$ and therefore by the definition $(\ast)$ of $\varphi$ we have $$\varphi(a_1,a_2,\dots,a_s)=(c_1,c_2,\dots, c_s, c_{s+1}).$$

• Sorry for unchecking the answer. I thought about it during the last few days, but I still don't have a clue how to proove it in a formal way (I understood your analogy). Perhaps you could add a start? – ulead86 Jan 3 '12 at 17:37
• No problem! If you tell me fairly exactly what it is that you need, I can try to fill in detail. Beside the analogy, there is already a more formal part of the post, that deals with counting the solutions of a certain equation. The Wikipedia article also is partly formulated in terms of equations. – André Nicolas Jan 3 '12 at 17:48
• I tried to find a bijection to proove that the both set's have the same cardinality. It's ok to start that way? – ulead86 Jan 3 '12 at 19:24
• The bijection part has been written up, but not proofread carefully. All the components, however, are basically or completely right. I take it that the counting of $N$ is not a problem for you anymore, if it ever was. The writeup makes things look more complicated than they really are! – André Nicolas Jan 3 '12 at 22:05
• You're right, I solved the other part by myself. Thanks a lot for a) and the hints for b) – ulead86 Jan 6 '12 at 19:45