I thought of doing it this way:
Since there will be four cases, we just consider each one and then just add the results up in the end.
Case 1: You have exactly $2$ red balls and $3$ blue balls. The number of groups is $P(5,2) \cdot P(4, 3)= 480$.
Case 2: You have exactly $3$ red balls and $2$ blue balls. The number of groups is $P(5,3) \cdot P(4, 2)=720$.
Case 3: You have exactly $4$ red balls and $1$ blue ball. The number of groups is $P(5,4) \cdot P(4, 1)=480$.
Case 4: You have $5$ red balls and no blue balls. You only have one possible group.
Adding up all the results, you get 1201 possible groups. Order doesn't matter here. What am I doing wrong?
[Math] If you have 4 blue balls and 5 red balls, in how many ways can you form a group of 5 balls that must contain at least 2 red balls
combinatoricsdiscrete mathematics
Related Solutions
This problem is a straightforward application of the Polya Enumeration Theorem. Suppose we treat the case of $r$ red balls, $g$ green balls and $b$ blue balls and $n$ indistinguishable bins where no bins are left empty.
Recall the recurrence by Lovasz for the cycle index $Z(P_n)$ of the set operator $\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{SET}_{=n}$ on $n$ slots, which is $$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$
We need to employ the set operator because the elements of a distribution are supposed to be unique.
We have for example, $$Z(P_3) = 1/6\,{a_{{1}}}^{3}-1/2\,a_{{2}}a_{{1}}+1/3\,a_{{3}}$$ and $$Z(P_4) = 1/24\,{a_{{1}}}^{4}-1/4\,a_{{2}}{a_{{1}}}^{2} +1/3\,a_{{3}}a_{{1}}+1/8\,{a_{{2}}}^{2}-1/4\,a_{{4}}.$$
Applying PET it now follows almost by inspection that the desired count is given by using the repertoire
$$-1 + \sum_{q=0}^r R^q \sum_{q=0}^g G^q \sum_{q=0}^b B^q$$
with $Z(P_n)$ to get
$$[R^r G^g B^b] Z\left(P_n; -1 + \sum_{q=0}^r R^q \sum_{q=0}^g G^q \sum_{q=0}^b B^q \right).$$
The minus one term cancels empty bins.
The answer for eight red, six green and seven blue balls in four indistinguishable bins turns out to be $$60040.$$The following Maple code implements two routines, q1 and q2. The first of these computes the value for $(r,g,b)$ and $n$ by brute force (enumerate all configurations) and can be used to verify the correctness of the PET formula for small values of the parameters. The second one uses the PET for instant computation of the desired coefficient.
Observe that we can compute values that are utterly out of reach of brute force enumeration, e.g. with ten balls of each color and five bins we obtain $$7098688.$$With twenty balls of each color and six bins we get $$194589338219.$$
with(combinat);
pet_cycleind_set :=
proc(n)
option remember;
if n=0 then return 1; fi;
expand(1/n*
add((-1)^(l-1)*a[l]*pet_cycleind_set(n-l), l=1..n));
end;
pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;
res := ind;
polyvars := indets(poly);
indvars := indets(ind);
for v in indvars do
pot := op(1, v);
subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];
subs2 := [v=subs(subs1, poly)];
res := subs(subs2, res);
od;
res;
end;
allparts :=
proc(val, size)
option remember;
local res, els, p, pp, q;
res := [];
for p in partition(val) do
if nops(p) <= size then
pp := [op(p), 0$(size-nops(p))];
res := [op(res), pp];
fi;
od;
res;
end;
q1 :=
proc(RC, GC, BC, n)
option remember;
local p, q, pr, pg, pb, res,
sr, sg, sb, dist;
pr := [];
for p in allparts(RC, n) do
pr := [op(pr), op(permute(p))];
od;
pg := [];
for p in allparts(GC, n) do
pg := [op(pg), op(permute(p))];
od;
pb := [];
for p in allparts(BC, n) do
pb := [op(pb), op(permute(p))];
od;
res := {};
for sr in pr do
for sg in pg do
for sb in pb do
dist :=
{seq(R^sr[pos]*G^sg[pos]*B^sb[pos],
pos=1..n)};
if nops(dist) = n and
not member(1, dist) then
res := res union {dist};
fi;
od;
od;
od;
nops(res);
end;
q2 :=
proc(RC, GC, BC, n)
option remember;
local q, rep, sind;
rep := add(R^q, q=0..RC)
* add(G^q, q=0..GC)
* add(B^q, q=0..BC);
sind := pet_varinto_cind(rep-1,
pet_cycleind_set(n));
coeff(coeff(coeff(expand(sind), R, RC),
G, GC), B, BC);
end;
To make notation easier, I will reword the problem to be about strings of length 10 using the characters A,B,C,D,E,F. (Just replace "A" with red, "B" with blue, etc... to go back to the original wording of the question)
The wording for part (a) is a bit confusing. In my initial interpretation, we are counting the number of ways of picking balls such that in the process of picking them, we see exactly three colors total in any order and any amount (except zero). For example, ABACCCCCAC or DAEEEEEEEE. For part (a), we try to count how many length-10 strings have exactly three letters appearing.
- Pick which three letters it is that appear. $\binom{6}{3}$ choices.
- Count how many length-10 strings have specifically the letters A,B,C where all letters appear at least once. (The number of length-10 strings that have specifically three other letters will be the same by symmetry) ($\star$)
- Multiply these numbers to get the total number of length-10 strings that have exactly three letters appearing.
Actually counting $(\star)$ will require a bit of thought. We approach via Inclusion-Exclusion.
- The total number of length-10 strings whose characters are from the alphabet A,B,C will be $3^{10}$ (since for each of the ten positions in the string, we choose one of the characters A,B,C to place in the spot)
- The total number of length-10 strings whose characters are from the alphabet A,B,C which do not have any A's will be $2^{10}$. Similarly for those without B's and those without C's
- The total number of length-10 strings whose characters are from the alphabet A,B,C which do not have any A's or B's will be $1^{10}$. Similarly for the others.
Let $\mathcal{A},\mathcal{B},\mathcal{C}$ denote the events where the character $A,B,C$ are not present respectively. Let $U$ denote the universal event.
We have by inclusion-exclusion $|\mathcal{A}^c\cap\mathcal{B}^c\cap\mathcal{C}^c|=|U\setminus(\mathcal{A}\cup\mathcal{B}\cup\mathcal{C})|=|U|-|\mathcal{A}|-|\mathcal{B}|-|\mathcal{C}|+|\mathcal{A}\cap\mathcal{B}|+|\mathcal{A}\cap\mathcal{C}|+|\mathcal{B}\cap\mathcal{C}|-|\mathcal{A}\cap\mathcal{B}\cap\mathcal{C}|$
$=3^{10}-3\cdot 2^{10}+3\cdot 1^{10}-0=55980$
So, the number of length-10 strings whose characters come from the alphabet A,B,C,D,E,F where exactly three characters appear in the string are $\binom{6}{3}(3^{10}-3\cdot 2^{10}+3)=1119600$.
Another possible interpretation of part (a) is that you forgot a crucial word. Perhaps the original question was "How many strings have exactly three RED balls." (or some other color)
This question is much easier.
- Pick the location of the three red balls. $\binom{10}{3}$
- Pick which ball goes in each other position (note that these cannot be red). $5^{7}$
For a total of $\binom{10}{3}\cdot 5^7$ possible sequences.
(I just noticed the title of question reads "at least" instead of "exactly" as it does in the body of the question. For the question of "at least" approach as in part (b) below)
Part (b) is approached similarly to the second interpretation of part (a) with a bit of inclusion-exclusion thrown in.
Let us count how many ways violate this condition. Count how many have less than 4 blue balls. The number with exactly three blue balls will be $\binom{10}{3}\cdot 5^7$ as calculated previously. With exactly two blue balls will be $\binom{10}{2}\cdot 5^8$. Similarly for exactly one and exactly zero blue balls.
There are then a total of $6^{10}-\binom{10}{3}5^7-\binom{10}{2}5^8-\binom{10}{1}5^9-5^{10}$ sequences with at least four blue balls.
Note, we could have approached directly. By approaching indirectly, we save ourselves some arithmetic. Approaching directly, we have $\binom{10}{4}5^6+\binom{10}{5}5^5+\dots+\binom{10}{9}5^1+\binom{10}{10}5^0$. You will see these equal the same thing.
For part (c), approach similarly to part (b). Break it into cases based on the number of yellow balls and add (or subtract from the total). In the case of picking exactly 2 black balls and 5 yellow balls for example,
- Pick the location of the black balls $\binom{10}{2}$
- Pick the location of the $5$ yellow balls from the remaining available positions $\binom{8}{5}$
- For each still remaining position, pick a color other than black or yellow. $4^3$
Related Question
- [Math] In how many ways can b blue balls and r red balls be distributed in n distinct boxes.
- Distribute red and blue balls into bins. P(No two red balls in a bin)
- [Math] In how many ways can we place 10 identical red balls and 10 identical blue balls into 4 distinct urns if each urn has at least 1 ball
Best Answer
The order of the balls does not matter when choosing the balls in the problem, so you should be using combinations instead of permutations when solving the problem. Thus, the correct answer should be $$C(5,2)C(4,3)+C(5,3)C(4,2)+C(5,4)C(4,1)+C(5,5)C(4,0)=121$$.