🔢Enumerative Combinatorics Unit 2 – Permutations & Combinations

Permutations and combinations form the backbone of counting in mathematics. These concepts help us understand how to arrange and select objects in various ways, laying the groundwork for more advanced probability and statistical analysis. From basic counting principles to advanced techniques like generating functions, this unit covers a wide range of tools for solving complex counting problems. Understanding these concepts is crucial for applications in cryptography, scheduling, and data analysis.

Study Guides for Unit 2

2.1

Permutations without repetition

7 min read

2.2

Permutations with repetition

4 min read

2.3

Combinations without repetition

8 min read

2.4

Combinations with repetition

7 min read

2.5

Circular permutations

7 min read

2.6

Derangements

7 min read

Key Concepts

Permutations arrange objects in a specific order, considering the sequence of arrangement
Combinations select objects from a group without regard to the order, focusing on the selection itself
The fundamental counting principle multiplies the number of ways to perform independent tasks to find the total number of ways to perform all tasks together
Factorials (
```
n!
```
) calculate the product of all positive integers less than or equal to
```
n
```
, used extensively in permutation and combination formulas
The binomial coefficient $\binom{n}{k}$ $(k n)$ represents the number of ways to choose
```
k
```
objects from a set of
```
n
```
objects, calculated as $\frac{n!}{k!(n-k)!}$ $\frac{n !}{k ! ( n - k )!}$
- Also known as "n choose k" and written as $C(n,k)$ or $_nC_k$
Multinomial coefficients generalize binomial coefficients to count the number of ways to partition a set into multiple subsets of specified sizes
The inclusion-exclusion principle calculates the size of the union of multiple sets by subtracting the double-counted elements

Fundamental Counting Principles

The rule of sum states that if there are
```
n
```
ways to do one task and
```
m
```
ways to do another task, and these tasks cannot be done simultaneously, then there are
```
n + m
```
ways to do either task
The rule of product states that if there are
```
n
```
ways to do one task and
```
m
```
ways to do another task, and these tasks are independent, then there are
```
n × m
```
ways to do both tasks
The pigeonhole principle asserts that if
```
n
```
items are put into
```
m
```
containers, with
```
n > m
```
, then at least one container must contain more than one item
- Useful for proving the existence of certain configurations or arrangements
The principle of inclusion-exclusion calculates the size of the union of multiple sets by adding the sizes of individual sets, subtracting the sizes of pairwise intersections, adding the sizes of triple intersections, and so on
Permutations with repetition occur when objects can be chosen more than once, calculated as $n^r$ $n^{r}$ , where
```
n
```
is the number of objects and
```
r
```
is the number of choices

Permutations

A permutation is an ordered arrangement of objects, where the order matters
The number of permutations of
```
n
```
distinct objects is given by
```
n!
```
(factorial of
```
n
```
)
Permutations of
```
n
```
objects taken
```
r
```
at a time, denoted as $P(n,r)$ $P (n, r)$ or $_nP_r$ $_{n} P_{r}$ , is calculated as $\frac{n!}{(n-r)!}$ $\frac{n !}{( n - r )!}$
- Represents the number of ways to arrange
```
r
```
  objects from a set of
```
n
```
  objects in a specific order
Circular permutations arrange objects in a circle, where rotations are considered the same, calculated as $(n-1)!$ $(n - 1)!$ for
```
n
```
distinct objects
Permutations with indistinguishable objects use the formula $\frac{n!}{n_1!n_2!...n_k!}$ $\frac{n !}{n _{1} ! n _{2} ! ... n _{k} !}$ , where
```
n
```
is the total number of objects and $n_1, n_2, ..., n_k$ $n_{1}, n_{2}, ..., n_{k}$ are the numbers of indistinguishable objects of each type
Derangements are permutations where no object appears in its original position, calculated using the inclusion-exclusion principle or the formula $!n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}$

Combinations

A combination is a selection of objects from a group where the order does not matter
The number of combinations of
```
n
```
objects taken
```
r
```
at a time, denoted as $C(n,r)$ $C (n, r)$ or $\binom{n}{r}$ $(r n)$ , is calculated as $\frac{n!}{r!(n-r)!}$ $\frac{n !}{r ! ( n - r )!}$
- Represents the number of ways to select
```
r
```
  objects from a set of
```
n
```
  objects without regard to order
The binomial theorem expands powers of binomials using combinations, stated as $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$
Combinations with repetition allow objects to be chosen multiple times, calculated as $\binom{n+r-1}{r}$ $(r n + r - 1)$ or $\binom{n+r-1}{n-1}$ $(n - 1 n + r - 1)$ , where
```
n
```
is the number of objects and
```
r
```
is the number of choices
The hockey-stick identity relates the sum of consecutive combinations to a single combination, stated as $\sum_{i=r}^n \binom{i}{r} = \binom{n+1}{r+1}$
The Vandermonde identity expresses the product of two combinations as a sum of combinations, stated as $\binom{m+n}{r} = \sum_{k=0}^r \binom{m}{k} \binom{n}{r-k}$

Advanced Counting Techniques

The principle of inclusion-exclusion (PIE) calculates the size of the union of multiple sets by alternately adding and subtracting the sizes of intersections
- For two sets: $|A \cup B| = |A| + |B| - |A \cap B|$
- For three sets: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$
Generating functions represent sequences as coefficients of power series, used to solve counting problems
- Ordinary generating functions have the form $\sum_{n=0}^{\infty} a_n x^n$ $\sum_{n = 0}^{\infty} a_{n} x^{n}$ , where $a_n$ $a_{n}$ is the
```
n
```
  -th term of the sequence
- Exponential generating functions have the form $\sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ , used for problems involving labelled objects
The Stirling numbers of the first kind, denoted as $s(n,k)$ $s (n, k)$ , count the number of permutations of
```
n
```
objects with
```
k
```
cycles
The Stirling numbers of the second kind, denoted as $S(n,k)$ $S (n, k)$ , count the number of ways to partition a set of
```
n
```
objects into
```
k
```
non-empty subsets
Catalan numbers, denoted as $C_n$ , count various combinatorial structures, such as balanced parentheses, binary trees, and Dyck paths, calculated as $C_n = \frac{1}{n+1}\binom{2n}{n}$

Problem-Solving Strategies

Identify the type of counting problem (permutation, combination, or other) based on the problem statement
Determine if order matters and if repetition is allowed to choose between permutations and combinations
Break down complex problems into smaller, manageable subproblems that can be solved using fundamental counting principles
Use complementary counting to find the complement of the desired set, which may be easier to count, and then subtract from the total number of possibilities
Apply the binomial theorem to expand binomial expressions and find the coefficients of specific terms
Utilize generating functions to solve problems involving sequences or recurrence relations
- Multiply generating functions to account for independent choices
- Compose generating functions to handle dependent choices or constraints
Employ the principle of inclusion-exclusion to count the number of elements in the union of multiple sets, accounting for overlaps

Real-World Applications

Cryptography uses permutations and combinations to create secure encryption keys and analyze the strength of passwords
Lottery games and gambling rely on combinations to determine the odds of winning and calculate payouts
Scheduling problems, such as creating timetables or seating arrangements, often involve permutations to find the best possible configurations
Combinatorial design theory applies counting techniques to create efficient experimental designs, error-correcting codes, and tournament schedules
Computational biology uses permutations and combinations to analyze DNA sequences, study gene expression, and model population genetics
Machine learning and data analysis employ combinatorial methods to generate feature combinations and explore parameter spaces
Operations research utilizes counting principles to optimize resource allocation, transportation networks, and supply chain management

Common Pitfalls and Mistakes

Confusing permutations and combinations, leading to the use of incorrect formulas
- Remember: permutations consider order, while combinations do not
Failing to account for repetition or distinguishability of objects, resulting in over- or under-counting
Miscalculating factorials or binomial coefficients, especially for large numbers
- Use calculators or programming languages with built-in support for large integers
Neglecting to consider the constraints or dependencies between choices, leading to incorrect counts
Misapplying the principle of inclusion-exclusion by alternating signs incorrectly or omitting terms
Overlooking symmetry or overcounting equivalent configurations, particularly in problems involving circular or rotational symmetry
Misinterpreting problem statements or making unjustified assumptions about the given information
- Carefully read and understand the problem before attempting to solve it
Rushing to apply formulas without first understanding the underlying concepts and principles
- Take time to reason about the problem and identify the appropriate counting technique