3. Counting Probabilities with Combinatorics and the Factorial =========================================================== In the previous lesson, probability was calculated by counting favorable and total outcomes: .. math:: 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: .. math:: 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. .. admonition:: 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 .. admonition:: 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 :math:`HT` means heads first and tails second. The sequence :math:`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. .. admonition:: 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 | Main counting method | | | repetition? | | +======================+======================+===============================+ | Yes | Allowed | Repeated multiplication | | | | such as :math:`n^r` | +----------------------+----------------------+-------------------------------+ | Yes | Not allowed | Permutation | +----------------------+----------------------+-------------------------------+ | No | Not allowed | Combination | +----------------------+----------------------+-------------------------------+ | No | Allowed | Combination with repetition; | | | | not covered in this lesson | +----------------------+----------------------+-------------------------------+ .. admonition:: 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. .. admonition:: Rule: Multiplication principle If stage 1 can occur in :math:`n_1` ways, stage 2 can occur in :math:`n_2` ways, and so on, then the total number of outcomes is: .. math:: n_1n_2\cdots n_r Example: Three Coin Flips ~~~~~~~~~~~~~~~~~~~~~~~~~ Each flip has two possible outcomes: .. math:: H \quad \text{or} \quad T Therefore, three flips have: .. math:: 2\times 2\times 2=2^3=8 possible ordered sequences. The sample space is: .. math:: S=\{HHH,HHT,HTH,HTT,THH,THT,TTH,TTT\} Example: Ten Coin Flips ~~~~~~~~~~~~~~~~~~~~~~~ For ten coin flips, each position still has two choices. .. math:: |S|=2^{10}=1024 There are 1,024 possible ordered sequences. .. admonition:: 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: .. math:: 2^{10}=1024 Now consider the event: .. math:: 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. .. math:: |A|=\binom{10}{5}=252 Therefore: .. math:: P(A) = \frac{\binom{10}{5}}{2^{10}} = \frac{252}{1024} = 0.24609375 \approx 24.61\% .. admonition:: Interpretation There is approximately a 24.61 percent chance of obtaining exactly five heads in ten independent flips of a fair coin. .. admonition:: 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: .. math:: 52\times 51\times 50\times 49\times 48 The decrease occurs because a selected card is not returned to the deck. .. admonition:: 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. .. admonition:: Definition: Factorial For a positive integer :math:`n`, the factorial of :math:`n` is: .. math:: n!=n(n-1)(n-2)\cdots 3\times 2\times 1 The symbol :math:`n!` is read as **n factorial**. Examples ~~~~~~~~ .. math:: 1!=1 .. math:: 3!=3\times 2\times 1=6 .. math:: 5!=5\times 4\times 3\times 2\times 1=120 By definition: .. math:: 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: .. math:: 5\times 4\times 3\times 2\times 1=5!=120 .. admonition:: Interpretation A factorial counts the ways to arrange all :math:`n` different items when order matters. Cancel Before Calculating ~~~~~~~~~~~~~~~~~~~~~~~~~ Factorials often simplify because common factors cancel. For example: .. math:: \frac{10!}{7!} = \frac{10\times 9\times 8\times 7!}{7!} = 10\times 9\times 8 = 720 .. admonition:: Calculation advice Do not expand every factorial completely when cancellation is possible. 7. Permutations: Order Matters ------------------------------ Suppose we select :math:`r` different items from :math:`n` available items. An item cannot be used again, and order matters. The number of choices is: .. math:: n(n-1)(n-2)\cdots(n-r+1) This is called a permutation. .. admonition:: Definition: Permutation A permutation counts selections of :math:`r` different items from :math:`n` different items when order matters and an item cannot be used again. The formula is: .. math:: P(n,r) = {}_nP_r = \frac{n!}{(n-r)!} Here: * :math:`n` is the total number of available items; * :math:`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: .. math:: P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10\times 9\times 8 = 720 .. admonition:: 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: .. math:: 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 :math:`r` different items from :math:`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 :math:`A`, :math:`B`, and :math:`C` can be arranged as: :: ABC ACB BAC BCA CAB CBA These are six ordered arrangements: .. math:: 3!=6 If order does not matter, these six arrangements should count as only one selection. Therefore, divide the permutation count by :math:`r!`. .. admonition:: Definition: Combination A combination counts selections of :math:`r` different items from :math:`n` different items when order does not matter and an item cannot be used again. The formula is: .. math:: \binom{n}{r} = C(n,r) = {}_nC_r = \frac{n!}{r!(n-r)!} The notation :math:`\binom{n}{r}` is read as **n choose r**. How Permutations and Combinations Are Related ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. math:: P(n,r)=\binom{n}{r}r! Therefore: .. math:: \binom{n}{r}=\frac{P(n,r)}{r!} Dividing by :math:`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. .. math:: \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. .. admonition:: 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: .. math:: \binom{52}{5} = \frac{52!}{5!47!} = 2{,}598{,}960 Why do we divide by :math:`5!`? Each group of five cards can be dealt in: .. math:: 5!=120 orders. However, those 120 deal orders produce the same poker hand. The relationship is: .. math:: \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: .. math:: \binom{13}{5}=1287 The total number of five-card hands is: .. math:: \binom{52}{5}=2{,}598{,}960 Therefore: .. math:: P(\text{five hearts}) = \frac{\binom{13}{5}}{\binom{52}{5}} = \frac{1287}{2{,}598{,}960} \approx 0.0004952 As a percentage: .. math:: P(\text{five hearts})\approx 0.04952\% .. admonition:: 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: .. math:: \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: .. math:: 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 | :math:`2^{10}` | +---------------------------------+-------------------------------------------+ | Sequences with five heads | :math:`\binom{10}{5}` | +---------------------------------+-------------------------------------------+ .. admonition:: 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: .. math:: 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: .. math:: 26\times 25\times 24\times 10\times 9\times 8 = 11{,}232{,}000 .. admonition:: Interpretation The format alone is not enough. The repetition rules change the count. .. admonition:: 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: .. math:: \binom{10}{3}=120 If three employees are assigned to three different roles: .. math:: 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: .. math:: 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: .. math:: \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. .. admonition:: 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 | +============================+============================+========================+ | :math:`r` ordered choices, | :math:`n^r` | Can an option repeat? | | repetition allowed | | | +----------------------------+----------------------------+------------------------+ | :math:`r` ordered choices, | :math:`P(n,r)` | Does order matter? | | no repetition | :math:`=n!/(n-r)!` | | +----------------------------+----------------------------+------------------------+ | Order does not matter, | :math:`\binom{n}{r}` | Is this only a group | | no repetition | :math:`=n!/(r!(n-r)!)` | 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 :math:`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: .. math:: 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 :math:`52!` and :math:`47!` separately, cancel first: .. math:: \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: .. math:: 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: .. math:: n!=n(n-1)(n-2)\cdots 2\times 1 When order matters and repetition is not allowed: .. math:: P(n,r)=\frac{n!}{(n-r)!} When order does not matter and repetition is not allowed: .. math:: \binom{n}{r}=\frac{n!}{r!(n-r)!} The relationship between them is: .. math:: 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: .. math:: \text{probability} = \frac{\text{favorable count}} {\text{total count}} These methods make large probability problems easier to count.