Online Course Discussion Forum

math challenge II a combinatorics 7.19

 
 
WangDr. Kevin的头像
Re: math challenge II a combinatorics 7.19
WangDr. Kevin - 2021年10月19日 Tuesday 22:21
 

The question says "repeats allowed", so it means that the collection of six numbers could be {1,1,4,7,7,7}, or something similar. and this is not just choosing 6 numbers out of 8.  We have to consider a different method.

The idea is to use Stars and Bars.  However, in order to use the Stars and Bars method, we have to figure out what exactly the equation is, and what is $n$, what is $k$.  Without that, the formula $\binom{n+k-1}{k-1}$ has no meaning.  Do not blindly plug number into formulas, without knowing what each of the variables mean for this particular problem.

Because repeats are allowed, we don't know how many times each number is chosen, but we do know that we are choosing $6$ numbers in total.  So let $x_1$ represent the number of times we choose $1$, $x_2$ be the number of times we choose $2$, etc.  Any of the numbers $x_1$, $x_2$, $\ldots$, $x_8$ could be $0$, and $$x_1+x_2+x_3+\cdots +x_8=6.$$  We want to find out how many nonnegative solutions this equation has.  This is the Stars and Bars equation.  Here $n=6$ and $k=8$, or we say there are $6$ stars and $7$ bars, and the answer is $\binom{13}{6}$.