1

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

user803592
  • 13

2 Answers2

2

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.

Woria
  • 1,783
  • 9
  • 15
  • 1
    wow. that makes perfect sense. Just have to figure out how to generalize it into a formula. I was trying to solve it using combination/permutation formulas because that's what I am trying to learn. Anyway, I'll try that, but I might need a few more hints :) – user803592 Mar 03 '14 at 18:10
  • @user803592, I'll be happy to help. – Woria Mar 03 '14 at 18:27
  • alas, I can draw lots of pictures on apiece of paper representing what I'm looking for, but I can't seem to come up with a formula. My latest attempt is to assign the number of possible values of x2 and x3 for each value of x1, which gives me 8 total possibilities:

    when x1 = 0, x2 and x3 could be either 1 or 2, hence two possibilities

    when x1 = 1, x2 and x3 could be either 0, 1 or 2, hence three possibilities,

    etc... for a total of 8 possibilities

     – user803592 Mar 03 '14 at 20:04
  • I can also write it a simple loop algorithm, but, again, that is not what I'm after:

    var count = 0; for(var x = 0; x <=3; x++){ for(var y = 0; y <= 2; y++){ for (var z = 0; z<=2; z++){ if (x+y+z == 3){ count++; } } } } console.log(count);

    count = 8

     – user803592 Mar 03 '14 at 20:37
  • I apologize for the crappy formatting - I don't know how to enter multiple lines – user803592 Mar 03 '14 at 20:39
  • @user803592, I updated the answer, check it! – Woria Mar 03 '14 at 20:51
  • thank you. I guess I was hoping there was some way of accommodating the fact that there are only 2 of b and c. To get the result 10 is the same as combinations with repeats if we were to treat each type of element as one element - so rewriting the original set as {a,b,c} and using the formula: n+r-1 C r (3+3-1 C 3 = 10).But then I have to remember that I have 2 missing.

    So what's the generating functions method?? sounds interesting.

     – user803592 Mar 03 '14 at 21:27
  • @user803592, about the generating functions method, well since number of $a$'s can be $0,1,2,3$ so its generating function is $(1+x+x^2+x^3)$, and since number of $b$'s and $c$'s can be $0,1,2$ so there generating function is $(1+x+x^2)$. Thus the number of combinations that you are looking for is the coefficient of $x^3$ in the following generating function $$(1+x+x^2+x^3)(1+x+x^2)(1+x+x^2)$$ for more details it's better to have look at some discrete math or combinatorics book. – Woria Mar 04 '14 at 03:58
  • that is really really neat. thank you. I have several discrete math books, but they only just arrived :)) Who says you have to start at the beginning, eh? thanks again. I'm sure I'll be back with more noobie questions :) – user803592 Mar 04 '14 at 12:13
-1

if you have $3$ items and want the different combinations of every set, but NOT the $0$ possibility then you can use $2^3 - 1 = 7$; if you want to know the possibilities of the $7$ in sets then you can use the similar formula $2^7 - 1 = 127$. This does not account for the $0$ possibility.

emonHR
  • 2,650
David
  • 1