1.4 Counting Techniques
=======================

:bolditalic:`Key Terms`

:bolditalic:`Counting principle（乘法原理）`
   A method that multiplies the number of choices at each step.

:bolditalic:`Factorial（階乘）`
   The product of the positive integers from a number down to 1.

:bolditalic:`Permutation（排列）`
   A selection or arrangement where order matters.

:bolditalic:`Combination（組合）`
   A selection where order does not matter.

:bolditalic:`With replacement（放回抽樣）`
   A selected object is returned before the next selection.

:bolditalic:`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

.. math::

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

when all outcomes are equally likely.

Here:

- :math:`n` is the number of favorable outcomes;
- :math:`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:

.. math::

   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 :math:`n_1` choices, the second step has
:math:`n_2` choices, and so on, then the total number of possible results
is

.. math::

   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

.. math::

   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,

.. math::

   N=4\times3=12.

Therefore, there are 12 possible ordered results.

Some possible results are

.. math::

   AK,\ AQ,\ AJ,\ KA,\ldots

The result :math:`AK` is different from :math:`KA` because the order is
different.

.. image:: ../_static/figures/probability/figure_1_4_1_counting_principle_two_cards.png
   :width: 88%
   :align: center
   :alt: Four possible first-card choices, each followed by three possible second-card choices, giving twelve ordered outcomes.

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 :math:`n`,

.. math::

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

Also,

.. math::

   0!=1.

For example,

.. math::

   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

.. math::

   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,

.. math::

   4\times3\times2\times1=24.

Using factorial notation,

.. math::

   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** :math:`\longrightarrow` permutation

   **Order does not matter** :math:`\longrightarrow` combination

1.4.10 Permutation: Order Matters
---------------------------------

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

Suppose we select :math:`r` distinct objects from :math:`n` distinct
objects without replacement.

The number of ordered selections is

.. math::

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

The word ``ordered`` is important.

For example,

.. math::

   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

.. math::

   A,\ K,\ Q,\ J

and record the first card and the second card.

Because the positions are different, order matters.

From the counting principle,

.. math::

   4\times3=12.

Using the permutation formula,

.. math::

   {}_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:

.. math::

   4\times3.

1.4.12 Combination: Order Does Not Matter
-----------------------------------------

A **combination** is used when order does not matter.

Suppose we select :math:`r` distinct objects from :math:`n` distinct
objects.

The number of different groups is

.. math::

   \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 :math:`A` and :math:`K` is the same
group whether we write :math:`AK` or :math:`KA`.

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

Now suppose we select a group of two cards from

.. math::

   A,\ K,\ Q,\ J.

We do not care which card is selected first.

Therefore, order does not matter.

Using the combination formula,

.. math::

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

The six groups are

.. math::

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

We do not list :math:`KA` separately because it is the same two-card group
as :math:`AK`.

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

.. math::

   {}_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, :math:`AK` and :math:`KA` are different;
- in a combination, :math:`AK` and :math:`KA` represent the same group.

For two objects, each group can be ordered in

.. math::

   2!=2

ways.

That is why, in this example,

.. math::

   12 \div 2 = 6.

This also explains the :math:`r!` in the denominator of the combination
formula. It removes the repeated orderings of the same group.

.. image:: ../_static/figures/probability/figure_1_4_2_permutation_vs_combination.png
   :width: 88%
   :align: center
   :alt: A comparison showing that AK and KA are different permutations but the same combination.

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

.. math::

   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,

.. math::

   N=4\times4=16.

With replacement, results such as

.. math::

   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,

.. math::

   N=4\times3=12.

Without replacement, results such as :math:`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.

.. list-table::
   :header-rows: 1
   :widths: 42 28 30

   * - Question
     - Method
     - Number of results
   * - Arrange all four cards
     - Factorial
     - :math:`4!=24`
   * - Choose 2, order matters, without replacement
     - Permutation
     - :math:`{}_4P_2=12`
   * - Choose 2, order does not matter
     - Combination
     - :math:`\binom{4}{2}=6`
   * - Choose 2 in order, with replacement
     - Counting principle
     - :math:`4\times4=16`
   * - Choose 2 in order, without replacement
     - Counting principle
     - :math:`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:

.. list-table::
   :header-rows: 1
   :widths: 40 28 32

   * - Situation
     - Method
     - Main idea
   * - Several steps
     - Counting principle
     - Multiply the choices
   * - Arrange all :math:`n` objects
     - Factorial
     - Use :math:`n!`
   * - Select :math:`r` objects and order matters
     - Permutation
     - Different orders are different
   * - Select :math:`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

.. math::

   4\times3=12,

not

.. math::

   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, :math:`AK` and :math:`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, :math:`AK` and
:math:`KA` are different results.

A final mistake is to ignore replacement.

For two selections from four cards:

.. math::

   4\times4=16

with replacement, but

.. math::

   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,

.. math::

   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,

.. math::

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

where

- :math:`n` is the number of outcomes in event :math:`A`;
- :math:`N` is the number of outcomes in sample space :math:`S`.

The important connection is:

    count :math:`A` + count :math:`S` -> find :math:`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 :math:`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,

.. math::

   N=6\times6=36.

So, the sample space contains 36 ordered outcomes.

For example, :math:`(1,6)` and :math:`(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

.. math::

   (1,6),(2,5),(3,4),(4,3),(5,2),(6,1).

Therefore,

.. math::

   n=6.

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

.. image:: ../_static/figures/probability/figure_1_4_3_two_dice_sum_7.png
   :width: 62%
   :align: center
   :alt: A six-by-six grid of ordered outcomes for two dice with the six outcomes whose sum is seven highlighted.

**Step 3: Calculate the probability.**

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

Therefore,

.. math::

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

So, the probability that the sum is 7 is

.. math::

   \frac{1}{6}.

.. note::

   **For equally likely outcomes**

   .. math::

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

   First count the outcomes in :math:`A`, then count the outcomes in
   :math:`S`, and use these counts to find :math:`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:

.. math::

   N=n_1n_2\cdots n_k.

Factorial is

.. math::

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

with

.. math::

   0!=1.

When order matters, use a permutation:

.. math::

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

When order does not matter, use a combination:

.. math::

   \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

.. math::

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

.. 1.4.23 Short Review Questions
.. -----------------------------

.. 1. What is the counting principle?
.. 2. Why do we multiply the choices in a process with several steps?
.. 3. Calculate :math:`5!`.
.. 4. What is the difference between a permutation and a combination?
.. 5. From four cards, how many ordered selections of two cards are possible without replacement?
.. 6. From four cards, how many two-card groups are possible?
.. 7. Why are :math:`AK` and :math:`KA` different in a permutation?
.. 8. Why are :math:`AK` and :math:`KA` the same group in a combination?
.. 9. What does ``with replacement`` mean?
.. 10. What does ``without replacement`` mean?
.. 11. From four cards, how many ordered selections of two cards are possible with replacement?
.. 12. How does replacement change the number of choices?
.. 13. What question should you ask before choosing between a permutation and a combination?
.. 14. Why are counting techniques useful in probability?