Understanding permutations and combinations in a coin toss experiment

[Kakashi]

Consider a coin that is tossed n times, where heads occurs with probability p and tails with probability 1−p.


The sample space consists of all possible outcomes of the experiment. At the first stage there are two possible results H or T. For each possible result at the first stage there are 2 possible results at the second stage, and so on. Therefore, after n tosses the sample space contains 2^{n} possible outcomes.

I would like to clarify the meaning of permutations and combinations in this context.

Is a permutation picking one of the possible outcomes at the nth stage and then finding the number of different sequences we can form by rearranging the objects that make it?

For example, we want to determine the number of distinct sequences we can form from a nth element containing exactly k heads by rearranging the k-heads. If we temporarily label the heads, then the first head can be placed in n different positions, the second head in n−1 positions, and so on, until the k-th head can be placed in n−k+1 positions. This gives

$$ n(n-1)(n-2)..(n-k+1)=\frac{n!}{(n-k)!} $$ possible placements.

However, this overcounts the number of distinct sequences, because the heads are indistinguishable. For example, swapping the “first” and “second” head while keeping all positions fixed produces the same sequence. In fact, each distinct sequence has been counted k! times. Therefore, we divide by k! and the number of distinct sequences with k heads is $$\frac{n!}{(n-k)!k!} $$

Combinations are defined as the number of k-element subsets of a given n-element set. Using the same idea, we can form subsets by choosing elements one at a time: there are n choices for the first element of the subset, n−1 choices for the second element, and so on, until k elements are chosen. This gives

$$ n(n-1)(n-2)..(n-k+1)=\frac{n!}{(n-k)!} $$

possible selections, but since the order of elements in a subset does not matter, many of these selections represent the same subset. Therefore, we divide by k, which yield $$\frac{n!}{(n-k)!k!} $$

 

[PeroK]

When we talk about permutations and combinations, it's important to establish whether the elements are distinguishable or not. Let's take the case where things are distinguishable. A good example is people. If we have $n$ people and we want to choose a team of $k$ people, then the next question is whether the team is ordered in some way.

If the team is not ordered, so it's just $k$ people, then this is a combination. The number of possible teams is:$$C = \binom n k = \frac{n!}{(n-k)!k!}$$Example: if we have three people (A, B, C) and we want to pick a team of two of them, then we have three combinations:

AB, AC and BC

(To be precise AB is the same team as BA etc.)

If the team is ordered (there might be two different positions on the team) then this is a permutation. The number of possible teams is greater and is given by: $$P = \frac{n!}{(n-k)!}$$In our example, the possible teams are:

AB, BA, AC, CA, BC and CB

In your scenario, you have a sequence of indistinguishable heads and tails. In this case, the terminology of permutations and combinations doesn't really apply. Let's assume we toss a coin $n$ times.

If the order doesn't matter, then you have $n+1$ outcomes. These can be identified by the number of heads ($k$ ranging from $0$ to $n$). Or, by the number of tails, if you prefer.

If the order does matter and you want to count the number of possible sequences of $k$ heads and $n-k$ tails, then it's the same as the combination formula:
$$S = \binom n k = \frac{n!}{(n-k)!k!}$$My advice is to be careful not to rely too heavily on words like permutation and combination. Instead, you need to look at each scenario and determine whether the things you have are indistinguishable and whether the order you choose things or arrange things matters.

Combinatiorics is a subject where it's diffilcult to get by memorising formulas!

Hope this helps.

 

[PeroK]

PS to expand on the case of $n$ coin tosses. This is a binomial distribution with probability $p$. The probablity of each outcome ($k$ heads) is:
$$P_k = \binom n k p^k(1-p)^{n-k}$$Note that the sum of all these probabilities must be 1:
$$\sum_{k = 0}^nP_k = \sum_{k = 0}^n \binom n k p^k(1-p)^{n-k} = 1$$This must hold for all $p$, which we see from an understanding of probability theory. You might like to confirm that purely algebraically.

 

[FactChecker]

In a two-toss experiment, if (H, T) is considered different from (T, H), you are counting permutations. If they are considered the same, you are counting combinations.
For permutations, there are 4 distinct outcomes: (H, H), (H, T), (T, H), (T, T).
For combinations, there are 3 distinct outcomes: 2 Tails, 0 Heads; 1 Tail, 1 Head; 0 Tails, 2 Heads.

 

[PeroK]

In a two-toss experiment, if (H, T) is considered different from (T, H), you are counting permutations. If they are considered the same, you are counting combinations.
For permutations, there are 4 distinct outcomes: (H, H), (H, T), (T, H), (T, T).
For combinations, there are 3 distinct outcomes: 2 Tails, 0 Heads; 1 Tail, 1 Head; 0 Tails, 2 Heads.

That's $2^n$ permutations and $n+1$ combinations. You then have to be clear that the forumlas for permutations and combinations don't apply.

 

[Hill]

the meaning of permutations and combinations

A permutation on a set $S$ is a bijection $S\to S$.
A combination is a subset of $S$.

 

[haruspex]

Enumeration problems do not, in general, fall neatly into just the two categories. See https://en.wikipedia.org/wiki/Twelvefold_way.