Today I saw this question in a book:
There are $12$ objects, $3$ of which are alike and the remainder all different. In how many ways can a selection of $5$ be made?
I tried to answer:
$k=11, r=5$. The formula is $C(k+r-1,r) = C(11+5-1,5) = C(15,5) = 3003$.
But the solution says $666$.
How is that possible?
Thanks a lot.
Update
Let me tell you what was written in my book:
If we ignore 3 repeated items, there would be possible ${12\choose 5}$= 792 arrangements.
However if we consider the 3 repeated objects as one object we are left with 9 objects and 4 selections. Hence there are ${9\choose 4 }$= 126 possible arrangements.
Hence we have to subtract this number from the previous one i.e.
There are 792-126= 666 different ways...
Hence it is giving answer as 666
I am facing this problem in Multi sets. The problem is that for some problems we use stars and bars, for other problems we use some other way...How should we think when we are given a multiset Combination Problem...? Thanks!
Update 2
While I was thinking, I found this another formula similar to the formula given by frogeyedpeas. Please check if this formula is correct:
${n-k\choose r-k}$+${n-k\choose r-k+1}$+${n-k\choose r-k+2}$+.....+${n-k\choose r-k+r}$
Thanks
So we can do a case work based approach:
Case 1: (none of the objects that are alike are chosen), then there are 9 objects we choose from and choose 5 so we have $ \frac{9!}{5!4!}$ ways to do this.
Case 2: (We select one similar object), then the other 4 are selected from the 9 objects so we have $\frac{9!}{4!5!}$ ways to do this.
Case 3: (We select two similar objects), then the other 3 are selected from 9 so we have $\frac{9!}{3!6!}$.
Case 4: (We select all the similar objects), the the other 2 are selected from 9 so we have $\frac{9!}{2! 7!}$. Thus the total number of ways is:
$$ \frac{9!}{2! 7!}+ \frac{9!}{3!6!} + \frac{9!}{4!5!} + \frac{9!}{5!4!} = 36 + 84 + 126 + 126 = 372$$
Either you've made a mistake reviewing the answer and posting it here, or the book is wrong.
In either case a more general answer can found by observing $n$ objects of which $k$ are similar and we want to select $s$. That we are summing
"number of ways to select s objects from n, that aren't one of the k"
"number of ways to select s-1 objects from n, and one of the k"
"number of ways to select s-2 objects from n, and two of the k"
$$\vdots$$ 1. "number of ways to pick 0 objects from n and s from k" OR 2. "number of ways to pick s-k objects from n and all k from k"
If K > S then we descend to case 1. If S < K then we descend to case 2.
Ultimately we descend to the case "number of ways to pick $\max(0,s-k)$ objects from n and $\max(s,k)$ objects from k".
Notice in general that
"number of ways to select G objects from n and W objects from k" is given by
$$ \begin{pmatrix} n - k \\ G \end{pmatrix} $$.
(Notice that $W$ doesn't matter, since all the k objects are the same, so picking any $W$ is the SAME event).
So we are now summing
$$ \begin{pmatrix} n - k \\ G \end{pmatrix} \forall G \in {s, s-1, ... \max{(0, s-k)}} $$
Which gives us:
$$ \begin{pmatrix} n-k \\ s \end{pmatrix} + \begin{pmatrix} n-k \\ s-1 \end{pmatrix} + \begin{pmatrix} n-k \\ s-2 \end{pmatrix} + ... \begin{pmatrix} n - k \\ \max(0, s-k)\end{pmatrix} $$
As desired.