Say I have this set: {a,a,a,a,b,b,c,c}
I want to know how many combinations of 3 items I can make. this would be the result I'm looking for:
{a,a,a} {a,b,b} {a,b,c} {a,c,c} {a,a,b} {a,a,c} {b,b,c} {b,c,c}
8 items in total. Another words, order doesn't matter, repetitions are not allowed, but some of the items in my set are of the same type. ( I can't use nCr with repeats because I don't have enough items of type b or c ). I'm total noob. please bear with me.
thanks, Kyle
Best Answer
Hint: Let $x_1, x_2$ and $x_3$ be the number of $a$'s, $b$'s and $c$'s in your combination respectively. So your question is to find the number of nonnegative integer solutions of the equation $$x_1+x_2+x_3=3$$ with the conditions $x_2,x_3\le 2$.
Suppose we have a multiset $\{a,a,a,b,b,c,c\}$. If we try to select $3$ of them, it would be like arranging three $x$ and two vertical sticks $|$ in a row. How is that? OK, let me explain, consider one arrangement of three $x$ and two $|$, for example $$xx||x$$ we can correspond this arrangement to $$aa||c$$ or to the selection $$\{a,a,c\}.$$ For every such arrangement there is one and only one $3$-element selection from our multiset. Thus the answer for number of selections is the number of ways to arrange three $x$ and two $|$in a row, that is $\binom{3+2}{2}=10$, because in such arrangement there are $5$ places to fill with three $x$ and two $|$, and we do that by choosing two places for $|$'s. But don't forget that we can't have three $b$'s or three $c$'s so the final answer is $10-2=8$.
In general the number of nonnegative integer solutions to the equation $$x_1+x_2+\cdots+x_m=n$$ is $\binom{n+m-1}{m-1}=\binom{n+m-1}{n}$.
And there is another method that uses generating functions that is useful for equations with conditions like our equation.