7.2 Permutations

Permutations are all about arranging things in different orders. They help us count how many ways we can line up objects or pick items in a specific sequence. This concept is super useful for solving real-world problems and understanding probabilities.

We use factorial notation and special formulas to calculate permutations. These tools let us figure out things like how many ways to arrange letters in a word or pick winners in a contest. It's a key part of discrete math and probability theory.

Permutations

Factorial formula for permutations

• Calculates the number of ways to arrange $n$ distinct objects in a specific order
  • Multiplies all positive integers from 1 up to $n$ (5 objects: $5 \times 4 \times 3 \times 2 \times 1 = 120$ arrangements)
• Accounts for repeated objects by dividing $n!$ by the factorial of each repeated object's count
  • Arranging "MISSISSIPPI" ($4$ I's, $4$ S's, $2$ P's, $1$ M): $\frac{11!}{4! \times 4! \times 2! \times 1!} = 34,650$ unique permutations
  • Eliminates duplicate arrangements caused by identical objects (e.g., swapping positions of two I's)
• Utilizes set theory principles to define the elements being arranged

Permutation notation for subsets

• Denotes the number of ways to select and arrange $r$ objects from a set of $n$ distinct objects
  • Notated as $P(n, r)$ or $_{n}P_{r}$, calculated as $\frac{n!}{(n-r)!}$
  • Choosing $3$ people from a group of $7$ to stand in a line: $P(7, 3) = \frac{7!}{(7-3)!} = 210$ possible arrangements
• Applies when order matters and repetition is not allowed
  • Arranging books on a shelf, selecting contest winners (first, second, third place)
• Contrasts with combinations, where order doesn't matter

Permutations in probability problems

1. Determine the total number of possible outcomes ($n$) and desired outcomes ($r$)
2. Calculate the number of ways the desired outcome can occur using the appropriate permutation formula
3. Divide the number of desired outcomes by the total outcomes to find the probability

• Winning a lottery by matching $6$ numbers drawn from $49$ in the correct order:
  • Total outcomes: $P(49, 6) = \frac{49!}{(49-6)!} = 10,068,347,520$
  • Desired outcome: $1$ (only one way to match all $6$ numbers in the correct order)
  • Probability: $\frac{1}{10,068,347,520} \approx 9.93 \times 10^{-11}$ (about $1$ in $10$ billion)
• Permutations help calculate probabilities for ordered outcomes (e.g., horse race results, card hands)

Related Concepts in Discrete Mathematics

• Counting techniques: Permutations are a fundamental counting method in discrete mathematics
• Probability: Permutations are essential for calculating probabilities of ordered events
• Combinations: Another counting technique used when order doesn't matter, complementing permutations