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.

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

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

$$mn$$

ways in total.

Caption: Addition counts alternatives; multiplication counts successive stages.

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)\cdots 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.

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)\cdots 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)\cdots (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

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\}$.

Caption: The difference is not the objects chosen; it is whether their order is part of the outcome.

Relationship Between ${}^n{P}_r$ and ${}^n{C}_r$

The relationship is

$${}^n{P}_r={}^n{C}_{r}r!.$$

This says:

1. choose the $r$ objects
2. arrange the $r$ chosen objects

So

$${}^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.

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.

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.

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.

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.

Links

• Permutations and Combinations
• Special Arrangements and Restrictions