Combinatorics Unit 2 Review: Permutations and Combinations

Key Concepts and Definitions

• Permutations arrange objects in a specific order, where the order matters and repetition is not allowed
• Combinations select objects from a group, where the order does not matter and repetition is not allowed
• The fundamental counting principle states that if there are $n_1$ ways to do something and $n_2$ ways to do another thing, then there are $n_1 \times n_2$ ways to do both things
• $n!$ represents the factorial of $n$, which is the product of all positive integers less than or equal to $n$ ($n! = n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1$)
  • For example, $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$
• The number of permutations of $n$ objects taken $r$ at a time is denoted as $P(n,r)$ or $nPr$ and is calculated using the formula $P(n,r) = \frac{n!}{(n-r)!}$
• 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 using the formula $C(n,r) = \frac{n!}{r!(n-r)!}$
  • This formula is also known as the binomial coefficient

Fundamental Counting Principle

• The fundamental counting principle is a basic rule in combinatorics that helps determine the total number of possible outcomes in a given situation
• It states that if there are $n_1$ ways to do something and $n_2$ ways to do another thing, then there are $n_1 \times n_2$ ways to do both things
• This principle can be extended to more than two events: if there are $n_1$ ways to do the first thing, $n_2$ ways to do the second thing, ..., and $n_k$ ways to do the $k$-th thing, then there are $n_1 \times n_2 \times ... \times n_k$ ways to do all $k$ things
• For example, if you have 3 shirts and 4 pairs of pants, there are $3 \times 4 = 12$ possible outfits
• The fundamental counting principle is the foundation for more complex counting techniques, such as permutations and combinations
• It is essential to identify when events are independent (the outcome of one event does not affect the outcome of another) to apply the fundamental counting principle correctly

Permutations: Theory and Applications

• A permutation is an arrangement of objects in a specific order, where the order matters and repetition is not allowed
• The number of permutations of $n$ objects taken $r$ at a time is denoted as $P(n,r)$ or $nPr$ and is calculated using the formula $P(n,r) = \frac{n!}{(n-r)!}$
  • For example, the number of ways to arrange 3 books on a shelf from a collection of 5 books is $P(5,3) = \frac{5!}{(5-3)!} = \frac{5!}{2!} = 60$
• When $r = n$, the formula simplifies to $P(n,n) = n!$, representing the number of ways to arrange all $n$ objects
• Permutations are used in various applications, such as determining the number of possible ways to:
  • Arrange people in a line (e.g., for a photo or a race)
  • Create a seating chart for a group of people
  • Order tasks or events in a specific sequence
• Circular permutations are a special case where objects are arranged in a circle, and the number of distinct permutations is $(n-1)!$ for $n$ objects
• Permutations with repetition allow objects to be repeated, and the number of such permutations is calculated using the formula $n^r$, where $n$ is the number of objects and $r$ is the number of positions

Combinations: Theory and Applications

• A combination is a selection of objects from a group, where the order does not matter and repetition is not allowed
• 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 using the formula $C(n,r) = \frac{n!}{r!(n-r)!}$
  • For example, the number of ways to choose 3 toppings from a list of 5 toppings for a pizza is $C(5,3) = \frac{5!}{3!(5-3)!} = \frac{5!}{3!2!} = 10$
• The formula for combinations is also known as the binomial coefficient because it appears in the binomial theorem
• Combinations are used in various applications, such as determining the number of possible ways to:
  • Form a committee from a group of people
  • Select a subset of items from a larger set (e.g., choosing toppings for a pizza or selecting cards from a deck)
  • Distribute objects among groups without considering the order
• Combinations with repetition allow objects to be repeated, and the number of such combinations is calculated using the formula $\binom{n+r-1}{r}$, where $n$ is the number of objects and $r$ is the number of positions
• The binomial theorem expresses the expansion of $(x + y)^n$ using binomial coefficients: $(x + y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$

Permutations vs. Combinations: When to Use Which

• Permutations and combinations are both counting techniques, but they are used in different situations depending on whether the order matters and whether repetition is allowed
• Use permutations when:
  • The order of the objects matters (e.g., arranging books on a shelf or creating a seating chart)
  • Repetition is not allowed (each object can only be used once)
• Use combinations when:
  • The order of the objects does not matter (e.g., selecting toppings for a pizza or forming a committee)
  • Repetition is not allowed (each object can only be used once)
• In some cases, you may need to use both permutations and combinations to solve a problem
  • For example, if you want to create a 4-digit PIN using numbers from 0 to 9, you would first use combinations to determine the number of ways to select 4 numbers from 10 (without repetition), and then use permutations to determine the number of ways to arrange those 4 numbers
• When repetition is allowed, use the appropriate formulas for permutations with repetition ($n^r$) or combinations with repetition ($\binom{n+r-1}{r}$)
• Always carefully read the problem statement to identify whether order matters and whether repetition is allowed to choose the appropriate counting technique

Advanced Topics and Special Cases

• Derangements are permutations where no object is in its original position, and the number of derangements of $n$ objects is denoted as $!n$ and can be calculated using the formula $!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$
• The inclusion-exclusion principle is a counting technique that helps determine the number of elements in the union of multiple sets, taking into account the overlaps between the sets
  • For two sets $A$ and $B$, the principle states that $|A \cup B| = |A| + |B| - |A \cap B|$
  • For three sets $A$, $B$, and $C$, the principle states that $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$
• The pigeonhole principle states that if you have $n$ items to put into $m$ containers, and $n > m$, then at least one container must contain more than one item
  • This principle is useful for proving the existence of certain configurations or arrangements without explicitly finding them
• Stirling numbers of the first kind, denoted as $s(n,k)$, count the number of permutations of $n$ objects with $k$ cycles
• Stirling numbers of the second kind, denoted as $S(n,k)$, count the number of ways to partition a set of $n$ objects into $k$ non-empty subsets
• The Catalan numbers, denoted as $C_n$, are a sequence of natural numbers that appear in various counting problems, such as the number of valid parentheses expressions with $n$ pairs of parentheses, and can be calculated using the formula $C_n = \frac{1}{n+1}\binom{2n}{n}$

Problem-Solving Strategies

• Identify the type of counting problem (permutation or combination) by determining whether the order matters and whether repetition is allowed
• Break down complex problems into smaller, more manageable sub-problems that can be solved using the fundamental counting principle, permutations, or combinations
• Use complementary counting when it is easier to count the number of ways an event does not occur and then subtract that from the total number of possible outcomes
• Look for symmetry in the problem to simplify the counting process
  • For example, if you need to arrange people around a circular table, you can fix one person's position and count the permutations of the remaining people, as all rotations of a particular arrangement are considered the same
• Consider using recursion or generating functions to solve more complex counting problems
• When solving problems involving permutations or combinations with repetition, be careful to correctly apply the appropriate formulas
• Double-check your work by verifying that the solution makes sense in the context of the problem and by testing it against small cases or known results

Real-World Applications

• Cryptography: Permutations and combinations are used in the design and analysis of cryptographic systems, such as determining the strength of passwords or the security of encryption algorithms
• Genetics: Combinations are used to calculate the probability of inheriting certain traits or genetic disorders based on the possible combinations of alleles from parents
• Lottery and gambling: Combinations are used to determine the probability of winning a lottery or the odds of certain events occurring in games of chance
• Quality control: Combinations are used in the design of experiments and sampling plans to ensure that products meet the required quality standards
• Resource allocation: Permutations and combinations are used in the optimization of resource allocation problems, such as assigning tasks to workers or distributing resources among different projects
• Scheduling: Permutations are used in the creation of schedules, such as determining the order of tasks in a project or the sequence of events in a conference
• Sports: Permutations and combinations are used in the analysis of sports statistics, such as calculating the number of possible ways a tournament bracket can be filled out or the likelihood of certain game outcomes
• Transportation: Permutations are used in the optimization of transportation networks, such as determining the best route for a delivery truck or the most efficient way to schedule flights