2
$\begingroup$

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.

enter image description here

Any help is appreciated. (Sorry for the bad english)

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

Page 114, task 70

  • 0
    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.2011-12-22

1 Answers 1

3

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

  • 0
    You're right, I solved the other part by myself. Thanks a lot for a) and the hints for b)2012-01-06