I want everything on permutation and combination

Factorials

Before diving into permutations and combinations, it's essential to understand factorials.
The factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$.

$$n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1$$

By definition, $0! = 1$.

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

Permutations

Permutations refer to the arrangement of objects where the order matters. If you change the order of the objects, it's considered a different permutation.

1. Permutations of $n$ distinct objects taken $r$ at a time

The number of permutations of $n$ distinct objects taken $r$ at a time is given by the formula:

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

Example 1: Arranging a subset
How many ways can you arrange 3 different books on a shelf from a selection of 5 different books?

Here, $n=5$ (total books) and $r=3$ (books to arrange).

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

There are 60 ways to arrange the books.

2. Permutations of $n$ distinct objects taken $n$ at a time

This is a special case where $r=n$. The formula simplifies to:

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

Example 2: Arranging all objects
How many different ways can the letters of the word "MATH" be arranged?

Here, $n=4$ (total letters) and $r=4$ (all letters are used).

$$P(4, 4) = 4! = 4 \times 3 \times 2 \times 1 = 24$$

There are 24 different arrangements.

3. Permutations with Repetition (Identical Objects)

If there are $n$ objects where $n_1$ are of one type, $n_2$ are of a second type, ..., $n_k$ are of a $k$-th type, and $n_1 + n_2 + \dots + n_k = n$, then the number of distinct permutations is:

$$\frac{n!}{n_1! n_2! \dots n_k!}$$

Example 3: Arranging letters with repetition
How many distinct arrangements can be made from the letters of the word "MISSISSIPPI"?

Here, $n=11$ (total letters).
M: 1 ($n_1=1$)
I: 4 ($n_2=4$)
S: 4 ($n_3=4$)
P: 2 ($n_4=2$)

Number of distinct arrangements = $\frac{11!}{1! 4! 4! 2!} = \frac{39,916,800}{1 \times 24 \times 24 \times 2} = \frac{39,916,800}{1152} = 34,650$
There are 34,650 distinct arrangements.

Combinations

Combinations refer to the selection of objects where the order does not matter. If you select a group of objects, changing the order in which you picked them does not create a new combination.

1. Combinations of $n$ distinct objects taken $r$ at a time

The number of combinations of $n$ distinct objects taken $r$ at a time is given by the formula:

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

Note that $C(n, r) = \frac{P(n, r)}{r!}$. This shows that for every $r!$ permutations, there is only 1 combination.

Example 4: Selecting a committee
A committee of 3 people is to be chosen from a group of 7 people. How many different committees can be formed?

Here, $n=7$ (total people) and $r=3$ (people to choose). The order of selection does not matter for a committee.

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

There are 35 different committees that can be formed.

Example 5: Selecting items from a menu
A student needs to choose 2 subjects from a list of 4 optional subjects. How many ways can the student choose the subjects?

Here, $n=4$ (total subjects) and $r=2$ (subjects to choose). The order of choosing subjects does not matter.

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

There are 6 ways to choose the subjects.

Key Difference: Order Matters vs. Order Does Not Matter

• Permutations: Use when the order or arrangement of the selected items is important (e.g., arranging books, forming a password, assigning positions).
• Combinations: Use when only the selection or group of items is important, and their order does not change the outcome (e.g., choosing a committee, selecting lottery numbers, picking cards).