How does the binomial coefficient relate to the combinations formula?

Question

I have been having some problems reconciling the definition of "combinations" with the binomial coefficient. The definition goes something like: combinations compute the number of ways in which k objects can be chosen from of n objects, where the order in which the objects are arranged doesn't matter. But isn't it true that for every binomial experiment the order does matter?

For instance, if I'm flipping a coin three times and I want to find out the probability that it lands on head exactly once, I first calculate the binomial coefficient, which is given by (3 choose 1), i.e., the combinations formula, which gives me 3 possibilities in which head is chosen once (HTT), (THT) and (TTH).

Now what I don't understand is why these 3 possibilities aren't considered as a single combination? After all, they are all the same objects but just arranged in a different order, right? But combinations apparently disregard order, so now I'm confused.

I realise that using this logic every binomial coefficient in every binomial experiment would be 1, which is obviously bollocks. I just want to know where I'm lacking understanding in terms of how the combinations definition actually makes sense in the context of the binomial coefficient

Answer 1

The crux of your question seems to be the idea that order matters to a "binomial experiment".

In cases where the order of outcomes matters, permutations are probably what you are interested in - the order of heads and tails is fully captured in the $2^3$ permutations of coin flip outcomes.

But if you are only asking the likelihood of 1 head after 3 flips, combinations is what you want. By definition, a combination ignores ordering in the permutations.

Think of $(x+y)^3$. By memorization you know this is $x^3 + 3x^2y + 3 xy^2 + y^3$. The second term $3x^2y$ is just like your coin situation - the "y" is the heads "H". Also it is $3 \choose 1$. But multiply this out by hand and don't group like terms. You will end up with $yxx$, $xyx$, and $xxy$ terms at various places in your expansion depending on how you do your expansion. Here, we clearly don't care which comes where and we group into the summarization $3x^2y$ without even thinking about it. That's what a combination does.

Answer 2

I will illustrate with examples.

$~(a+b)^2.~$

Tableau-1 - Computation by individual terms:

(a+b) : Factor 1
(a+b) : Factor 2

The product will have $~2^2~$ terms, since, with each factor, you can either use the first term or the second term. So, the result is:

$$(a \times a) + (a \times b) + (b \times a) + (b \times b).$$

This consolidates to three terms, because the terms
$(a\times b) + (b \times a),~$ become $~\displaystyle \binom{2}{1}\times (ab) = 2ab.$

The coefficient $~\displaystyle \binom{2}{1}~$ represents that to form the product $~(a \times b),~$ there are $~\displaystyle \binom{2}{1}~$ ways of selecting exactly one of the factors, and using the term $~[a]~$ from that factor, while using the term $~[b]~$ from the unselected factor.

---

$~(a+b)^7.~$

Tableau-2 - Computation by individual terms:

(a+b) : Factor 1
(a+b) : Factor 2
(a+b) : Factor 3
(a+b) : Factor 4
(a+b) : Factor 5
(a+b) : Factor 6
(a+b) : Factor 7

Similar to Tableau-1, the product will have $~2^7 = 128~$ terms.

Again, similar to Tableau-1, these $~128~$ terms will be consolidated into the $~8~$ terms represented by

$$a^7, ~a^6b, ~a^5b^2, ~a^4b^3, ~a^3b^4, ~a^2b^5, ~ab^6, ~b^7. \tag1 $$

For $~k \in \{0,1,2,\cdots,7\},~$ to compute the coefficient that is assigned to the term $~a^k b^{7-k}~$ in (1) above, you have to compute the number of ways of selecting the term $~[a]~$ from exactly $~k~$ of the $~7~$ factors. Then, you will select the term $~[b]~$ from the remaining $~(7-k)~$ factors.

The number of different ways of selecting which $~k~$ factors will contribute the $~[a]~$ term is $~\displaystyle \binom{7}{k}.~$

---

$~(a+b)^n ~: ~n \in \Bbb{Z_{\geq 2}}.~$

Tableau-3 - Computation by individual terms:

(a+b) : Factor 1
(a+b) : Factor 2
...
(a+b) : Factor n-1
(a+b) : Factor n

Similar to Tableau-2, the product will have $~2^n ~$ terms.

Again, similar to Tableau-2, these $~2^n~$ terms will be consolidated into the $~(n+1)~$ terms represented by

$$a^n, ~a^{n-1}b, ~a^{n-2}b^2, ~\cdots, ~a^2b^{n-2}, ~ab^{n-1}, ~b^n. \tag2 $$

For $~k \in \{0,1,2,\cdots,n\},~$ to compute the coefficient that is assigned to the term $~a^k b^{n-k}~$ in (2) above, you have to compute the number of ways of selecting the term $~[a]~$ from exactly $~k~$ of the $~n~$ factors. Then, you will select the term $~[b]~$ from the remaining $~(n-k)~$ factors.

The number of different ways of selecting which $~k~$ factors will contribute the $~[a]~$ term is $~\displaystyle \binom{n}{k}.~$

---

As a sanity check, based on the above analysis, you should have that

$$\sum_{k=0}^n \binom{n}{k} = 2^n.$$

One way of proving this is by first proving (algebraically) that for $~n \in \Bbb{Z^+},~$ and for $~k \in \{0,1,2,\cdots,n-1\},~$ you have that

$$\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}. \tag3 $$

After proving (3) algebraically, you can then prove by induction that the $~n$-th row of Pascal's Triangle is represented by

$$\binom{n}{0} ~~\binom{n}{1} ~~\cdots ~~\binom{n}{n-1} ~~\binom{n}{n}.$$

Here, I am construing the first row of Pascal's Triangle to be

1  1

The proof will be based on the algorithm used to construct Pascal's Triangle, that each number is the sum of the two numbers above it.

After having done this, and again considering the Pascal's Triangle algorithm, you can then use induction (again) to prove that the sum of the numbers in the $~n$-th row of Pascal's Triangle equals $~2^n.$

As an illustration of how you would use induction the second time, consider the following two rows of Pascal's Triangle:

  1    3    3    1
1    4    6    4    1
1   3+1  3+3  1+3   1

You can see that the sum of the terms in the 1 4 6 4 1 row, actually represents two times the sum of the terms in the 1 3 3 1 row.

Answer 3

Your Mistake

There is a missing link here. When we count the number of ways to land the head exactly once, we don't perform direct counting, we use a bijection. Consider the following mapping:

$$ \begin{aligned} HTT&\to1\\ THT&\to2\\ TTH&\to3 \end{aligned} $$

where each possibility is assigned an integer indicating the location of the head. Each possibility must have a unique integer, therefore, the number of distinct integers equal the number of possibilities. The integer is one of $1$, $2$, or $3$, i.e. we choose one integer from three possible integers $\{1,2,3\}$. Hence $\binom{3}{1}$.

An Advice

Whenever you have a doubt, try to paraphrase your logic in the form of

choose ... from ...

If you cannot do so, then there's a flaw in the logic. For example, you don't know where to choose $HTT$ from right? So there is a flaw in that logic.

Answer 4

I've been recently wondering about the same question and think I've figured out the relation between the binomial coefficient and the combinations formula.

In your example, the probability that a coin lands on heads exactly once after flipping it three times is $$~\displaystyle \binom{3}{1}* (\frac{1}{2})^3 = \frac{3}{8}$$

Here, the binomial coefficient $\binom{3}{1}$ corresponds to the number of ways to choose 1 head from three coin flips: $$HTT,THT,TTH$$

Clearly, these are three permutations which correspond to one combination. But if you view the binomial coefficient $\binom{3}{1}$ as the number of ways to choose one spot from three spots to put the $H$, you will see that it is actually three combinations. For example, the above three permutations of letters respectively correspond to these three combinations $$1,2,3$$ where the numbers represent the position of the $H$. So the $HTT,THT,TTH$ can be viewed as $1,2,3$ here which is $\binom{3}{1}=3$ combinations.

---

In short, I think the binomial coefficient here is actually representing permutations with repetitions conventionally, but is equivalent to/can be viewed as combinations in the case of binomial distribution (only has two states).

Note that, $$\binom{3}{1}=\frac{3!}{{1!}{2!}}$$ is the combinations formula, which is the same formula for permutations with repetitions of two kinds of objects.