Online Course Discussion Forum

math challenge II a combinatorics 7.19

 
 
Picture of Dr. Kevin Wang
Re: math challenge II a combinatorics 7.19
by Dr. Kevin Wang - Tuesday, 19 October 2021, 10:21 PM
 

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