Online Course Discussion Forum

math challenge II a combinatorics 7.19

 
 
Picture of Jialin Wang
math challenge II a combinatorics 7.19
by Jialin Wang - Tuesday, October 19, 2021, 8:58 PM
 

Suppose you pick an unordered collection (repeats allowed) of six numbers from the set {1,2,3,4,5,6,7,8}{1,2,3,4,5,6,7,8}. How many different collections are possible?

I tried 8*7*6*5*4*3/6! because it's basically choosing from 8 numbers and getting rid of the repititions but i am wrong. I don't know where did the 13C6 comes from. If I am supposed to use stars and bars it should be either 13C5 or 7C5


it says i am supposed to solve it with stars and bars but it satisfies neither of the theorem. It isn't (n+k-1)C(k-1) and it's (n+k-1)Ck instead

 
Picture of Dr. Kevin Wang
Re: math challenge II a combinatorics 7.19
by Dr. Kevin Wang - Tuesday, October 19, 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}$.