Combinations are a key concept in counting problems. They help us figure out how many ways we can select items from a group when the order doesn't matter. This is super useful in real-life situations, like picking team members or choosing pizza toppings.

Understanding combinations is crucial for tackling more complex probability and statistics problems. By mastering this concept, you'll be better equipped to analyze data, make predictions, and solve practical math problems in various fields, from business to science.

Combinations

Combinations without order

• Combinations select items from a collection where order does not matter
  • Selecting a team of 3 students from a class of 20 (Alice, Bob, Charlie is the same as Charlie, Alice, Bob)
  • Choosing 2 toppings from 5 options for a pizza (pepperoni and mushroom is the same as mushroom and pepperoni)
• Denoted as $C(n,r)$ or $\binom{n}{r}$ where:
  • $n$ is the total number of items in the set
  • $r$ is the number of items being selected
• Formula for combinations: $C(n,r) = \frac{n!}{r!(n-r)!}$
  • $n!$ is the factorial of $n$, the product of all positive integers less than or equal to $n$ ($5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$)
  • $r!$ is the factorial of $r$
  • $(n-r)!$ is the factorial of $n-r$
• To calculate combinations:
  1. Identify the total items $n$ and the number to select $r$
  2. Plug $n$ and $r$ into the formula $\frac{n!}{r!(n-r)!}$
  3. Simplify the factorials and calculate the result
• Example: Selecting 2 fruits from a basket of 5 fruits
  • $n = 5$ (total fruits) and $r = 2$ (fruits selected)
  • $C(5,2) = \frac{5!}{2!(5-2)!} = \frac{5!}{2!3!} = \frac{5 \cdot 4 \cdot 3!}{2 \cdot 1 \cdot 3!} = 10$
  • There are 10 ways to select 2 fruits from 5 fruits where order doesn't matter
• Combinations are fundamental to set theory, as they help determine the number of subsets of a given size from a larger set

Permutations vs combinations

• Permutations consider the order of selection, combinations do not
  • Permutation: Arranging the letters A, B, C (ABC, ACB, BAC, BCA, CAB, CBA are all different)
  • Combination: Selecting 2 toppings from cheese, pepperoni, mushroom (cheese and pepperoni is the same as pepperoni and cheese)
• Use permutations when:
  • Order matters
  • Each item is distinct and used only once
  • Arranging books on a shelf (Moby Dick then Huckleberry Finn is different than Huckleberry Finn then Moby Dick)
• Use combinations when:
  • Order does not matter
  • Items are not distinct or can be used multiple times
  • Selecting 3 toppings for a pizza from 8 options (mushroom, pepperoni, olive is the same as olive, mushroom, pepperoni)
• To decide between permutations and combinations:
  1. Determine if order matters
  2. Check if items are distinct or can be repeated
• Example: Making a 4-digit PIN code using digits 0-9
  • Order matters (1234 is a different PIN than 4321)
  • Digits can be repeated (1111 is a valid PIN)
  • This requires permutations with repetition, not combinations

Applications of combination formula

1. Identify the total items $n$ and number to select $r$
2. Substitute $n$ and $r$ into the formula $\frac{n!}{r!(n-r)!}$
3. Simplify factorials by canceling common terms in numerator and denominator
4. Calculate the final result to get the number of combinations

• Example: A sundae bar has 10 toppings. How many 4-topping sundaes are possible?
  • $n = 10$ toppings total, $r = 4$ toppings per sundae
  • $C(10,4) = \frac{10!}{4!(10-4)!} = \frac{10!}{4!6!}$
  • $\frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6!}{4 \cdot 3 \cdot 2 \cdot 1 \cdot 6!} = 210$
  • There are 210 different ways to make a 4-topping sundae from 10 toppings
• Example: A jury of 12 must be selected from 50 candidates. How many possible juries are there?
  • $n = 50$ candidates, $r = 12$ jurors
  • $C(50,12) = \frac{50!}{12!(50-12)!} = \frac{50!}{12!38!} \approx 1.24 \times 10^{10}$
  • There are approximately $1.24 \times 10^{10}$ possible 12-person juries from 50 candidates
• Combinations are essential in probability calculations, especially when determining the number of ways to select a sample from a larger population

Combinatorics and Counting Principles

• Combinatorics is the branch of mathematics dealing with counting, arrangement, and combination of objects
• The fundamental counting principle states that if one event can occur in m ways, and another independent event can occur in n ways, then the two events can occur together in m × n ways
• Sampling techniques in statistics often rely on combinations to determine the number of possible samples from a population
• Combinations play a crucial role in various fields, including probability theory and statistical analysis