Study Guide: Permutations, Combinations, and Applications of Counting Principles in Probability

3.4 Additional Topics in Probability and Counting

Permutations

Permutations are fundamental in probability and counting, representing the number of ways a set of objects can be arranged in order. The concept is essential when the order of arrangement matters.

• Definition: A permutation is an ordered arrangement of objects.

• Formula for Permutations of n Distinct Objects: The number of permutations of n distinct objects is given by the factorial: $n!$

• Factorial: For a positive integer n, n! (read as "n factorial") is the product of all positive integers up to n. $n! = n \times (n-1) \times (n-2) \times \ldots \times 1$

• Special Case: $0! = 1$

• Example: The number of ways to fill the first row of a blank Sudoku grid (using digits 1–9 without repetition): $9! = 362,880$

Permutations of n Objects Taken r at a Time

Sometimes, only a subset of objects is arranged in order. This is called a permutation of n objects taken r at a time.

• Formula: $P(n, r) = \frac{n!}{(n-r)!}$

• Example: Forming four-digit codes with no repeated digits from 10 digits: $P(10, 4) = \frac{10!}{(10-4)!} = 5040$

• Application: Assigning positions (e.g., president, vice president, secretary, treasurer) among 12 board members: $P(12, 4) = \frac{12!}{(12-4)!} = 11,880$

Distinguishable Permutations

When some objects are identical, not all permutations are distinguishable. The formula adjusts for repeated items.

• Formula: For n objects, where n_1 are of one type, n_2 of another, ..., n_k of the k-th type: $\frac{n!}{n_1! \times n_2! \times \ldots \times n_k!}$

• Example: Arranging the letters AAAABBC: $\frac{7!}{4! \times 2! \times 1!} = 105$

• Application: Arranging 6 one-story, 4 two-story, and 2 split-level houses: $\frac{12!}{6! \times 4! \times 2!} = 13,860$

Combinations

Combinations count the number of ways to select objects from a group without regard to order. This is used when the arrangement does not matter.

• Definition: A combination is a selection of objects where order is not important.

• Formula: $C(n, r) = \binom{n}{r} = \frac{n!}{r! \times (n-r)!}$

• Example: Selecting 3 beaches out of 5 for restroom construction: $C(5, 3) = \frac{5!}{3! \times 2!} = 10$

• Application: Choosing 4 companies from 16 bids: $C(16, 4) = \frac{16!}{4! \times 12!} = 1820$

Applications of Counting Principles

Counting principles are used to solve probability problems by determining the number of possible outcomes. The main principles are summarized below.

Principle	Description	Formula
Fundamental Counting Principle	If one event can occur in m ways and a second event in n ways, the total number of ways both can occur in sequence is m × n.	$m \times n$
Permutations	Number of ordered arrangements of n distinct objects.	$n!$
Permutations (n objects taken r at a time)	Number of ordered arrangements of r objects from n distinct objects.	$\frac{n!}{(n-r)!}$
Distinguishable Permutations	Number of arrangements when some objects are identical.	$\frac{n!}{n_1! \times n_2! \times \ldots \times n_k!}$
Combinations	Number of ways to select r objects from n without regard to order.	$\frac{n!}{r! \times (n-r)!}$

Choosing the Appropriate Principle

• Are there two or more separate events? Use the Fundamental Counting Principle.

• Is the order of the objects important? Use Permutation.

• Are the chosen objects from a larger group and order is not important? Use Combination.

• Some problems may require more than one principle.

Probability Applications Using Counting Principles

Counting principles are often used to calculate probabilities by determining the ratio of favorable outcomes to total possible outcomes.

• General Probability Formula: $P = \frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}}$

• Example: Probability of selecting the correct three members for chair, secretary, and webmaster from 17 members: Number of favorable outcomes: 1 Number of possible outcomes: $P(17, 3) = 4080$ Probability: $\frac{1}{4080} \approx 0.000245$

• Example: Probability of being dealt 5 diamonds from a standard deck: Number of ways to choose 5 diamonds: $C(13, 5)$ Total number of 5-card hands: $C(52, 5)$ Probability: $\frac{C(13, 5)}{C(52, 5)}$

• Example: Probability of selecting exactly one toxic kernel from 400 kernels (3 toxic, 397 nontoxic): Number of ways to choose 1 toxic: $C(3, 1)$ Number of ways to choose 3 nontoxic: $C(397, 3)$ Total ways to choose 4 kernels: $C(400, 4)$ Probability: $\frac{C(3, 1) \times C(397, 3)}{C(400, 4)}$

Examples and Applications

• Sudoku Puzzle: Filling the first row with digits 1–9 (no repetition): $9! = 362,880$ ways.

• Four-digit Codes: Using digits 0–9, no repeats: $P(10, 4) = 5040$ codes.

• Assigning Board Positions: 12 members, 4 positions: $P(12, 4) = 11,880$ ways.

• Arranging Houses: 6 one-story, 4 two-story, 2 split-level: $\frac{12!}{6! \times 4! \times 2!} = 13,860$ ways.

• Selecting Committee: 20 employees, 3-person committee: $C(20, 3) = 1140$ ways.

• Lottery Probability: Powerball lottery involves combinations and permutations to calculate winning odds.

Additional info: Technology such as calculators, Excel, and statistical software can be used to compute permutations and combinations efficiently. Understanding when to use each counting principle is crucial for solving probability problems.