# Basic Combinatorics: How many sequences have at least 3 red balls?

Pick a sequence of 10 balls from a sack containing red, blue, green, yellow, white and black balls. Each time a ball is picked, it is replaced in the sack before the next ball is picked.

a) How many sequences have at least 3 red balls?

b) At least 4 blue balls?

c) exactly 2 black balls AND at least 4 yellow balls?

I don't know where to begin. I believe the total number of sequences is $6^{10}$. For part a) would we choose the first 3 slots out of 5 rather than 6? Overall just very confused.

• A permutation is officially defined as a bijective function from a finite set to itself. The simpler definition is that you take a set of distinct letters (or colors, names, people etc...) such as $\{A,B,C,D,E\}$ and then arrange them in a line such that each appears exactly once. For example $CABED$ or $ABCDE$, etc... Since there is repetition allowed, this is not called a "permutation" but rather a "sequence" or "string." More officially, you are counting the number of functions from the set $\{1,2,\dots,10\}$ to the set $\{red,blue,green,\dots,black\}$. – JMoravitz Dec 14 '15 at 0:36
• @JMoravitz Thanks for the clarification. I've edited my original post. – Hani Al-shafei Dec 14 '15 at 0:39

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$
• Thank you very much. Apologizes for my question errors. – Hani Al-shafei Dec 14 '15 at 1:23

For a, if you mean exactly three red balls like the title (otherwise the answer is zero as all sequences have ten balls), you can first choose the locations for the three red balls, then choose the colors of the other ones. b is similar, but you have to add up various numbers of blue balls. For c, you first choose the locations for the black balls, then choose the locations for yellow balls from what is left (summing over the allowable numbers of yellow balls), then choose the colors for the rest from the four remaining.