Counting (HL)

Does calling it “counting” make it more or less intimidating than “combinatorics”?

Principles
Definitions
Strategies / Techniques
Connections to probability
Extensions (beyond HL)

Principles

Multiply when

the choices are independent (ie does not impact each other), OR
the choices are dependent but the number of choices remain the same, OR
the choices are known, because all previous choices are known (such as when working through a case)

Add when finding the total from separate cases.

In probability, multiplication translates to independent events and conditional events, while addition translates to mutually exclusive events.

Definitions

Distinct means different. For example, the 5 green balls in a bag are not distinct from each other, but are distinct from the 3 red balls. People are distinct. Different locations are distinct. Items are not distinct (ie identical) when we just care about the quantity.

Factorial is the number of ways to arrange $n$ distinct items in a line.

n! = n(n-1)(n-2) ... (2)(1)

They are multiplied because the number of choices at each position is a constant, ie the second position always has $n-1$ choices, even if they are not always the same choices.

Factorials are defined for $n\in\mathbb N$ . $0!=1! = 1$ .

Rearrangement with repetition means we divide by by $r!$ for each group of $r$ identical items.

Example: Find the number of ways to rearrange all letters of the word “MISSISSIPPI”.

The word has $1M, 4I, 4S, 2P$

N = \frac{11!}{1!4!4!2!} = 34650 \qed

Note that when all items only appear once, this simplifies to the factorial.

Permutation is the number of ways to arrange $r$ items in a line from $n$ distinct options

^n\text{P}_r = \frac{n!}{r!}

Combination is the number of ways to group $r$ items in from $n$ distinct options

^n\text{C}_r = \binom nr = \frac{n!}{r!(n-r)!}

Tip: For rearrangement, if each item goes to its own location, then it’s permutation; if multiple items go to the same location, then it’s combination.

Many combination questions involving probability, can also be solved with permutations. Eg questions involving poker hands where dealing one card at a time is same as dealing multiple cards at once.

See binomial theorem for properties of the binomial coefficient.

Hypergeometric distribution is a fancy term for making two groups from two sets of distinct options, one from each set.

m\text{ of } M\text{ and }n \text{ of } N = \binom Mm \binom Nn

Example: There are 4 boys and 5 girls. What is the probability that a random group of 6 includes exactly 3 boys and 3 girls?

\frac{^4\text{C}_3\cdot {^5\text{C}_3}}{^9\text{C}_6} = \frac{10}{21} \qed

Example: Given that $360 = 2^{\color{purple}3} \cdot 3^{\color{blue}2} \cdot 5^{\color{darkgreen}1}$ , how many factors does $360$ have?

Each factor is one times $0$ to ${\color{purple}3}$ twos, times $0$ to ${\color{blue}2}$ threes, times $0$ to ${\color{darkgreen}1}$ five.

{\color{purple}4}\cdot {\color{blue}3} \cdot {\color{darkgreen}2} = 24 \qed

Note: There are $n - m + 1$ integers from $m$ to $n$ .

Example: A particular IB school does not offer an Arts course, so a Diploma candidate must take 6 classes from 5 Groups. Here are the courses offered:

Group 1	Group 2	Group 3	Group 4	Group 5
English A	French B	History	Biology	AA
	Spanish B	Psychology	Chemistry	AI
			Physics

In addition, the student can only take one maths course. All courses are offered at both SL and HL. How many ways can the student choose a six-subject course combination, if

a) we ignore SLs vs HLs?

b) each student must take 3 or 4 HLs and the rest SLs?

a) The strategy is to list all possible cases, find out how many ways for each case, then add them up. Note that there is only one choice for Group 1.

G2	G3	G4	G5	# Ways
$2$ of $2$	$1$ of $2$	$1$ of $3$	$1$ of $2$	$^2\text{C}_2 \times 2 \times 3 \times 2 = 12$
$1$ of $2$	$2$ of $2$	$1$ of $3$	$1$ of $2$	$2 \times {^2\text{C}_2} \times 3 \times 2 = 12$
$1$ of $2$	$1$ of $2$	$2$ of $3$	$1$ of $2$	$2 \times 2 \times {^3\text{C}_2} \times 2 = 24$

These were multiplied because within each case each group does not affect another. Finally we add the separate cases to get $12 + 12 + 24 = 48$ combos. $\qed$

b) In this school, choices of SLs vs HLs don’t restrict course selection. For each combo above, there are are $^6\text{C}_3$ ways to take 3 HLs + 3 SLs, and $^6\text{C}_4$ ways to take 4 HLs + 2 SLs. These are the two cases per combo.

48 \times \left({^6\text{C}_3} + {^6\text{C}_4}\right) = 1680 \qed

Note that in practice, not all subjects will be offered in both SL and HL, so that will greatly limit the number of options.

Strategies / Techniques

If several items must be next to each other, consider number of ways to rearrange items inside the group, multiplied by numbers of ways to permute the group with other items outside.

Example: A coupon code has five numbers $1, 2, 3, 4, 5$ and five letters $A, B, C, D, E$ in some order. Each character is used exactly once. Find the number of coupons where there are exactly three letters appearing consecutively.

Consider the cases of

i) three letters next to a number at the beginning/end, and ii) three letters in the middle of the code, such as 1ABC2.

For the first case, we form a group of three letters one number, with $\displaystyle {^5\text{P}_3}{^5\text{P}_1} = 300$ ways to permute within the group.

The group is fixed to the start or end. The remaining six characters can freely be permuted $6!$ ways. So we have $2 \cdot 300 \cdot 6!$ for the first case.

For the second case, we form a group of five characters, with $\displaystyle {^5\text{P}_3}{^5\text{P}_2} = 1200$ ways to permute within the group.

This group can be permuted with the remaining five characters in $1200 \cdot 6!$ ways.

Different cases are to be added.
$2 \cdot 300 \cdot 6! + 1200 \cdot 6! = 1296000 \qed$
Indirect method - Look for signalling words such as “at least”.
Inclusion-exclusion principle.

Example: A coupon code has five numbers $1, 2, 3, 4, 5$ and five letters $A, B, C, D, E$ in some order. Each character is used exactly once. Find the number of coupons where there are no three or more letters appearing consecutively.

It is easier to group items together than keeping them apart. So we’ll be using an inverse method.

A relatively simple $\displaystyle 10! - {^5\text{P}_3}\cdot8!$ , ie rearranging a group of $3$ letters with $7$ characters means we would subtract a group of $4$ letters twice, and a group of $5$ letters three times.

So we would need to add back a count of $4$ consecutive letters, and two counts of $5$ consecutive letters.

A $\displaystyle {^5\text{P}_4}\cdot7!$ (meaning a group of four letters with six other characters outside the group) would count a group of $4$ letters once, and a group of $5$ letters twice.

We need to count each occurrence once:
$10! - {^5\text{P}}_3\cdot8! + {^5\text{P}_4}\cdot7! = 1814400 \qed$
for a total of $1814400$ ways.
Where multiple approaches are possible, use the one with the least number of cases. If you could get it down to two cases it’s probably a good method. If you are looking at four cases, it’s probably excessive.
Consider the symmetry.

Example: $25$ equal-sized balls with letters A to Y, all different, are put in a bag. Then the balls are taken out in a random order, without putting any back. What is the probability that A is picked before B, while B is picked before C?

For any three positions that A, B, C will appear in, only $1$ out of $3! = 6$ ways has A before B before C. This is true regardless which three positions are used.

Therefore, the probability is $\frac16 \qed$

Connections to probability

operation	case(s)	counting	probability
$\times$	independent events	$n(A \cap B) = n(A)\cdot n(B)$	$\text{P}(A \cap B) = \text{P}(A)\cdot P(B)$
$\times$	conditional events	$n(A \cap B) = n(A) \cdot n(B \vert A)$	$\text{P}(A \cap B) = \text{P}(A) \cdot \text{P}(B \vert A)$
$+$	mutually exclusive events	$n(A \cup B) = n(A) + n(B)$	$\text{P}(A \cap B) = \text{P}(A) + \text{P}(B)$

The formulas are true only for the specified type of events in each row.

See Venn diagrams as a way to visualize the events, and thereby using Venn diagram formulas.

Extensions (beyond HL)

	distinct items	identical items
distinct bins	$b^n$ , $b$ bins $n$ items (part of HL)	multiset / stars and bars
identical bins	partitions of a set	partitions of an integer

Counting (HL)

Contents

Principles

Definitions

Strategies / Techniques

Connections to probability

Extensions (beyond HL)