3. Counting Probabilities with Combinatorics and the Factorial

In the previous lesson, probability was calculated by counting favorable and total outcomes:

\[P(A)=\frac{|A|}{|S|}\]

This method is simple when the sample space is small. However, listing every outcome becomes difficult when an experiment has many stages.

For example:

• ten coin flips produce many possible sequences;

• five cards can be selected from a deck in many ways;

• a product code may contain several letters and digits;

• several workers may be selected and assigned to different roles.

Combinatorics gives us faster ways to count these outcomes.

Use this process:

probability question
   -> identify total outcomes
   -> identify favorable outcomes
   -> ask whether order matters
   -> ask whether repetition or replacement is allowed
   -> choose a counting method
   -> calculate the probability
   -> interpret the result

This lesson focuses on:

• the multiplication principle;

• counting with and without replacement;

• the factorial;

• permutations when order matters;

• combinations when order does not matter;

• applications to coin flips, poker hands, and license plates.

1. Why We Need Combinatorics

For equally likely outcomes, probability is calculated as:

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

The formula is simple. The main task is to count the favorable and total outcomes correctly.

Suppose a fair coin is flipped ten times. The first few possible sequences are:

HHHHHHHHHH
HHHHHHHHHT
HHHHHHHHTH
HHHHHHHHTT
...

Writing every sequence one by one is not practical.

Definition: Combinatorics

Combinatorics provides methods for counting possible selections, arrangements, and outcomes.

It lets us count many possible outcomes without listing them one by one.

The connection to probability is:

combinatorics counts outcomes
           |
           v
probability compares favorable and total counts

Principle: Count before calculating probability

In many probability problems, first count:

1. all possible outcomes;

2. the outcomes that satisfy the event.

Then divide the favorable count by the total count.

2. Choose the Counting Method

Before using a formula, ask two questions.

Does Order Matter?

Order matters when changing the sequence creates a different outcome.

For example:

HT != TH

The sequence \(HT\) means heads first and tails second. The sequence \(TH\) means tails first and heads second.

For a license plate:

ABC123 != BAC123

Changing the order creates a different plate.

However, in a five-card poker hand, the same five cards usually form the same hand even if they were dealt in a different order.

Principle: Order

If changing the order creates a different result, order matters.

If changing the order does not create a different result, order does not matter.

Can an Option Be Used Again?

Repetition allowed means that the same option can be used more than once. In sampling, this may happen when an item is returned after selection.

Without replacement means that a selected item is not returned. The number of choices then decreases.

For example, when drawing cards without replacement:

first card     52 choices
second card    51 choices
third card     50 choices

For a three-digit code with repetition allowed:

first digit    10 choices
second digit   10 choices
third digit    10 choices

The same digit may appear more than once.

A useful decision table is:

Does order matter?	Replacement or repetition?	Main counting method
Yes	Allowed	Repeated multiplication such as \(n^r\)
Yes	Not allowed	Permutation
No	Not allowed	Combination
No	Allowed	Combination with repetition; not covered in this lesson

Warning

Do not choose a formula only because the problem uses the word “select.” First decide whether order matters and whether repetition is allowed.

3. Multiply the Number of Choices

The previous lesson introduced multiplication for experiments with several steps.

Rule: Multiplication principle

If stage 1 can occur in \(n_1\) ways, stage 2 can occur in \(n_2\) ways, and so on, then the total number of outcomes is:

\[n_1n_2\cdots n_r\]

Example: Three Coin Flips

Each flip has two possible outcomes:

\[H \quad \text{or} \quad T\]

Therefore, three flips have:

\[2\times 2\times 2=2^3=8\]

possible ordered sequences.

The sample space is:

\[S=\{HHH,HHT,HTH,HTT,THH,THT,TTH,TTT\}\]

Example: Ten Coin Flips

For ten coin flips, each position still has two choices.

\[|S|=2^{10}=1024\]

There are 1,024 possible ordered sequences.

Interpretation

The multiplication principle counts all possible paths through a sequence of choices.

4. Count Coin-Flip Results

Suppose a fair coin is flipped ten times.

The total number of possible ordered sequences is:

\[2^{10}=1024\]

Now consider the event:

\[A=\{\text{exactly five heads in ten flips}\}\]

A sequence such as:

HHHHHTTTTT

has five heads. However, the heads can appear in many different positions:

HHHHHTTTTT
HHTHTHTHTT
THTHHTHTHT
...

The event is not one outcome. It contains every sequence with exactly five heads and five tails.

To count these sequences, we need to choose which five of the ten positions contain heads.

\[|A|=\binom{10}{5}=252\]

Therefore:

\[P(A) = \frac{\binom{10}{5}}{2^{10}} = \frac{252}{1024} = 0.24609375 \approx 24.61\%\]

Interpretation

There is approximately a 24.61 percent chance of obtaining exactly five heads in ten independent flips of a fair coin.

Key idea

The full sample space counts every ordered sequence.

The event count chooses the five positions that contain heads. The combination formula is explained later in this lesson.

5. Draw Cards Without Replacement

A standard deck has 52 different cards.

Suppose five cards are drawn without replacement.

If the order of dealing is recorded, the number of choices changes at every stage:

first card      52 choices
second card     51 choices
third card      50 choices
fourth card     49 choices
fifth card      48 choices

Therefore, the number of ordered five-card sequences is:

\[52\times 51\times 50\times 49\times 48\]

The decrease occurs because a selected card is not returned to the deck.

Principle: Without replacement

When sampling without replacement, the number of available choices decreases after each selection.

For poker, however, the order of the five cards normally does not matter. The same five cards can be dealt in many different orders but still form one poker hand.

This counts the same hand many times. Factorials and combinations remove this repeated counting.

6. Factorials

Counting often uses a product of decreasing whole numbers. A factorial is a short way to write this product.

Definition: Factorial

For a positive integer \(n\), the factorial of \(n\) is:

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

The symbol \(n!\) is read as n factorial.

Examples

\[1!=1\]

\[3!=3\times 2\times 1=6\]

\[5!=5\times 4\times 3\times 2\times 1=120\]

By definition:

\[0!=1\]

Why We Use Factorials

Suppose five different items must be arranged in five positions.

For the first position, there are 5 choices. After one item is used, there are 4 choices. The choices continue to decrease:

position 1     5 choices
position 2     4 choices
position 3     3 choices
position 4     2 choices
position 5     1 choice

Therefore:

\[5\times 4\times 3\times 2\times 1=5!=120\]

Interpretation

A factorial counts the ways to arrange all \(n\) different items when order matters.

Cancel Before Calculating

Factorials often simplify because common factors cancel.

For example:

\[\frac{10!}{7!} = \frac{10\times 9\times 8\times 7!}{7!} = 10\times 9\times 8 = 720\]

Calculation advice

Do not expand every factorial completely when cancellation is possible.

7. Permutations: Order Matters

Suppose we select \(r\) different items from \(n\) available items. An item cannot be used again, and order matters.

The number of choices is:

\[n(n-1)(n-2)\cdots(n-r+1)\]

This is called a permutation.

Definition: Permutation

A permutation counts selections of \(r\) different items from \(n\) different items when order matters and an item cannot be used again.

The formula is:

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

Here:

• \(n\) is the total number of available items;

• \(r\) is the number of positions to fill.

Example: Assign Three Roles

Ten workers are available. A manager must assign three different roles: leader, recorder, and presenter.

Order matters because the roles are different.

The number of assignments is:

\[P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10\times 9\times 8 = 720\]

Interpretation

There are 720 ways to select and assign three of the ten workers to the three different roles.

Example: Record the Card Order

If the deal order is recorded, the number of five-card sequences is:

\[P(52,5) = \frac{52!}{47!} = 52\times 51\times 50\times 49\times 48\]

This counts the same set of five cards many times because different deal orders are treated as different outcomes.

8. Combinations: Order Does Not Matter

Suppose we choose \(r\) different items from \(n\) different items, and order does not matter.

An ordered count includes all possible orders of each selected group.

For example, the three selected items \(A\), \(B\), and \(C\) can be arranged as:

ABC   ACB   BAC   BCA   CAB   CBA

These are six ordered arrangements:

\[3!=6\]

If order does not matter, these six arrangements should count as only one selection. Therefore, divide the permutation count by \(r!\).

Definition: Combination

A combination counts selections of \(r\) different items from \(n\) different items when order does not matter and an item cannot be used again.

The formula is:

\[\binom{n}{r} = C(n,r) = {}_nC_r = \frac{n!}{r!(n-r)!}\]

The notation \(\binom{n}{r}\) is read as n choose r.

How Permutations and Combinations Are Related

\[P(n,r)=\binom{n}{r}r!\]

Therefore:

\[\binom{n}{r}=\frac{P(n,r)}{r!}\]

Dividing by \(r!\) removes the different orders of the same group.

Example: Select Three Workers

Ten workers are available. A manager wants to select three workers for one committee. All committee members have the same role.

Order does not matter.

\[\binom{10}{3} = \frac{10!}{3!7!} = \frac{10\times 9\times 8}{3\times 2\times 1} = 120\]

Compare the two situations:

Situation	Counting method	Number
Select leader, recorder, presenter	Permutation	720
Select three committee members	Combination	120

The same ten people and three selections are involved. The difference is whether the roles make the order important.

Main question

Ask: If I change the order, do I obtain a different result?

• If yes, use a permutation.

• If no, use a combination.

9. Count Poker Hands

For a five-card poker hand, the order of the cards does not matter. Therefore, the total number of five-card hands is:

\[\binom{52}{5} = \frac{52!}{5!47!} = 2{,}598{,}960\]

Why do we divide by \(5!\)?

Each group of five cards can be dealt in:

\[5!=120\]

orders. However, those 120 deal orders produce the same poker hand.

The relationship is:

\[\binom{52}{5} = \frac{P(52,5)}{5!}\]

Example: Five Hearts

Suppose five cards are drawn from a standard deck. What is the probability that all five cards are hearts?

There are 13 hearts in the deck. The number of favorable five-heart hands is:

\[\binom{13}{5}=1287\]

The total number of five-card hands is:

\[\binom{52}{5}=2{,}598{,}960\]

Therefore:

\[P(\text{five hearts}) = \frac{\binom{13}{5}}{\binom{52}{5}} = \frac{1287}{2{,}598{,}960} \approx 0.0004952\]

As a percentage:

\[P(\text{five hearts})\approx 0.04952\%\]

Interpretation

The probability is very small because only 1,287 of the 2,598,960 possible five-card hands contain five hearts.

10. Return to the Ten-Coin Example

We can now explain the earlier coin-flip count fully.

There are ten ordered flip positions. We want exactly five positions to contain heads.

The positions of the five heads can be selected in:

\[\binom{10}{5}=252\]

ways.

Once the five head positions are chosen, the remaining five positions must be tails. Therefore, no additional choice is needed.

The probability is:

\[P(\text{exactly five heads}) = \frac{\binom{10}{5}}{2^{10}}\]

This combines two counting ideas:

Part of probability	Counting method
Total ten-flip sequences	\(2^{10}\)
Sequences with five heads	\(\binom{10}{5}\)

Principle: Different counts may use different methods

The numerator and denominator do not always use the same counting formula. Count each one according to its own structure.

11. Count License Plates

A license plate is an ordered code. Changing the position of a letter or digit creates a different plate.

The exact number of plates depends on the rules.

Example: Repetition Is Allowed

Suppose a plate contains three letters followed by three digits:

L L L D D D

Assume:

• each letter position has 26 choices;

• each digit position has 10 choices;

• letters and digits may repeat.

Using the multiplication principle:

\[26\times 26\times 26\times 10\times 10\times 10 = 26^3 10^3 = 17{,}576{,}000\]

Example: Repetition Is Not Allowed

Now suppose that letters cannot repeat and digits cannot repeat.

The numbers of choices are:

letters:  26, 25, 24
digits:   10,  9,  8

Therefore:

\[26\times 25\times 24\times 10\times 9\times 8 = 11{,}232{,}000\]

Interpretation

The format alone is not enough. The repetition rules change the count.

Warning

Always state whether repetition is allowed. A missing assumption can change the answer substantially.

12. Industrial Engineering Examples

These counting methods are also useful in Industrial Engineering.

Select a Team or Assign Roles

A production improvement team may be selected from ten employees.

If three equal team members are selected:

\[\binom{10}{3}=120\]

If three employees are assigned to three different roles:

\[P(10,3)=720\]

Plan an Inspection Sequence

Suppose five different inspection stations are available, and three stations must be visited in sequence without repetition.

Because the visit order matters:

\[P(5,3) = 5\times 4\times 3 = 60\]

Select Product Samples

Suppose a quality engineer selects four products from a batch of 30 products. The order of selection is not recorded, and products are not replaced.

The number of possible samples is:

\[\binom{30}{4}\]

Count Product Codes

A product code may contain letters, digits, or categories. The multiplication principle counts possible codes, but the count depends on:

• the number of positions;

• the available symbols for each position;

• whether repetition is allowed;

• whether some positions have restrictions.

So what?

Counting helps Industrial Engineers compare samples, assignments, sequences, codes, and possible operating outcomes.

13. Counting Steps

Use the following workflow before selecting a formula.

Step 1: What is being counted?
             |
             v
Step 2: Does order matter?
             |
             v
Step 3: Is replacement or repetition allowed?
             |
             v
Step 4: How many choices are available at each stage?
             |
             v
Step 5: Choose multiplication, permutation, or combination.
             |
             v
Step 6: Use the count in the probability formula.
             |
             v
Step 7: Interpret the result.

The method-selection table is:

Situation	Formula	Main question
\(r\) ordered choices, repetition allowed	\(n^r\)	Can an option repeat?
\(r\) ordered choices, no repetition	\(P(n,r)\) \(=n!/(n-r)!\)	Does order matter?
Order does not matter, no repetition	\(\binom{n}{r}\) \(=n!/(r!(n-r)!)\)	Is this only a group or selection?

14. Common Mistakes

Mistake 1: Ignoring Order

Selecting a leader and an assistant is not the same as selecting two equal committee members.

leader = A, assistant = B

is different from:

leader = B, assistant = A

Use a permutation when the positions or roles are different.

Mistake 2: Counting Order When It Does Not Matter

A poker hand should not be counted as a new hand every time the same cards are dealt in a different order.

Divide the ordered count by \(r!\), or use the combination formula.

Mistake 3: Forgetting Whether Repetition Is Allowed

With replacement:

n, n, n, ...

Without replacement:

n, n-1, n-2, ...

Mistake 4: Treating a Count as a Probability

A combination or permutation gives a number of outcomes. It is not automatically a probability.

For equally likely outcomes:

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

Mistake 5: Assuming Equal Likelihood

Counting formulas produce probabilities directly only when the relevant sample points are equally likely.

For a fair coin, all ten-flip sequences have the same probability. For a biased coin, simple favorable-over-total counting may not be sufficient.

Mistake 6: Expanding Large Factorials

Instead of calculating \(52!\) and \(47!\) separately, cancel first:

\[\frac{52!}{47!} = 52\times 51\times 50\times 49\times 48\]

This is simpler and reduces calculation errors.

15. Summary

The previous lesson introduced probability by simple counting:

\[P(A)=\frac{|A|}{|S|}\]

This lesson introduced faster methods for counting large sample spaces and events.

The first key question is whether order matters.

order matters      -> permutation
order does not     -> combination

The second key question is whether repetition or replacement is allowed.

The factorial is:

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

When order matters and repetition is not allowed:

\[P(n,r)=\frac{n!}{(n-r)!}\]

When order does not matter and repetition is not allowed:

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

The relationship between them is:

\[P(n,r)=\binom{n}{r}r!\]

Key Points

• Combinatorics counts outcomes without listing them individually.

• The multiplication principle counts choices across several steps.

• A factorial describes a decreasing product of positive integers.

• A permutation is used when order matters.

• A combination is used when order does not matter.

• Without replacement, the number of available choices decreases.

• With repetition, the same choice may be used again.

• The numerator and denominator of a probability may require different counting methods.

• Counting gives the number of outcomes; probability compares favorable and total outcomes.

• Assumptions about order, replacement, and equal likelihood must be stated clearly.

Final Check

Before calculating, ask:

What am I counting?
Does order matter?
Can an option be repeated?

Then choose the counting method:

multiplication
   or
permutation
   or
combination

Finally, return to probability:

\[\text{probability} = \frac{\text{favorable count}} {\text{total count}}\]

These methods make large probability problems easier to count.