Counting Principles, Permutations, and Combinations

Scope Label

Core 9758. This note covers the basic language and formulas needed before handling harder restrictions or special arrangements.

Use it with the hub Permutations and Combinations.

The First Decision: Add or Multiply

The addition and multiplication principles are the foundation of counting.

Use the addition principle when the outcome can occur in one of several separate cases.

If there are $m$ ways for case A and $n$ ways for case B, and the cases do not overlap, then there are

m + n

ways in total.

The cases must be mutually exclusive. If sets $A$ and $B$ overlap, either rewrite them as disjoint cases or use

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.

The overlap is subtracted once because it was included once in each separate count.

Use the multiplication principle when the outcome is built through successive stages.

If stage 1 can be done in $m$ ways and, after every stage-1 choice, stage 2 can be done in $n$ ways, then there are

mn

ways in total.

If the number of stage-2 choices depends on the first choice, use a branch count instead: multiply along each branch, then add the mutually exclusive branch totals. The multiplication principle is about building one outcome through stages; it is not an assumption of probabilistic independence.

How to read this figure. The left panel assumes the cases do not overlap; otherwise subtract the repeated overlap or split into disjoint cases. The right panel builds one outcome by completing every stage, so the stage counts multiply.

Example: Cases versus stages

A student chooses either one of 4 sandwiches or one of 3 drinks. If exactly one item is chosen, the number of choices is

4 + 3 = 7.

If the student chooses one sandwich and one drink, the number of choices is

4 \times 3 = 12.

The numbers are similar, but the structure is different.

Factorial Notation

Factorial notation appears when distinct objects are arranged in order.

For a positive integer $n$ ,

n! = n (n - 1) (n - 2) \dots 2 \cdot 1.

For example,

5! = 5 \times 4 \times 3 \times 2 \times 1 = 120.

The convention

0! = 1

is important. There is one way to make no choice or arrange no remaining objects.

Here $n$ is a non-negative integer. The formulas below use integers $n, r$ with $0 \leq r \leq n$ unless stated otherwise.

Arranging All Distinct Objects

If $n$ distinct objects are arranged in a row, the number of arrangements is

n! .

Reason:

$n$ choices for the first position
$n - 1$ choices for the second position
$n - 2$ choices for the third position
continuing until 1 choice remains

Therefore,

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

Permutations: Arranging Some Objects

A permutation counts an ordered arrangement.

The number of ways to arrange $r$ objects chosen from $n$ distinct objects, without replacement, is

^{n} P_{r} = n (n - 1) (n - 2) \dots (n - r + 1) .

In factorial form,

^{n} P_{r} = \frac{n !}{( n - r )!} .

Use $^{n} P_{r}$ when:

$r$ objects are chosen from $n$
the chosen objects are placed in ordered positions
changing the order gives a different outcome

Ordered Sequences with Repetition Allowed

If an ordered sequence has $r$ positions and every position has all $n$ symbols available, including symbols used earlier, the multiplication principle gives

r factors n \times n \times \dots \times n = n^{r} .

For this repeated-choice formula, $n \geq 1$ and $r \geq 0$ are integers. There is no requirement that $r \leq n$ , because a symbol may be used again. When $r = 0$ , the one empty sequence agrees with $n^{0} = 1$ .

For example, a four-character code made from seven letters, with repetition allowed, has $7^{4}$ possibilities. Without repetition it has $^{7} P_{4}$ possibilities.

Repeated choices versus identical objects

“Repetition allowed” means a choice may be made again. “Identical objects” means a fixed collection already contains indistinguishable copies. The first usually gives repeated multiplication; the second usually requires division for invisible swaps.

Example: Ordered positions

There are 8 students and 3 different roles: chairperson, secretary, and treasurer.

The number of ways is

^{8} P_{3} = 8 \times 7 \times 6 = 336.

Order matters because the roles are different.

Combinations: Selecting Objects

A combination counts an unordered selection.

The number of ways to choose $r$ objects from $n$ distinct objects, without replacement, is

^{n} C_{r} = \frac{n !}{r ! ( n - r )!} .

Use $^{n} C_{r}$ when:

$r$ objects are chosen from $n$
the order of the chosen objects does not matter
the selected group has no internal roles or ranking

Example: Committee selection

There are 8 students and 3 are chosen for a committee.

The number of committees is

^{8} C_{3} = \frac{8 !}{3 ! 5 !} = 56.

The group ${A, B, C}$ is the same committee as ${C, B, A}$ .

How to read this figure. It holds the selected set fixed. Its six orders are six ordered outcomes but collapse to one unordered outcome when internal order is not part of the result.

Relationship Between $^{n} P_{r}$ and $^{n} C_{r}$

The relationship is

^{n} P_{r} =^{n} C_{r} r! .

This says:

choose the $r$ objects
arrange the $r$ chosen objects

^{n} C_{r} = \frac{^{n} P _{r}}{r !} .

The division by $r!$ removes the internal order of the selected objects.

This is often the most useful way to understand combinations. A combination is not a new kind of magic formula; it is a permutation after internal order has been ignored.

This also provides a check: if you first choose $r$ objects and then assign them to $r$ ordered positions, your product $^{n} C_{r} r!$ should equal $^{n} P_{r}$ .

How to read this figure. Every ordered $r$ -tuple can be produced uniquely by first selecting its $r$ objects and then ordering that selected set. Because neither stage repeats or omits an ordered outcome, the stage counts multiply.

Useful Combination Identities

Symmetry

^{n} C_{r} =^{n} C_{n - r} .

Choosing $r$ objects to include is equivalent to choosing $n - r$ objects to exclude.

For example,

^{10} C_{3} =^{10} C_{7} .

Edge cases

^{n} C_{0} = 1,^{n} C_{n} = 1.

There is one way to choose nothing, and one way to choose everything.

Pascal’s identity

For $1 \leq r \leq n - 1$ ,

^{n} C_{r} =^{n - 1} C_{r} +^{n - 1} C_{r - 1} .

Fix one particular object. A selection of $r$ objects either excludes it, giving $^{n - 1} C_{r}$ choices, or includes it, leaving $^{n - 1} C_{r - 1}$ choices for the remaining places. These two cases are disjoint and exhaustive.

Grouping Problems

Grouping problems require special care because groups may be labelled or unlabelled.

Labelled groups

If 6 students are split into a Red team of 3 and a Blue team of 3, the teams are labelled.

Choose the Red team:

^{6} C_{3} .

The remaining students automatically form the Blue team.

More generally, splitting $n$ distinct people into labelled groups of sizes $n_{1}, \dots, n_{k}$ , where $n_{1} + \dots + n_{k} = n$ , gives

\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !} .

The group labels make exchanging whole groups a genuine new allocation.

Unlabelled groups

If 6 students are split into two unlabelled groups of 3, then temporarily calling the groups “group A” and “group B” overcounts by $2!$ .

The number of ways is

\frac{^{6} C _{3}}{2 !} .

The division removes the artificial swap of the two whole groups.

For $m$ unlabelled groups of the same size and role, divide by a further $m!$ because permuting those whole groups changes nothing. Thus six people split into three unlabelled pairs can be counted as

\frac{6 !}{( 2 ! ) ^{3} 3 !} = 15.

Do not divide for groups that are distinguished by labels or by unequal sizes. If several classes of interchangeable groups occur, divide by the factorial for each class of identical whole groups.

How to read this figure. Labelling equal-sized groups makes swapping whole groups observable. If the groups are unlabelled, those whole-group permutations are repeated descriptions of the same allocation and must be divided out.

Core Worked Examples

Example 1: Arranging letters without repetition

How many 4-letter codes can be formed from 7 distinct letters without repetition?

The positions are ordered, so use permutations:

^{7} P_{4} = 7 \times 6 \times 5 \times 4 = 840.

Example 2: Choosing a team

How many teams of 4 can be chosen from 9 students?

The team has no internal order, so use combinations:

^{9} C_{4} = 126.

Example 3: Choose then assign roles

From 9 students, choose 4 students for a team, then appoint one of the chosen students as captain.

One method is:

^{9} C_{4} \times 4.

Another method is:

9 \times^{8} C_{3} .

Both count the same thing: choose the captain, then choose the other 3 team members.

Common Pitfalls

Treating every selection problem as an arrangement problem.
Forgetting that different roles make order matter.
Dividing by $r!$ when the order is actually meaningful.
Using addition when stages should be multiplied.
Using multiplication when cases overlap.
Forgetting that cases must be mutually exclusive before adding.

Singapore H2 Math Wiki

Start Here

Counting Principles, Permutations, and Combinations

Counting Principles, Permutations, and Combinations

Scope Label