Permutations and Combinations

Permutations and Combinations

Permutations and combinations are fundamental concepts in combinatorics, which is the branch of mathematics focused on counting, arrangement, and selection. They are used to solve problems involving the arrangement and selection of objects.

1. Permutations

A permutation is an arrangement of objects in a specific order. When the order of the objects matters, we use permutations. The number of permutations of a set of objects depends on the total number of objects and whether or not repetition is allowed.

a. Permutations of $n$ distinct objects

The number of ways to arrange $n$ distinct objects in a sequence is called the factorial of $n$, denoted as $n!$.

The formula for $n!$ is:

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$

For example:

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

b. Permutations of $r$ objects from $n$ distinct objects (without repetition)

If we want to arrange $r$ objects out of $n$ distinct objects, the number of permutations is given by:

$$P(n, r) = \frac{n!}{(n - r)!}$$

Where:

• $P(n, r)$ is the number of ways to arrange $r$ objects from $n$ distinct objects,
• $n!$ is the factorial of $n$,
• $(n - r)!$ accounts for the unused objects.

Example: How many ways can you arrange 3 objects out of 5 distinct objects?

$$P(5, 3) = \frac{5!}{(5 - 3)!} = \frac{5!}{2!} = \frac{5 \times 4 \times 3 \times 2!}{2!} = 5 \times 4 \times 3 = 60$$

So, there are 60 ways to arrange 3 objects from 5 distinct objects.

c. Permutations with repetition

If repetition is allowed, the number of ways to arrange $r$ objects from $n$ distinct objects is:

$$P_{\text{with repetition}} = n^r$$

Where:

• $n^r$ represents the number of ways to choose each object from $n$ options $r$ times.

Example: How many ways can you form a 3-digit number if repetition of digits is allowed and the digits range from 0 to 9?

$$P_{\text{with repetition}} = 10^3 = 1000$$

So, there are 1000 possible 3-digit numbers.

---

2. Combinations

A combination is a selection of objects where the order does not matter. When the order is irrelevant, we use combinations to count the number of ways to choose $r$ objects from $n$ distinct objects.

a. Combinations of $r$ objects from $n$ distinct objects

The number of ways to choose $r$ objects from $n$ distinct objects (without regard to order) is given by the binomial coefficient:

$$C(n, r) = \frac{n!}{r!(n - r)!}$$

Where:

• $C(n, r)$ is the number of combinations,
• $n!$ is the factorial of $n$,
• $r!$ is the factorial of $r$,
• $(n - r)!$ accounts for the unused objects.

This formula counts the ways to choose $r$ objects from $n$ objects without considering the order of selection.

Example: How many ways can you choose 3 objects from a set of 5 distinct objects?

$$C(5, 3) = \frac{5!}{3!(5 - 3)!} = \frac{5!}{3!2!} = \frac{5 \times 4 \times 3!}{3! \times 2!} = \frac{5 \times 4}{2 \times 1} = 10$$

So, there are 10 ways to choose 3 objects from 5 distinct objects.

b. Combinations with repetition (multiset combinations)

If repetition of elements is allowed, the formula for combinations changes. The number of ways to choose $r$ objects from $n$ distinct objects, where repetition is allowed, is given by:

$$C_{\text{with repetition}}(n, r) = \frac{(n + r - 1)!}{r!(n - 1)!}$$

This is sometimes called the "stars and bars" formula, and it's used when you want to count the number of ways to distribute $r$ identical objects into $n$ distinct bins.

Example: How many ways can you choose 3 objects (with repetition allowed) from 5 distinct objects?

$$C_{\text{with repetition}}(5, 3) = \frac{(5 + 3 - 1)!}{3!(5 - 1)!} = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$$

So, there are 35 ways to choose 3 objects from 5 distinct objects if repetition is allowed.

---

3. Important Properties and Formulas

• Factorial properties:

  • $0! = 1$
  • $n! = n \times (n - 1)!$

• Symmetry property of combinations:

  $$C(n, r) = C(n, n - r)$$

  This means that choosing $r$ objects from $n$ objects is the same as choosing the remaining $n - r$ objects.

• Pascal's Triangle: The binomial coefficients $C(n, r)$ can be arranged in a triangular array, known as Pascal's Triangle, where each number is the sum of the two directly above it:

  $$C(n, r) = C(n - 1, r - 1) + C(n - 1, r)$$

  Pascal’s Triangle is helpful for quick reference and also for expanding binomials.

• Binomial Theorem: The binomial theorem gives the expansion of $(x + y)^n$:

  $$(x + y)^n = \sum_{r=0}^{n} C(n, r) x^{n-r} y^r$$

  This uses combinations to find the coefficients in the expansion.

---

4. Applications of Permutations and Combinations

1. Counting arrangements: Permutations are used to count how many ways objects can be arranged in order. This is useful in problems where order matters, such as seating arrangements, scheduling, and password generation.

2. Selecting groups: Combinations are used to count how many ways you can select a group of objects from a larger set, where the order does not matter. This is useful in problems like choosing committees, team selections, and lottery numbers.

3. Probability: Permutations and combinations are essential in probability theory. For example, they are used to calculate the probability of certain events in games of chance, like drawing cards from a deck or rolling dice.

4. Optimization problems: In optimization and game theory, permutations and combinations are used to find the best arrangement or selection out of many possibilities.

5. Discrete structures: In computer science, especially in algorithms and data structures, permutations and combinations are applied in areas such as hashing, cryptography, and network design.

---

5. Conclusion

Permutations and combinations are core concepts in combinatorics, providing methods to count the number of ways objects can be arranged or selected. Permutations are used when the order of selection matters, while combinations are used when the order is not important. These concepts have broad applications in various fields, including mathematics, computer science, probability, and optimization. Mastery of these techniques is essential for solving counting problems efficiently.