4.13 Combinations, Counting, and PermutationsHL ONLY

1. Multiplication Principle & Box Technique

Suppose that a specific Task A has 4 possible outcomes (a, b, c, d), and a subsequent Task B has 3 possible outcomes (1, 2, 3). The total outcomes for A and B combined can be mapped

The outcomes combine as follows

a1, b1, c1, d1
a2, b2, c2, d2
a3, b3, c3, d3

The total number of combinations is exactly 12. This scenario is represented using the BOX-TECHNIQUE:

= 12

In general: $m$ choices for A, $n$ choices for B $\implies m \times n$ choices altogether.

EXAMPLE 1

Two dice are tossed. How many distinct results are there?

Each die possesses exactly 6 outcomes. Using the box technique

6 6 $6 \times 6 = 36$ results altogether.

In this elementary example, it would be simple to write down all possible combinations. However, it is not always practical to count all outcomes manually.

EXAMPLE 2

The Latin alphabet contains 26 letters. How many distinct combinations of two letters exist if

a) Repetition of letters is allowed
There are 26 complete choices for each independent box.

26 26 $26 \times 26 = 676$ combinations altogether.

b) No repetition is allowed (i.e., strictly different letters)
There are 26 choices for the first box. Once we isolate the first letter, there are exactly 25 remaining choices for the second box.

26 25 $26 \times 25 = 650$ combinations altogether.

2. Words of Letters

Consider an alphabet of strictly $n$ letters. Then,

Number of words of $r$ letters = $n^r$

Indeed, let us place $r$ boxes in a sequential row. There are $n$ independent choices for each box. Therefore, the total number of words evaluates to

n n n $\cdots$ n
($r$ times)
$$n \cdot n \cdot n \dots \cdot n = n^r$$

EXAMPLE 3

Find the total number of words with strictly 4 letters if our core alphabet is

a) the alphabet of the 26 Latin letters: $26^4 = \mathbf{456,976}$
b) only the specific letters A, B, C, D, E: $5^4 = \mathbf{625}$
c) the ten base digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9: $10^4 = \mathbf{10,000}$
d) only the digits 0, 1 (binary alphabet): $2^4 = \mathbf{16}$

EXAMPLE 4

A secure password has the explicit structural form XXYYY, where

X is one of the 26 Latin letters
Y is one of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

The total number of possible distinct passwords is derived via the box technique

26 26 10 10 10

$26 \times 26 \times 10 \times 10 \times 10 = 26^2 \times 10^3 = \mathbf{676,000}$

3. Factorial: $n!$

A crucial mathematical symbol is introduced to simplify permutation counting. We define:

$n! = 1 \cdot 2 \cdot 3 \dots n$

which is read exactly as "n factorial". For example,

$1! = 1$
$2! = 1 \cdot 2 = 2$
$3! = 1 \cdot 2 \cdot 3 = 6$
$4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24$
$5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$

We also agree that $0! = 1$.

Why mathematically?
The most straightforward algebraic proof relies on the recursive property of factorials $$n! = n \times (n - 1)!$$ If we rearrange this formula to solve for $(n - 1)!$, we get $$(n - 1)! = \frac{n!}{n}$$ By substituting $n = 1$ into this rearranged equation, the result naturally emerges $$(1 - 1)! = \frac{1!}{1}$$ $$0! = 1$$ Conceptually, a factorial counts the number of ways to arrange a set of objects. If you have zero objects, there is exactly one way to arrange them: doing nothing.

4. Rearrangements of $n$ Objects

Consider 5 separate objects, say A, B, C, D, E. How many distinct ways are there to arrange them in strict sequential order? We apply the box technique!

We possess 5 choices for the 1st box: A, B, C, D, or E.
Once isolated and completed, we inherently have 4 choices for the 2nd box, and so on.

5 4 3 2 1

There are $5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5!$ possible arrangements. In general,

$n$ objects can be seamlessly arranged in $n!$ ways

EXAMPLE 5

Three people, Alex, Bill, and Chris, must sit in three chairs positioned in a row.

There are precisely $3! = 6$ distinct ways for them to be arranged. Indeed, we can map them fully:

ABC ACB BAC BCA CAB CBA

5. Combinations and Permutations

Consider a pool of $n$ distinct objects. How many specific ways are there to select a subset of $r$ objects out of them? Two defining conceptual boundaries arise:

COMBINATIONS	PERMUTATIONS
We do not mind about the order	We mind about the order
(The $r$ objects are strictly seen as a group)	(AB is inherently different than BA)
${^{n}C_r}$	${^{n}P_r}$

The rigorous formulas executing these calculations are:

${^{n}C_r} = \dfrac{n!}{r!(n-r)!}$

${^{n}P_r} = \dfrac{n!}{(n-r)!}$

NOTICE: Key Properties of ${^{n}C_r}$

${^{n}C_1} = n$
($n$ ways to choose 1 out of $n$)
${^{n}C_n} = 1$
(1 way to choose all $n$)
${^{n}C_0} = 1$
(1 way to choose nothing!)
${^{n}C_2} = \dfrac{n(n-1)}{2}$
(Derived algebraically)

EXAMPLE 6

Consider $n=5$ discrete objects, A, B, C, D, E. We select $r=2$ out of them.

Combinations (${^{5}C_2}$)
There are exactly 10 possible combinations:
AB, AC, AD, AE, BC, BD, BE, CD, CE, DE
Using the formula:
${^{5}C_2} = \dfrac{5!}{2!3!} = \mathbf{10}$

Permutations (${^{5}P_2}$)
There are precisely 20 possible permutations (order matters):
AB, BA, AC, CA, AD, DA, AE, EA, BC, CB, BD, DB, BE, EB, CD, DC, CE, EC, DE, ED
Using the formula:
${^{5}P_2} = \dfrac{5!}{3!} = \mathbf{20}$

EXAMPLE 7

There are 10 people existing in a room. We choose 3 people out of them.

a) If we consider the 3 people as a unified group (there is no internal order):
We strictly require Combinations. There are ${^{10}C_3} = \mathbf{120}$ possible distinct ways.

b) If we intentionally arrange the 3 specific people in absolute sequential order:
We require Permutations. There are ${^{10}P_3} = \mathbf{720}$ possible ways.
(Note: We can evaluate this using the Box technique: 10 × 9 × 8 = 720).

EXAMPLE 8 (LOTTO)

We choose 6 distinct numbers out of an initial pool of 49. Because the draw sequence is irrelevant, we process combinations. The numerical total of possible combinations is:

${^{49}C_6} = \dfrac{49!}{6!43!} = \dfrac{44 \cdot 45 \cdot 46 \cdot 47 \cdot 48 \cdot 49}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6} = \mathbf{13,983,816}$

This implies that if we submit a single ticket of 6 numbers, the raw probability to win is 1 out of 13,983,816 (almost exactly 1 out of 14 million!).

EXAMPLE 9

There are 26 standard Latin letters (A, B, C, $\dots$, Z). When we construct structural words of exactly 3 letters, the operational order of letters dominates, thus we process permutations.
However, it is generally safer and more logical to utilize the Box-technique instead of the permutation formula ${^{n}P_r}$. The total number of all 3-letter words equates to $26^3 = 17,576$.

a) How many consist of distinct letters?
Box model: 26 × 25 × 24 $\implies 26 \times 25 \times 24 = \mathbf{15,600}$ words.

b) How many begin with the letter A?
Box model: 1 (reserved) × 26 × 26 $\implies 1 \times 26^2 = \mathbf{676}$ words.

c) How many do NOT begin with A?
Box model: 25 × 26 × 26 $\implies 25 \times 26^2 = \mathbf{16,900}$ words.

d) How many do NOT contain the letter F?
Box model: 25 × 25 × 25 $\implies 25^3 = \mathbf{15,625}$ words.

e) How many contain at least one F?
Method A: We map the permutations exactly (x represents any letter except F):

Fxx	1 × 25 × 25	$= 625$
xFx	25 × 1 × 25	$= 625$
xxF	25 × 25 × 1	$= 625$
FFx	1 × 1 × 25	$= 25$
FxF	1 × 25 × 1	$= 25$
xFF	25 × 1 × 1	$= 25$
FFF	1 × 1 × 1	$= 1$

Totally: $625 + 625 + 625 + 25 + 25 + 25 + 1 = \mathbf{1,951}$ words.

Method B: It is more convenient to evaluate the opposite conditions and exclude them from the universal.
(Total Words) − (Words Without F) = $17,576 - 15,625 = \mathbf{1,951}$ words.

EXAMPLE 10

A school class contains 10 boys and 20 girls. We select an internal committee of exactly 5 students. Clearly, the total number of all possible committees is ${^{30}C_5}$. Find the number of distinct ways to map a committee if

a) The committee consists of exactly 2 boys and 3 girls:
${^{10}C_2} \times {^{20}C_3}$ ways

b) The committee consists of boys only:
${^{10}C_5} \times {^{20}C_0} = \mathbf{{^{10}C_5}}$ ways

c) The committee consists of students of the same gender:
There are two independent cases: only boys OR only girls. Because these are mutually exclusive, we add the outputs
$\mathbf{{^{10}C_5} + {^{20}C_5}}$ ways

d) There are at most two boys in the committee
There are three cases: the commitee contains exactly 0, 1, or 2 boys (meaning 5, 4, or 3 girls respectively). We sum the parallel tracks
$\mathbf{{^{10}C_0}{^{20}C_5} + {^{10}C_1}{^{20}C_4} + {^{10}C_2}{^{20}C_3}}$

6. Probability and Counting

The fundamental probability formula $$ P(A) = \dfrac{n(A)}{\text{TOTAL}} $$ appears highly naïve. However, evaluating both $n(A)$ and the universal TOTAL is often non-trivial. It requires the rigorous counting combinatorics established above.
The number of distinct ways a scenario can occur translates into a probability when divided by the total possible outcomes.

EXAMPLE 11 (Compare with EXAMPLE 9)

Evaluate the probability that a randomly generated word of exactly 3 letters

a) Consists of different letters:
$P(\text{different letters}) = \dfrac{(26)(25)(24)}{26^3} = \mathbf{\dfrac{150}{169}}$

b) Begins with A:
$P(\text{begins with A}) = \dfrac{1 \cdot 26^2}{26^3} = \mathbf{\dfrac{1}{26}}$

c) Does NOT begin with A:
$P(\text{does not begin with A}) = \dfrac{25 \cdot 26^2}{26^3} = \mathbf{\dfrac{25}{26}}$

d) Does NOT contain the letter F:
$P(\text{does not contain the letter F}) = \mathbf{\dfrac{25^3}{26^3}}$

e) Contains at least one F:
$P(\text{contains the letter F}) = \mathbf{1 - \dfrac{25^3}{26^3}}$

EXAMPLE 12 (Compare with EXAMPLE 10)

A school class contains 10 boys and 20 girls. Evaluate the probability that a randomly selected committee of 5 students

a) Consists of exactly 2 boys and 3 girls:
$P(\text{2 boys and 3 girls}) = \dfrac{{^{10}C_2} \cdot {^{20}C_3}}{{^{30}C_5}}$

b) Consists of boys only:
$P(\text{boys only}) = \dfrac{{^{10}C_5} \cdot {^{20}C_0}}{{^{30}C_5}} = \dfrac{{^{10}C_5}}{{^{30}C_5}}$

c) Consists of students of the same gender:
$P(\text{same gender}) = \dfrac{{^{10}C_5} + {^{20}C_5}}{{^{30}C_5}}$

d) Contains at most two boys:
$P(\text{at most two boys}) = \dfrac{{^{10}C_0}{^{20}C_5} + {^{10}C_1}{^{20}C_4} + {^{10}C_2}{^{20}C_3}}{{^{30}C_5}}$