1.4 Counting Techniques

Key Terms

Counting principle（乘法原理）

A method that multiplies the number of choices at each step.

Factorial（階乘）

The product of the positive integers from a number down to 1.

Permutation（排列）

A selection or arrangement where order matters.

Combination（組合）

A selection where order does not matter.

With replacement（放回抽樣）

A selected object is returned before the next selection.

Without replacement（不放回抽樣）

A selected object is not returned before the next selection.

1.4.2 Learning Outcomes

After completing this section, students should be able to:

• explain why counting techniques are useful in probability;

• use the counting principle for a process with several steps;

• calculate simple factorials;

• explain when order matters;

• use permutations when order matters;

• use combinations when order does not matter;

• explain the difference between selection with replacement and without replacement;

• choose an appropriate counting method for a simple problem.

1.4.3 Why Do We Need Counting Techniques?

In Section 1.3, we used the probability formula

\[P(A)=\frac{n}{N}\]

when all outcomes are equally likely.

Here:

• \(n\) is the number of favorable outcomes;

• \(N\) is the total number of possible outcomes.

For a small sample space, we can list all outcomes and count them.

For a larger sample space, listing every outcome may take too much time.

Counting techniques help us find the number of possible outcomes without listing every sample point.

The main question in this section is:

How many possible outcomes are there?

1.4.4 Running Example: Four Different Cards

We will often use the same four different cards:

\[A,\ K,\ Q,\ J.\]

Using the same cards helps us compare different counting questions.

For example, we may:

• select two cards in order;

• arrange all four cards;

• choose a group of two cards;

• select cards with replacement;

• select cards without replacement.

The cards are the same, but the counting method may change because the question changes.

1.4.5 Counting Principle

Suppose a process has several steps.

If the first step has \(n_1\) choices, the second step has \(n_2\) choices, and so on, then the total number of possible results is

\[N=n_1n_2\cdots n_k.\]

Note

Counting principle: for several steps, multiply the number of choices at each step.

The reason is that each choice from one step can be combined with the choices from the next step.

1.4.6 Example 1: Select Two Cards in Order

Suppose we select two cards from

\[A,\ K,\ Q,\ J\]

without repeating a card.

For the first card, there are 4 choices.

After one card is selected, only 3 cards remain.

So, for the second card, there are 3 choices.

Using the counting principle,

\[N=4\times3=12.\]

Therefore, there are 12 possible ordered results.

Some possible results are

\[AK,\ AQ,\ AJ,\ KA,\ldots\]

The result \(AK\) is different from \(KA\) because the order is different.

The diagram shows why the numbers of choices are multiplied: each of the 4 first-card choices can be paired with 3 remaining second-card choices.

1.4.7 Factorial

A factorial is a short way to write a decreasing product.

For a positive integer \(n\),

\[n!=n(n-1)(n-2)\cdots(2)(1).\]

Also,

\[0!=1.\]

For example,

\[4!=4\times3\times2\times1=24.\]

Factorial is useful when we arrange all objects in order.

1.4.8 Example 2: Arrange All Four Cards

Suppose we arrange all four cards

\[A,\ K,\ Q,\ J\]

in a row.

For the first position, there are 4 choices.

For the second position, 3 cards remain.

For the third position, 2 cards remain.

For the last position, only 1 card remains.

Therefore,

\[4\times3\times2\times1=24.\]

Using factorial notation,

\[4!=24.\]

So, there are 24 different arrangements of the four cards.

1.4.9 Permutation and Combination

Many counting problems ask us to select only some of the available objects.

Before choosing a formula, ask:

Does order matter?

This question tells us whether to use a permutation or a combination.

Note

Order matters \(\longrightarrow\) permutation

Order does not matter \(\longrightarrow\) combination

1.4.10 Permutation: Order Matters

A permutation is used when the order of the selected objects matters.

Suppose we select \(r\) distinct objects from \(n\) distinct objects without replacement.

The number of ordered selections is

\[{}_nP_r=\frac{n!}{(n-r)!}.\]

The word ordered is important.

For example,

\[AK \neq KA.\]

Both selections contain the same two cards, but their order is different.

1.4.11 Example 3A: Select Two Cards When Order Matters

Suppose we select two cards from

\[A,\ K,\ Q,\ J\]

and record the first card and the second card.

Because the positions are different, order matters.

From the counting principle,

\[4\times3=12.\]

Using the permutation formula,

\[{}_4P_2 = \frac{4!}{(4-2)!} = \frac{4!}{2!} = 12.\]

Both methods give the same answer.

This is because the permutation formula is a compact way to count the decreasing number of choices:

\[4\times3.\]

1.4.12 Combination: Order Does Not Matter

A combination is used when order does not matter.

Suppose we select \(r\) distinct objects from \(n\) distinct objects.

The number of different groups is

\[\binom{n}{r} = \frac{n!}{r!(n-r)!}.\]

For a combination, changing the order does not create a new group.

For example, the group containing \(A\) and \(K\) is the same group whether we write \(AK\) or \(KA\).

1.4.13 Example 3B: Select Two Cards When Order Does Not Matter

Now suppose we select a group of two cards from

\[A,\ K,\ Q,\ J.\]

We do not care which card is selected first.

Therefore, order does not matter.

Using the combination formula,

\[\binom{4}{2} = \frac{4!}{2!(4-2)!} = \frac{4!}{2!2!} = 6.\]

The six groups are

\[AK,\ AQ,\ AJ,\ KQ,\ KJ,\ QJ.\]

We do not list \(KA\) separately because it is the same two-card group as \(AK\).

This is why the combination answer is smaller than the permutation answer:

\[{}_4P_2=12, \qquad \binom{4}{2}=6.\]

1.4.14 Why Permutation and Combination Give Different Answers

The difference comes from whether different orders count as different results.

For two selected cards:

• in a permutation, \(AK\) and \(KA\) are different;

• in a combination, \(AK\) and \(KA\) represent the same group.

For two objects, each group can be ordered in

\[2!=2\]

ways.

That is why, in this example,

\[12 \div 2 = 6.\]

This also explains the \(r!\) in the denominator of the combination formula. It removes the repeated orderings of the same group.

The key distinction is whether changing the order creates a new result.

1.4.15 With and Without Replacement

Another important question is:

Is the selected object returned before the next selection?

If the object is returned, the selection is with replacement.

If the object is not returned, the selection is without replacement.

Note

With replacement

Choices remain available.

Without replacement

The number of available choices decreases.

Replacement changes the number of choices in later steps.

1.4.16 Example 4: Select Two Cards in Order

Again, use the four cards

\[A,\ K,\ Q,\ J.\]

With replacement

For the first card, there are 4 choices.

After selecting the first card, put it back.

Therefore, there are again 4 choices for the second card.

So,

\[N=4\times4=16.\]

With replacement, results such as

\[AA,\ KK,\ QQ,\ JJ\]

are possible.

Without replacement

For the first card, there are 4 choices.

Do not return the selected card.

Therefore, only 3 choices remain for the second card.

So,

\[N=4\times3=12.\]

Without replacement, results such as \(AA\) are not possible because the first card cannot be selected again.

1.4.17 Comparing the Same Four Cards

The same four cards can produce different counts because the question is different.

Question	Method	Number of results
Arrange all four cards	Factorial	\(4!=24\)
Choose 2, order matters, without replacement	Permutation	\({}_4P_2=12\)
Choose 2, order does not matter	Combination	\(\binom{4}{2}=6\)
Choose 2 in order, with replacement	Counting principle	\(4\times4=16\)
Choose 2 in order, without replacement	Counting principle	\(4\times3=12\)

The important lesson is that the objects alone do not determine the method.

We must read the question carefully.

1.4.18 A Simple Decision Method

When solving a counting problem, use these steps.

Step 1: Identify the steps.

Ask:

What happens first? What happens next?

Step 2: Count the choices at each step.

If the problem has several steps, the counting principle may be useful.

Step 3: Check replacement.

Ask:

Can the same object be selected again?

With replacement, the number of choices may stay the same.

Without replacement, the number of choices usually decreases.

Step 4: Ask whether order matters.

Ask:

If I change the order, do I get a different result?

If yes, use a permutation.

If no, use a combination.

Step 5: Check the answer.

Make sure the count matches the type of result asked for in the problem.

A useful guide is:

Situation	Method	Main idea
Several steps	Counting principle	Multiply the choices
Arrange all \(n\) objects	Factorial	Use \(n!\)
Select \(r\) objects and order matters	Permutation	Different orders are different
Select \(r\) objects and order does not matter	Combination	Different orders give the same group

1.4.19 Common Mistakes

A common mistake is to add the number of choices instead of multiplying them.

For two steps with 4 choices and then 3 choices, the correct count is

\[4\times3=12,\]

not

\[4+3=7.\]

Another mistake is to forget that the number of choices changes without replacement.

After one card is selected from four cards and not returned, only three cards remain.

A third mistake is to use a permutation when order does not matter.

If the question asks for a two-card group, \(AK\) and \(KA\) should not be counted as two different groups.

A fourth mistake is to use a combination when order does matter.

If the question asks for a first card and a second card, \(AK\) and \(KA\) are different results.

A final mistake is to ignore replacement.

For two selections from four cards:

\[4\times4=16\]

with replacement, but

\[4\times3=12\]

without replacement.

1.4.20 Counting and Probability

Counting techniques are useful in probability because they help us count the outcomes in an event and the outcomes in the sample space.

For equally likely outcomes,

\[P(A) = \frac{\text{number of outcomes in }A} {\text{number of outcomes in }S}.\]

This is the same probability rule from Section 1.3.

In counting notation,

\[P(A)=\frac{n}{N},\]

where

• \(n\) is the number of outcomes in event \(A\);

• \(N\) is the number of outcomes in sample space \(S\).

The important connection is:

count \(A\) + count \(S\) -> find \(P(A)\)

Counting techniques do not create a new probability rule. They help us find the two counts needed in the probability calculation.

1.4.21 Example 5: Two Dice, Sum = 7

Suppose two fair dice are rolled.

Let \(A\) be the event that the sum of the two dice is 7.

Step 1: Count all possible outcomes.

Each die has 6 possible outcomes.

Using the counting principle,

\[N=6\times6=36.\]

So, the sample space contains 36 ordered outcomes.

For example, \((1,6)\) and \((6,1)\) are different outcomes because the first and second dice are recorded separately.

Step 2: Count the favorable outcomes.

The outcomes with sum 7 are

\[(1,6),(2,5),(3,4),(4,3),(5,2),(6,1).\]

Therefore,

\[n=6.\]

The full two-dice sample space can be organized as a \(6\times6\) grid. The highlighted cells are exactly the six ordered outcomes whose sum is 7.

Step 3: Calculate the probability.

Because the two dice are fair, all 36 ordered outcomes are equally likely.

Therefore,

\[P(A) = \frac{n}{N} = \frac{6}{36} = \frac{1}{6}.\]

So, the probability that the sum is 7 is

\[\frac{1}{6}.\]

Note

For equally likely outcomes

\[P(A) = \frac{\text{favorable outcomes}} {\text{total outcomes}}.\]

First count the outcomes in \(A\), then count the outcomes in \(S\), and use these counts to find \(P(A)\).

1.4.22 Summary

Counting techniques help us find the number of possible outcomes without listing every sample point.

For several steps, use the counting principle:

\[N=n_1n_2\cdots n_k.\]

Factorial is

\[n!=n(n-1)(n-2)\cdots(2)(1),\]

with

\[0!=1.\]

When order matters, use a permutation:

\[{}_nP_r=\frac{n!}{(n-r)!}.\]

When order does not matter, use a combination:

\[\binom{n}{r} = \frac{n!}{r!(n-r)!}.\]

Replacement changes the number of choices available at later steps.

The main decision process is:

Identify the steps -> Check replacement -> Ask whether order matters

Counting techniques connect directly to probability because they help us find the counts used in

\[P(A)=\frac{n}{N}.\]