4.13 Combinations, Counting, Permutations (for HL)

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 systematically:

The outcomes perfectly 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 powerfully 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 mathematically 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 dramatically 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 universally agree that $0! = 1$.
(It looks peculiar, I know! Please accept it!)

GDC usage: For Casio calculators, evaluate $x!$ by navigating to RUN mode $\to$ OPTN $\to$ PROB $\to$ $x!$

4. Rearrangements of $n$ Objects

Consider 5 separate objects, say A, B, C, D, E. How many mathematically 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 absolute general terms:

$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 mathematically 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$ sequentially 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 exactly 10 people existing in a room. We systematically 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 trivially evaluate this using the Box technique: 10 × 9 × 8 = 720).

EXAMPLE 8 (LOTTO)

We actively choose 6 distinct numbers out of an initial pool of 49. Because the draw sequence is irrelevant, we inherently 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 unequivocally 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 specifically consist of distinct (different) letters?
Box model: 26 × 25 × 24 $\implies 26 \times 25 \times 24 = \mathbf{15,600}$ words.

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

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

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

e) How many strictly contain the letter F (at least once)?
Method A (Analytical): 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 (Smart Way!): It is inherently more convenient to evaluate the absolute opposite conditions and exclude them from the universal matrix.
(Total Words) − (Words Without F) = $17,576 - 15,625 = \mathbf{1,951}$ words.

EXAMPLE 10

A school class objectively contains 30 students: 10 boys and 20 girls. We structurally select an internal committee of exactly 5 students. Clearly, the absolute total of all possible randomized 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 strictly boys only:
${^{10}C_5} \times {^{20}C_0} = \mathbf{{^{10}C_5}}$ ways

c) The committee logically consists of students of the exact same gender:
There are two independent boundaries: 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 mathematically at most two boys in the committee:
There are three sequential thresholds: 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}}$ initially appears highly naïve. However, accurately evaluating both $n(A)$ and the universal TOTAL is frequently non-trivial. It constantly requires the rigorous counting combinatorics established above.

Roughly speaking, the "number of distinct ways" mapping a scenario seamlessly maps into a definitive "probability" when mathematically divided by the absolute TOTAL ways.

EXAMPLE 11 (Compare strictly with EXAMPLE 9)

Evaluate the true 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 the letter F (at least once): $P(\text{contains the letter F}) = \mathbf{1 - \dfrac{25^3}{26^3}}$

EXAMPLE 12 (Compare strictly with EXAMPLE 10)

A school class objectively contains 30 students: 10 boys and 20 girls. Evaluate the pure probability that a randomly constructed 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 strictly 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 exact same gender:
$P(\text{same gender}) = \dfrac{{^{10}C_5} + {^{20}C_5}}{{^{30}C_5}}$

d) Contains mathematically 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}}$