# Why do we use nCk when determining numbers of favorable outcomes of coin tosses?

After delving back into probability a bit, I'm absolutely stumped as to why we would use nCk to answer the question "What is the probability of getting 3 heads when tossing a fair coin 10 times?" I know that the problem needs to be answered as '#favorable outcomes/ total possible outcomes', but from what I understand about combinations from this source,

the combination function would treat outcomes such as 'HHHTTTTTTT' and 'HTHTHTTTTT" as redundant since each outcome is a subset containing the same elements and is, in effect, 1 combination - yet the answer to the problem says there are 120 possible combinations, each having H occur threes times. I though this would be the same as considering {a,b,c} and {c,b,a} as different permutations of the same combination. Obviously I'm misunderstanding this, and I haven't been able to find an explanation thus far.

So far, I am stuck on finding an explanation for why combinations would be used when H and T can be used more than once - doesn't this imply that they're not "distinct elements"? According to the MIT pdf, combinations deal with distinct elements belonging to a larger set, and the outcome is the total number of subsets containing k distinct elements without regard to order. Yet in this example the order of H's in the string of flips matters, since getting a different order qualifies that set as a distinct favorable outcome.

Thank you for reading and considering.

• There are $n$ flips, we have to choose $k$ of them, the ones that are going to be heads. There are $nCk$ ways to do it. – Jorge Fernández Hidalgo Jan 28 '16 at 3:16
• Sure, but how does that use of nCk fit in with the definition of subsets and sets that it was defined with in the paper? – Richard Stein Jan 28 '16 at 3:19
• Oh ok, there are $n$ ways to choose the first element, $n-1$ for the second and so on. SO $n\times(n-1)\dots \time(n-k+1)=\frac{n!}{(n-k)!}$ in total. However you have counted each outcome $k!$ times,because the order can be swapped without changing the elements. So answer is $\frac{n!}{k!(n-k)!}$. – Jorge Fernández Hidalgo Jan 28 '16 at 3:23
• Would it make sense if the each flip was given a number 1-10, and think of the question as asking "how many ways can you pick 3 winners out of 10?" In that case, picking 1,2,3 would be different than picking 1,2,4, and so on. Unfortunately I don't follow your explanation in the previous comment, because there are only 2 ways to pick the first element: Heads or tails, not $n$, since $n$ = 10 – Richard Stein Jan 28 '16 at 3:27
• The point is that if you want three heads out of ten tosses you are not ultimately interested in which tosses are heads, just that there are three of them. It is in this sense that the order doesn't matter. The event "Three Heads" is made up of "Heads in positions 1,2,3 tails elsewhere" and a number of similar equally likely events - it is these events which are counted by the combination formula, which is often written $\binom nk$ rather than nCk. The situation is so common that it is often expressed in informal language. – Mark Bennet Jan 28 '16 at 6:02

It's due to a fundamental misunderstanding of probability. For the simple case:

$\text{Probability of an event E} = \dfrac{\text{Number of cases satisfying E}}{\text{Total number of cases}}$ where all the cases are equally likely.

You totally missed the bold part, and hence thought that the order doesn't matter. You are free to choose any way of dividing the possible outcomes into equally likely cases, but the most reasonable way in your case is to consider each sequence of coin flips as one case. The order clearly matters. "HH" and "HT" and "TH" and "TT" are all equally likely, so one cannot group "HT" and "TH" in one case just because there are the same number of heads and tails. So the total number of cases with $3$ heads is exactly the number of ways to choose $3$ positions in the sequence of $10$ flips to be "H" and the rest to be "T". That comes to $\binom{10}{3}$ ways. The total number of cases is $2^{10}$.

• Okay, this makes sense. But why are the number of ways to choose 3 positions out of 10 a combination and not a permutation? – Richard Stein Jan 28 '16 at 3:55
• I only ask this because I come across quotes as such: "C(n,r) is the number of 'combinations' of r things that can be chosen from n different things. It is used when the order within the combination is not important." – Richard Stein Jan 28 '16 at 4:04
• @RichardStein: That quote is utter rubbish. I will explain briefly. First you need to know that number of ways to do a sequence of independent tasks is exactly the product of the number of ways to do each task. This means that the number of ways to arrange $n$ distinct objects is $n \times (n-1) \times \cdots \times 1$, which is denoted $n!$. But if you think it is obvious, then you don't understand it. The way to justify it properly is as follows. There are $n$ possible choices for the object at position $1$, and in all cases after that we have $n-1$ objects left, [continued] – user21820 Jan 28 '16 at 4:08
• @RichardStein: so after having placed the object at position $1$, there are $n-1$ possible choices for the object at position $2$, and again **in all cases after that we have $n-2$ objects left. As you can see, this means that despite the choices being dependent on the previous choices, the total number of ways is still the product $n!$. Now with exactly the same reasoning we can see that if we want to take $k$ of $n$ distinct objects and put them in a line, then the number of ways is $n \times (n-1) \times \cdots \times (n-k+1) = \frac{n!}{(n-k)!}$. [continued] – user21820 Jan 28 '16 at 4:12
• @RichardStein: This is what some people call "permutations", but it really is not a meaningful name. Now if we just want to take $k$ of $n$ distinct objects but don't want to put them on a line but instead put them in a bag with no order at all, then notice that we can first put them on a line, and then put them into the bag. How many arrangements would end up giving the same bag contents? There are $k!$ ways to put the bag contents into a line, so $k!$ arrangements will give exactly the same contents when put into a bag. So total is $\frac{n!}{(n-k)!k!}$. [continued] – user21820 Jan 28 '16 at 4:16

Imagine that you have $10$ balls. Call the balls $B_1, B_2,...B_{10}$. The number of sets of $3$ balls which can be made is $10C3$. A set of three balls could be $\{B_2,B_7,B_9\}$. Since this is a set, it is equal to $\{B_7,B_2,B_9\}$. The number of ordered lists you can make without repeating an element is $10P3$. An example of an ordered list is $(B_2,B_7,B_9)$. This is distinct from $(B_7,B_2,B_9)$. The "order does not matter" for the combinations, and "the order does matter" for the permutations, but these terms are often confusing, and I think it is better to think in terms of subsets vs. lists.

In your case, you have 10 coin flips. These occur in an order, but that fact is a red herring. We have to change our perspective on the problem a bit. If we want three heads, we can achieve this by picking out a subset of the 10 flips to be heads. Call the flips $F_1,F_2,...,F_{10}$. The subset $\{F_2,F_7,F_9\}$ and the subset $\{F_7,F_2,F_9\}$ both refer to the same sequence $THTTTTHTHT$. This shows that the number of sequences containing exactly three heads is the same as the number of subsets of size three coming from a set with 10 elements. So the answer is $10\choose3$.

• So, from your explanation, the set we are considering when we find the total number of arrangements containing 3H's is not the sample space of the 10 coin flips? EDIT: Your explanation of subsets referring to a sequence helps visualize the intuitive decision of how to model this problem. – Richard Stein Jan 28 '16 at 5:18
• "Sample space" is a term of art, which refers to the full set of possible outcomes. In this case, the sample space would have $2^{10}$ elements. The "event" of getting $3$ heads is the subset of the sample space consisting of all the outcomes of interest. – Steven Gubkin Jan 28 '16 at 5:26
• Okay. And continuing that reasoning, the outcomes of interest is a subset consisting of all distinct subsets referring to a sequence of flips containing 3 heads. – Richard Stein Jan 28 '16 at 5:31
• You can formulate things that way, sure. The whole "sample space"/"event" thing is a bit technical, and I just made that comment because you used the words "sample space" in a slightly confused way in your first comment. I don't think it is something to get caught up on. The real meat here is the correspondence between subsets and sequences, in the case case when there are only two choices (like heads/tails). – Steven Gubkin Jan 28 '16 at 5:43

More properly they should have said that there are $120$ possible arrangements, or outcomes.   The use of the word "combination" at that point is misleading, as combination usually signifies selection without order.   Here, order of occurrence is actually significant, as each coin is a unique individual.

Consider tossing two coins, and let $X_2$ be the count of heads. Then $$\mathsf P(X_2{=}0) = \mathsf P({\rm TT}) = 1/4 \\ \mathsf P(X_2{=}1) = \mathsf P({\rm HT\cup TH}) = 2/4 \\ \mathsf P(X_2{=}2) = \mathsf P({\rm HH}) = 1/4$$

We can see that the number of (equally-probable) permutations that give the same result is important when evaluating probability mass of the random variable.   Probability is only a simple ratio of counts of distinct outcomes when every distinct outcome is equally likely.

$\{\textsf{No-Heads}, \textsf{One-Head}, \textsf{Three-Heads}\}$ are three distinct outcomes, but $\{TT, HT, TH, HH\}$ are four equally likely distinct outcomes.   That is important!

We count these permutations as: "ways to select places for 'heads' in the arrangement".   Hence the use of the "combination" notation in the binomial distribution's probability measure.   (PS: ${^n{\rm C}_k}$ is also called the binomial coefficient, hence why these distributions are so named.)

Then if $X_n$ is the count of heads in $n$ tosses, we have:

$$\mathsf P(X_n {=} k) = \dfrac{^n{\rm C}_k}{2^n}$$

That is all.

We use ${^{10}}{\rm C}_3$ to count ways to select a combination of $3$ distinct items out of $10$.   These items happen to be the position we place the 'heads', rather than the coins themselves.   That is why we use the "combination" notation to count permutations of the arrangement.

(Yes, it is confusing.   Take some time to wrap your brain around it.)

Another way to see it, we are counting permutations of an arrangement of $3$ heads and $7$ tails.   There are $10!$ permutations of ten distinct objects, but these are not all distinct.

Every arrangement is one of a group of $3!$ which are identical except that different heads are in the same position; but heads are not distinct so these $10!/3!$ groups are each of $3!$ indistinguishable arrangements (wrt the heads).   We can likewise group by the tails.   Thus there are $10!/3!7!$ completely distinct ways to arrange the coins.   This is ${^{10}}{\rm C}_3$, aka: the count of distinct ways to select positions for the three heads in the arrangement.

Here is a different way of deriving the binomial coefficient formula (from Wilf's generatingfunctionology):

For each nonnegative integer $n$ and integer $k$ with $0\leqslant k\leqslant n$, suppose $f(n,k)$ is the number of $k$-element subsets of $\{1,2,\ldots, n\}$. Since each such subset of $\{1,2,\ldots, n\}$ either contains $n$ or does not, we have the recurrence $$f(n,k) = f(n-1,k) + f(n-1,k-1)$$ for $n\geqslant 1$, with $f(n,0)=1$ for $n\geqslant 0$. For each $n$, define the generating function $$B_n(x) = \sum_{k=0}^n f(n,k)x^k.$$ Multiplying each side of the recurrence by $x^k$ and summing over $k\geqslant 1$ we get $$\sum_{k=1}^n f(n,k)x^k = \sum_{k=1}^n f(n-1,k)x^k + \sum_{k=1}^n f(n-1, k-1)x^k,$$ and hence $$B_n(x) = 1 = B_{n-1}(x) - 1 + xB_{n-1}(x),$$ so that $$B_n(x) = (1+x)B_{n-1}(x)$$ for $n\geqslant 1$. Since $B_n(x)=f(0,0)=1$, it follows that $$B_n(x) = (1+x)^n, \; n\geqslant0.$$ Since $B_n$ is a polynomial, it is equal to its Taylor expansion: $$B_n(x) = \sum_{k=0}^n \frac{B^{(k)}_n(0)}{k!}x^k.$$ It is clear that $$B^{(k)}(x) = (n)_k (1+x)^{n-k},$$ where $$(n)_k = \prod_{j=0}^{k-1}(n-j) = \frac{n!}{(n-k)!}.$$ Therefore $B^{(k)}(0)=(n)_k$, so that the coefficient of $x^k$ in the Taylor expansion is $$\frac{(n)_k}{k!} = \frac{n!}{k!(n-k)!}.$$ This is the familiar expression for $\binom nk$, and so $$(1+x)^n = \sum_{k=0}^n \binom nk x^k.$$

• This looks really cool. Unfortunately I've not progressed through my Calc II class just yet so I'll need to come back after I've learned about Taylor Series. – Richard Stein Jan 29 '16 at 4:30