# Which solution is correct to this question: find the number of different sequences $(x_1,x_2,x_3,x_4,x_5)$ with following rules

I have two solutions for this problem: find the number of different sequences $(x_1,x_2,x_3,x_4,x_5)$ with following rules $x_i \in \{1,2,3\}$ where $1 \leq i \leq 5$ and $x_1 \leq x_2 \leq x_3 \leq x_4 \leq x_5$

First Solution:

The question is asking about how many multiset we can make then we can uniquely organize it, therefore: $$N=\binom{5-1+3}{3}=\binom{7}{3}$$

Second Solution:

use the conditions to make r inequality: $$y_1=3-x_5 \geq 0$$ $$y_2=x_5 - x_4 \geq 0$$ $$y_3=x_4 - x_3 \geq 0$$ $$y_4=x_3 - x_2 \geq 0$$ $$y_5=x_2 - x_1 \geq 0$$ $$y_6=x_1 - 1 \geq 0$$ Adding them up(each term will be cancelled: $$y_1 + y_2 + y_2 + y_3 + y_4 + y_5 + y_6 = 2$$ the number of solutions of this equation is : $$N = \binom{6-1+2}{2}=\binom{7}{2}$$

which one of them is correct and why so?

• First one is wrongly computed, the number of multisets of $k$ elements taken out of $n$ is $\binom{n + k - 1}{k}$ ($k$ stars with $n - 1$ bars separating them into $n$ groups; select position of the stars), here $\binom{3 + 5 - 1}{5} = \binom{7}{5} = \binom{7}{2}$. Both are right. Aug 12 '15 at 20:34

We need to decide how many $1$'s, how many $2$'s, and (therefore) how many $3$'s there will be. Imagine that there are $3$ kids, Kid1, Kid2, and Kid3. We want to distribute $5$ identical candies between them. The number of ways to do this is $\binom{7}{2}$. Alternately, the number is $\binom{7}{5}$.
Remark: It can be tricky to remember the relevant formulas. My memory for formulas has always been at best mediocre, and is not improving. The way I do it is to imagine giving out $8$ candies, at least one to each kid, and then taking away a candy from each. Intuitively clear Stars and Bars gives that there are $\binom{8-1}{3-1}$ ways to do it.
We have two increments to invoke and 6 possible places to invoke them (counting before $x_1$ and after $x_5$ as possible locations). Therefore we can use the stars-and-bars selection rule to see that ${7}\choose{2}$ is the answer.