Mathematics · Combinatorics, probability and statistics · Grade 7

Combinatorics: counting rules

3 shirts and 2 pairs of trousers — how many different outfits? In how many orders can 6 people stand in a line?

The situation

In the morning there are 3 shirts and 2 pairs of trousers in the wardrobe — how many different outfits are possible? If a phone password has 4 digits, how many options must be tried? In how many different orders can the 6 duty students of a class be lined up? These are all counting problems. Instead of writing the options out one by one, we draw a tree, make a table and discover two simple rules.

Topic

Combinatorics: the addition and multiplication rules, permutations, ways of choosing. Choosing clothes, a phone passcode and class monitors: the tree of options, the multiplication rule, the n! permutations

Key ideas

Tree of options
Multiplication rule
Permutations

Formulas

N = n_{1} \cdot n_{2} \cdot \dots \cdot n_{k}

Multiplication rule: if a choice consists of $k$ stages linked one after another by and, the numbers of options are multiplied.

N = n_{1} + n_{2}

Addition rule: the first or the second way — the options of groups that cannot occur together are added.

P_{n} = n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n

The number of ways to arrange $n$ different things in a line is the number of permutations; $n!$ is “ $n$ factorial”.

n^{k} and n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)

Sequences of $k$ places from $n$ symbols: with repetition $n^{k}$ , without repetition — each next place has one option fewer.

Theory

Tree of options and the multiplication rule

When a choice is made step by step, we draw it as a tree: from each shirt there are as many branches as there are pairs of trousers. The number of leaves is the product of the numbers of branches: 3 shirts and 2 pairs of trousers give $3 \cdot 2 = 6$ outfits. Add shoes and there is one more layer of branches: $3 \cdot 2 \cdot 2 = 12$ . This is the multiplication rule: if it is “the first choice and the second choice”, the numbers of options are multiplied. In the first step, grow the tree yourself.

Addition rule: “or”

From Tashkent to Samarkand you can go by 3 trains or 2 buses — $3 + 2 = 5$ ways in all. If the groups cannot occur together (you cannot take a train and a bus at the same time), the options are added. If there are then 2 ways from Samarkand to Bukhara, the Tashkent → Bukhara routes number $(3 + 2) \cdot 2 = 10$ — first “or”, then “and”. The second method is a table: the rows are the first choice, the columns the second, and the number of cells is the answer.

Permutations: n!

We put 3 books on a shelf. For place 1, any book — 3 options; for place 2, one of the remaining two — 2 options; only one is left for the last: $3 \cdot 2 \cdot 1 = 6$ . In general, for $n$ things $n \cdot (n - 1) \cdot \dots \cdot 1 = n!$ (“ $n$ factorial”). For example $4! = 24$ , $5! = 120$ — the factorial grows very fast. In the third step all the arrangements are grouped by the first book: each group has $(n - 1)!$ arrangements, and there are $n$ groups.

The method of choosing (an ordered list)

A small problem can be solved with a systematic list: the two-digit numbers from the digits 1, 2, 3 — first those starting with 1 (11, 12, 13), then with 2, then with 3: $3 \cdot 3 = 9$ numbers. If the digits must not repeat, 11, 22 and 33 drop out: $3 \cdot 2 = 6$ — one digit fewer is left for the second place. If the list is ordered, nothing is forgotten and nothing is counted twice — check it in the fourth step.

Types of problems

Every counting problem raises two questions: does order matter (are 12 and 21 different?) and can things repeat (can one thing be taken twice?). Order matters, repetition allowed — a PIN code: $10^{4}$ . Order matters, no repetition — the places of the prize-winners: $8 \cdot 7 \cdot 6$ . Order does not matter, no repetition — choosing two representatives: $\frac{8 \cdot 7}{2} = 28$ (each pair is counted twice). Order does not matter, repetition allowed — ice-cream scoops: counted with a list. In the fifth step, sort the problem into its type.

About the model

The drawings use small numbers: up to 36 leaves on the tree, up to 5 books on the shelf (only some of the 120 arrangements are drawn), up to 64 numbers in the list — but the rules work for any number. The number of combinations $C_{n}^{k}$ and the binomial theorem are studied in Grade 11; here the problems where order does not matter are solved only with a list and the argument “each pair is counted twice”.

Did you know?

The number of ways to shuffle a pack of 52 cards is $52! \approx 8 \cdot 10^{67}$ — more than the number of stars in the universe; probably every shuffle gives a new order.
The sign “ $n!$ ” was introduced in 1808 by the French mathematician Christian Kramp; before that the factorial was written as a long product.

Inside the experiment

The topic is explained step by step with animation, from simple to advanced: from a real-life picture to the formula and the proof. Then you drag the points yourself to check. Inside are missions, a quiz and a guided tour.

More experiments in this section

Statistics: mean, median, σ — Grade 8
Probability: coin, die, Venn — Grade 9