4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – vonbrand Aug 12 '15 at 20:34
2
$\begingroup$

The second is correct. Here is my corrected version of your first calculation, which is less work than your second.

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.

$\endgroup$
1
$\begingroup$

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.

"Stars and bars"

I think of this as sticks and stones... we have 5 sticks and 2 stones to go into 7 places. Lay down the stones in 2 places, fill up the spaces with sticks |||*|*| and view the sticks as dividers between the 6 locations of interest.

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