Intro to Probability Unit 3 ReviewCounting: Permutations and Combinations

Key Concepts and Definitions

• Permutations involve arranging objects in a specific order where order matters
• Combinations involve selecting objects from a group where order does not matter
• Factorial notation $n!$ represents the product of all positive integers less than or equal to $n$
  • Example: $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
• Permutations with repetition allow objects to be chosen more than once
• Combinations with repetition allow objects to be chosen more than once and order does not matter
• The binomial coefficient $\binom{n}{k}$ represents the number of ways to choose $k$ objects from a set of $n$ objects
• The multiplication principle states that if there are $m$ ways to do one thing and $n$ ways to do another, there are $m \times n$ ways to do both

Fundamental Counting Principle

• Multiplicative principle states that if there are $n_1$ ways to perform task 1, $n_2$ ways to perform task 2, ..., and $n_k$ ways to perform task $k$, then there are $n_1 \times n_2 \times ... \times n_k$ ways to perform all $k$ tasks together
  • Example: If there are 3 shirt colors and 4 pant colors, there are $3 \times 4 = 12$ possible outfits
• Additive principle states that if there are $n_1$ ways to perform task 1 and $n_2$ ways to perform task 2, and the tasks are mutually exclusive, then there are $n_1 + n_2$ ways to perform either task
• The number of ways to arrange $n$ distinct objects is $n!$
  • Example: The number of ways to arrange the letters A, B, and C is $3! = 3 \times 2 \times 1 = 6$
• The number of ways to arrange $n$ objects where there are $n_1$ identical objects of type 1, $n_2$ identical objects of type 2, ..., and $n_k$ identical objects of type $k$ is $\frac{n!}{n_1! \times n_2! \times ... \times n_k!}$
• The number of ways to select $k$ objects from a set of $n$ objects is $\binom{n}{k} = \frac{n!}{k!(n-k)!}$

Permutations Explained

• A permutation is an ordered arrangement of objects
• The number of permutations of $n$ distinct objects is $n!$
• The number of permutations of $n$ objects taken $r$ at a time is denoted as $P(n,r)$ or $nPr$ and is calculated as $\frac{n!}{(n-r)!}$
  • Example: The number of ways to select 3 people from a group of 10 to stand in a line is $P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 720$
• Permutations with repetition, where objects can be chosen more than once, are calculated as $n^r$
  • Example: The number of 4-digit PIN codes using digits 0-9 is $10^4 = 10,000$
• Circular permutations, where arrangements in a circle are considered the same if they can be rotated to match, are calculated as $(n-1)!$
• Permutations with indistinguishable objects are calculated using the formula $\frac{n!}{n_1! \times n_2! \times ... \times n_k!}$

Combinations Demystified

• A combination is a selection of objects where order does not matter
• The number of combinations of $n$ objects taken $r$ at a time is denoted as $C(n,r)$, $nCr$, or $\binom{n}{r}$ and is calculated as $\frac{n!}{r!(n-r)!}$
  • Example: The number of ways to select 3 toppings from a list of 10 is $C(10,3) = \frac{10!}{3!(10-3)!} = \frac{10!}{3!7!} = 120$
• Combinations with repetition, where objects can be chosen more than once and order does not matter, are calculated as $\binom{n+r-1}{r}$
  • Example: The number of ways to select 3 scoops of ice cream from 5 flavors, allowing repetition, is $\binom{5+3-1}{3} = \binom{7}{3} = 35$
• The binomial theorem states that $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$
• Pascal's triangle is a triangular array of binomial coefficients where each number is the sum of the two numbers above it
• The hockey-stick identity states that the sum of any $r+1$ consecutive binomial coefficients in a diagonal of Pascal's triangle equals the next binomial coefficient in the next diagonal

Permutations vs Combinations: When to Use Which

• Use permutations when order matters and each object can only be used once
  • Example: Arranging books on a shelf, where the order of the books is important
• Use combinations when order does not matter and each object can only be used once
  • Example: Selecting a committee from a group of people, where the order of selection does not matter
• Use permutations with repetition when order matters and objects can be chosen more than once
  • Example: Creating a password where characters can be repeated
• Use combinations with repetition when order does not matter and objects can be chosen more than once
  • Example: Selecting a handful of candy from a bowl, where the order of selection does not matter and candies of the same type are indistinguishable
• In general, if the problem involves arranging or ranking, use permutations; if the problem involves selecting or grouping, use combinations

Common Pitfalls and How to Avoid Them

• Not distinguishing between permutations and combinations
  • Ask yourself if the order matters and if objects can be repeated
• Confusing $n$ and $r$ in the formulas
  • Remember that $n$ represents the total number of objects and $r$ represents the number of objects being selected or arranged
• Forgetting to account for repetition or indistinguishable objects
  • Pay attention to whether objects can be chosen more than once or if some objects are identical
• Overcounting or undercounting possibilities
  • Break the problem down into smaller parts and consider all possible cases
• Misinterpreting word problems
  • Carefully read the problem and identify the key information and constraints
• Not simplifying factorials before calculating
  • Cancel out common factors in the numerator and denominator to simplify the calculation
• Attempting to solve problems using brute force instead of formulas
  • Recognize patterns and use the appropriate formulas to save time and reduce errors

Real-World Applications

• Lottery and gambling probabilities
  • Example: Calculating the odds of winning a lottery jackpot
• Cryptography and password security
  • Example: Determining the strength of a password based on the number of possible combinations
• DNA sequencing and genetic analysis
  • Example: Estimating the number of possible DNA sequences of a given length
• Resource allocation and scheduling
  • Example: Assigning tasks to employees in different orders to optimize productivity
• Quality control and sampling
  • Example: Selecting a random sample of products to test for defects
• Sports and gaming strategies
  • Example: Analyzing the number of possible plays or moves in a game
• Marketing and product design
  • Example: Creating unique product configurations based on available options
• Logistics and transportation optimization
  • Example: Determining the most efficient route for a delivery truck to visit multiple locations

Practice Problems and Solutions

1. How many ways can 5 books be arranged on a shelf?

   • Solution: $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

2. In how many ways can a committee of 3 people be selected from a group of 10?

   • Solution: $C(10,3) = \frac{10!}{3!(10-3)!} = \frac{10!}{3!7!} = 120$

3. How many 4-digit PIN codes can be created using digits 0-9 if repetition is allowed?

   • Solution: $10^4 = 10,000$

4. How many ways can 5 people be seated around a circular table?

   • Solution: $(5-1)! = 4! = 24$

5. A box contains 5 red balls and 3 blue balls. In how many ways can 4 balls be selected if at least 2 must be red?

   • Solution: $C(5,2) \times C(6,2) + C(5,3) \times C(5,1) + C(5,4) = 10 \times 15 + 10 \times 5 + 5 = 205$

6. How many unique 5-character strings can be formed using the letters A, B, and C if repetition is allowed?

   • Solution: $3^5 = 243$

7. In how many ways can 6 identical pens be distributed among 4 people?

   • Solution: $\binom{6+4-1}{4-1} = \binom{9}{3} = 84$