A coin is flipped 15 times where each flip comes up either heads or tails. How many possible outcomes (a) contain exactly four tails?, (b) contain at least three heads?
Hello everyone, I am currently a beginner at combinatorics and discrete math and any comments or answers would be extremely helpful with this question as I am still getting the hang of them. Thank you so much in advance! All contribution really helps :D
Let's try to come up with an idea for a):
We start with something easier: How many possible outcomes contain exactly one tails? Well obviously $15$ since it can happen at either of these 15 throws.
Let's update our question to: How many possible outcomes contain exactly two tails? We know the first tails has 15 possible throws where it can appear. The second tails has to happen at a different throw, so there are only 14 throws left. But each of these throws would be okay. So what does this mean? Well, for each of the 15 possibilities for the first tails there are 14 possibilities for the second tails left. We are tempted to say the answer is therefore $15\cdot 14 = 210$ but we would be wrong. There is a problem we need to fix first. We counted every possible combination twice! For example we could have placed the first tails at throw 1 and the second tails at throw 2 but we could also have placed the first tails at throw 2 and the second at throw 1. In the end this yields the same outcome, meaning first and second throw are tails and rest is heads. We can fix this by dividing by $2$. So we get the answer $$\frac{15\cdot 14}{2} = 105\,.$$
So what happens if we ask: How many possible outcomes contain exactly three tails? The idea is the same. We have 15 throws to place the first tails. We have 14 positions to place the second tails. Now we are left with 13 throws to place the third tails. Combining these we get $15\cdot 14\cdot 13$ possibilities which contain duplicates like before. We need to find out how many duplicates of each possibility we have. In our second example this was $2$. Here it's a bit more complicated. We can have first tails throw 1, second tails throw 2 and third tails throw 3. Now we could also have first tails throw 2, second tails throw 3 and third tails throw 1. So in essence, for every possible way to arrange the three different tails at throw 1, 2 and 3, we have a duplicate. How many ways are there to arrange the first, second and third tails? That's $3 \cdot 2 \cdot 1 =6$. It's the same logic as before. The first tails has three positions to go to, the seoncd has two, the last has one.
This yields a formula which we can now state. It's $$\frac{n!}{k!\cdot(n-k)!}$$
This formula calculates how many ways there are to take $k$ things from $n$ total things. In your case this would be how many ways there are to have $k$ many throws land on tails when performing a total of $n$ throws.
A short reminder: $$n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1\,.$$ So for example $$3! = 3 \cdot 2 \cdot 1 = 6\,.$$
Let's try to understand this formula. First look only at $$\frac{n!}{(n-k)!}\,.$$ Let's put some numbers in. We chose $n=15$ and $k = 2$. We get $$\frac{15!}{(15-2)!} = \frac{15!}{13!} = \frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot \ldots \cdot 2\cdot 1}{13 \cdot 12 \cdot \ldots\cdot 2 \cdot 1} = 15 \cdot 14\,,$$ because many things cancel out. Notice that this is exactly the first thing we calculated in example 2. So this part $$\frac{n!}{(n-k)!} = n \cdot (n-1) \cdot\ldots\cdot (n-(k-1))$$ actually calculates this first step in our examples. It tells us how many ways there are to take $k$ many ordered things from $n$ total things.
We are not interested in orderings of $k$. So for us each way in which we take the $k$ things from the same positions is the same, regardless of ordering. We therefore have to calculate how many orderings of $k$ there are. And thats $k!$, it's exactly the argument we used in in example 3. Therefore we need to divide by $k!$. This yields the complete formula $$\frac{n!}{k!\cdot(n-k)!}\,.$$
You now should be able to tackle problem a) (you got the formula). There is now an easy (and an even easier) way to calculate b) using this formula, but you can't just use it since b) asks for at least but the formula only gives you an answer for exactly.
I hope this helps.