2.4 Permutation and combination

Detailed Theory: Permutations and Combinations

1. Fundamental Principles of Counting

1.1 Addition Principle (Rule of Sum)

If an event can occur in $m$ ways and another independent event can occur in $n$ ways, then either event can occur in $m + n$ ways.

Example: If there are 3 different shirts and 4 different pants in your wardrobe, and you want to wear either a shirt OR pants, you have:

$3 + 4 = 7$ choices

1.2 Multiplication Principle (Rule of Product)

If one event can occur in $m$ ways, and after it occurs, a second event can occur in $n$ ways, then both events can occur in $m \times n$ ways.

Example: If there are 3 different shirts and 4 different pants, and you want to wear a shirt AND pants, you have:

$3 \times 4 = 12$ different outfits

1.3 Comparison: AND vs OR

• AND means multiply (Rule of Product)

• OR means add (Rule of Sum)

Important: The OR case requires that the events are mutually exclusive (they cannot happen together).

---

2. Factorial Notation

2.1 Definition

For a positive integer $n$, factorial $n$ is:

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

Examples:

$1! = 1$

$2! = 2 \times 1 = 2$

$3! = 3 \times 2 \times 1 = 6$

$4! = 4 \times 3 \times 2 \times 1 = 24$

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

2.2 Special Cases

By definition:

$0! = 1$

This is a convention that makes many formulas work correctly.

2.3 Properties

1. $n! = n \times (n-1)!$

2. $\frac{n!}{(n-1)!} = n$

3. $\frac{n!}{(n-r)!} = n(n-1)(n-2)\cdots(n-r+1)$

Example: Calculate $\frac{7!}{4!}$

$\frac{7!}{4!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{4 \times 3 \times 2 \times 1} = 7 \times 6 \times 5 = 210$

---

3. Permutations

3.1 Definition

A permutation is an arrangement of objects in a specific order.

Key idea: Order matters!

3.2 Permutations of Distinct Objects

The number of permutations of $n$ distinct objects taken $r$ at a time is:

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

Alternative notation: $^nP_r$ or $_nP_r$

Special Cases:

When $r = n$: $P(n, n) = n!$ (all objects arranged)

When $r = 0$: $P(n, 0) = 1$ (one way: empty arrangement)

3.3 Important Results

1. $P(n, n) = n!$

2. $P(n, 1) = n$

3. $P(n, n-1) = n!$

4. $P(n, r) = n \times P(n-1, r-1)$

3.4 Solved Examples

Example 1: How many 3-letter codes can be formed using letters A, B, C, D without repetition?

Solution:

We need permutations of 4 letters taken 3 at a time:

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

Example 2: In how many ways can 5 people sit in a row of 5 chairs?

Solution:

This is permutation of all 5 people:

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

Example 3: How many 4-digit numbers can be formed using digits 1, 2, 3, 4, 5 without repetition?

Solution:

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

---

4. Permutations with Restrictions

4.1 Permutations with Repetition

The number of permutations of $n$ objects where some objects are identical:

If there are $n$ objects with $p$ alike of one kind, $q$ alike of second kind, $r$ alike of third kind, etc., then:

Number of permutations = $\frac{n!}{p! \times q! \times r! \times \cdots}$

Example: How many different words can be formed using letters of "MISSISSIPPI"?

Solution:

Word: MISSISSIPPI Total letters: $n = 11$

M: appears 1 time I: appears 4 times S: appears 4 times P: appears 2 times

Number of permutations = $\frac{11!}{1! \times 4! \times 4! \times 2!}$

$= \frac{39916800}{1 \times 24 \times 24 \times 2} = \frac{39916800}{1152} = 34650$

4.2 Circular Permutations

When objects are arranged in a circle, arrangements that can be rotated into each other are considered the same.

Number of circular permutations of $n$ distinct objects = $(n-1)!$

Reason: Fix one object's position to eliminate rotations.

Example: In how many ways can 5 people sit around a circular table?

Solution:

Number of ways = $(5-1)! = 4! = 24$

4.3 Permutations with Conditions

a) Objects always together

Treat the objects that must be together as a single "block".

Example: In how many ways can 5 people be arranged if 2 specific people must sit together?

Solution:

Treat the 2 people as one block. Now we have 4 items to arrange (block + 3 other people).

Arrange 4 items: $4! = 24$ ways

Within the block, the 2 people can switch places: $2! = 2$ ways

Total arrangements = $4! \times 2! = 24 \times 2 = 48$

b) Objects never together

Total arrangements without restrictions - arrangements with them together

Example: In how many ways can 5 people be arranged if 2 specific people must NOT sit together?

Solution:

Total arrangements of 5 people = $5! = 120$

Arrangements with them together (from previous example) = $48$

Arrangements with them NOT together = $120 - 48 = 72$

---

5. Combinations

5.1 Definition

A combination is a selection of objects without regard to order.

Key idea: Order does NOT matter!

5.2 Combinations Formula

The number of combinations of $n$ distinct objects taken $r$ at a time is:

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

Alternative notations: $^nC_r$, $_nC_r$, or $\binom{n}{r}$

5.3 Relationship between Permutations and Combinations

$P(n, r) = C(n, r) \times r!$

This makes sense because:

1. First select $r$ objects: $C(n, r)$ ways

2. Then arrange them: $r!$ ways

3. Total permutations = selection × arrangement

5.4 Important Properties of Combinations

1. $C(n, 0) = 1$ (one way to select nothing)

2. $C(n, 1) = n$ (n ways to select one object)

3. $C(n, n) = 1$ (one way to select all objects)

4. $C(n, r) = C(n, n-r)$ (complementary combinations)

5. $C(n, r) + C(n, r-1) = C(n+1, r)$ (Pascal's rule)

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

5.5 Solved Examples

Example 1: How many ways to choose 3 students from a class of 10?

Solution:

Order doesn't matter, so combination:

$C(10, 3) = \frac{10!}{3!(10-3)!} = \frac{10!}{3! \times 7!}$

$= \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

Example 2: A committee of 5 is to be formed from 6 men and 4 women. In how many ways can this be done?

Solution:

No restrictions, just choose 5 from 10:

$C(10, 5) = \frac{10!}{5! \times 5!} = \frac{10 \times 9 \times 8 \times 7 \times 6}{5 \times 4 \times 3 \times 2 \times 1} = 252$

Example 3: In the previous example, if the committee must have 3 men and 2 women, how many ways?

Solution:

Choose 3 men from 6: $C(6, 3) = \frac{6!}{3! \times 3!} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$

Choose 2 women from 4: $C(4, 2) = \frac{4!}{2! \times 2!} = \frac{4 \times 3}{2 \times 1} = 6$

Total ways = $20 \times 6 = 120$

---

6. Important Combinatorial Identities

6.1 Basic Identities

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

2. $C(n, 0) + C(n, 1) + C(n, 2) + \cdots + C(n, n) = 2^n$

3. $C(n, 0) - C(n, 1) + C(n, 2) - C(n, 3) + \cdots = 0$

4. $C(n, r) = \frac{n}{r} \times C(n-1, r-1)$

5. $C(n, r) = \frac{n-r+1}{r} \times C(n, r-1)$

6.2 Pascal's Triangle

Pascal's triangle gives binomial coefficients $C(n, r)$:

Row 0: 1 Row 1: 1 1 Row 2: 1 2 1 Row 3: 1 3 3 1 Row 4: 1 4 6 4 1 Row 5: 1 5 10 10 5 1

Property: Each number is sum of two numbers above it: $C(n, r) = C(n-1, r-1) + C(n-1, r)$

6.3 Vandermonde's Identity

$C(m+n, r) = \sum_{k=0}^{r} C(m, k) \times C(n, r-k)$

Special case: When $m = n = r$:

$C(2n, n) = \sum_{k=0}^{n} [C(n, k)]^2$

---

7. Applications to Probability

7.1 Basic Probability Formula

Probability of an event = $\frac{\text{Number of favorable outcomes}}{\text{Total number of possible outcomes}}$

7.2 Examples Using Combinations

Example 1: What is probability of getting exactly 2 heads when tossing 3 coins?

Solution:

Total outcomes: Each coin has 2 possibilities, so $2^3 = 8$

Favorable outcomes: Exactly 2 heads = select which 2 coins show heads:

Number of ways = $C(3, 2) = 3$

Probability = $\frac{3}{8}$

Example 2: From a deck of 52 cards, what is probability of getting 2 aces when drawing 5 cards?

Solution:

Total ways to draw 5 cards: $C(52, 5)$

Ways to get exactly 2 aces:

• Choose 2 aces from 4: $C(4, 2)$

• Choose 3 non-aces from 48: $C(48, 3)$

Favorable outcomes = $C(4, 2) \times C(48, 3)$

Probability = $\frac{C(4, 2) \times C(48, 3)}{C(52, 5)}$

---

8. Selection with Restrictions

8.1 Selection from Identical Objects

When selecting from identical objects, there's only 1 way to select any number.

Example: In how many ways can you select 3 balls from 5 identical red balls?

Solution: Only 1 way (they're identical)

8.2 Selection with Repetition Allowed

Number of ways to select $r$ objects from $n$ distinct objects when repetition is allowed:

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

Example: How many ways to buy 3 ice creams from 5 flavors if you can get multiple of same flavor?

Solution:

$n = 5$ (flavors), $r = 3$ (ice creams)

Number of ways = $C(5 + 3 - 1, 3) = C(7, 3) = 35$

8.3 Distribution Problems

a) Distinct objects into distinct boxes

Number of ways to distribute $n$ distinct objects into $r$ distinct boxes:

$r^n$ (each object can go to any box)

Example: In how many ways can 3 different books be given to 5 students?

Solution:

Each book can go to any of 5 students: $5^3 = 125$

b) Identical objects into distinct boxes

Number of ways to distribute $n$ identical objects into $r$ distinct boxes:

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

Example: In how many ways can 10 identical chocolates be distributed among 4 children?

Solution:

$n = 10$, $r = 4$

Number of ways = $C(10 + 4 - 1, 4 - 1) = C(13, 3) = 286$

---

9. Derangements

9.1 Definition

A derangement is a permutation where no object appears in its original position.

Example: For 3 letters A, B, C: Original: A B C Derangements: B C A, C A B (Not a derangement: A C B because A is in original position)

9.2 Formula for Derangements

Number of derangements of $n$ objects (denoted $!n$ or $D_n$):

$D_n = n! \left[1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!}\right]$

First few values: $D_1 = 0$ $D_2 = 1$ $D_3 = 2$ $D_4 = 9$ $D_5 = 44$

9.3 Recurrence Relation

$D_n = (n-1)[D_{n-1} + D_{n-2}]$ for $n \geq 2$

With $D_0 = 1$, $D_1 = 0$

Example: 4 letters are put into 4 envelopes at random. What is probability that no letter goes to correct envelope?

Solution:

Total arrangements: $4! = 24$

Derangements for 4: $D_4 = 9$

Probability = $\frac{9}{24} = \frac{3}{8}$

---

10. Multinomial Theorem

10.1 Binomial Theorem Review

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

10.2 Multinomial Theorem

For positive integer $n$:

$(x_1 + x_2 + \cdots + x_k)^n = \sum \frac{n!}{n_1! n_2! \cdots n_k!} x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}$

where the sum is over all non-negative integers $n_1, n_2, \ldots, n_k$ such that $n_1 + n_2 + \cdots + n_k = n$

10.3 Multinomial Coefficients

The coefficient $\frac{n!}{n_1! n_2! \cdots n_k!}$ is called a multinomial coefficient.

Example: Find coefficient of $x^2 y z^2$ in $(x + y + z)^5$

Solution:

Here $n = 5$, we need $x^2 y^1 z^2$

Coefficient = $\frac{5!}{2! \times 1! \times 2!} = \frac{120}{2 \times 1 \times 2} = \frac{120}{4} = 30$

---

11. Important Solved Examples

Example 1: Committee Formation

From 7 men and 5 women, form a committee of 6 with at least 3 women.

Solution:

Case 1: 3 women, 3 men Ways = $C(5, 3) \times C(7, 3) = 10 \times 35 = 350$

Case 2: 4 women, 2 men Ways = $C(5, 4) \times C(7, 2) = 5 \times 21 = 105$

Case 3: 5 women, 1 man Ways = $C(5, 5) \times C(7, 1) = 1 \times 7 = 7$

Total ways = $350 + 105 + 7 = 462$

Example 2: Word Formation

How many words can be formed from "BANANA" with B and N together?

Solution:

Treat "BN" as one block. Letters: Block, A, A, A, N

Total letters to arrange = 5 with 3 A's alike

Ways = $\frac{5!}{3!} = \frac{120}{6} = 20$

Within block, B and N can switch: $2! = 2$ ways

Total words = $20 \times 2 = 40$

Example 3: Handshake Problem

In a party with 10 people, if each person shakes hands with every other person, how many handshakes?

Solution:

Each handshake involves 2 people. So number of handshakes = $C(10, 2) = 45$

Example 4: Path Counting**

In a grid, how many paths from bottom-left to top-right moving only right or up?

Solution:

If grid is $m \times n$, need $m$ right moves and $n$ up moves.

Total moves = $m + n$ moves with $m$ R's and $n$ U's

Number of paths = $\frac{(m+n)!}{m! \times n!} = C(m+n, m) = C(m+n, n)$

For $3 \times 4$ grid: $C(7, 3) = C(7, 4) = 35$

---

12. Common Mistakes and Exam Tips

12.1 Common Mistakes

1. Confusing permutation and combination: Ask: "Does order matter?"

2. Overcounting: When objects are identical, division is needed

3. Undercounting: For "at least" problems, consider all cases

4. Circular permutations: Remember $(n-1)!$ not $n!$

5. Derangements: Use formula, not intuition

12.2 Problem-Solving Strategy

1. Identify the type: Selection or arrangement? Order matters or not?

2. Check restrictions: Always together, never together, at least, at most, etc.

3. Break into cases: When multiple conditions, use cases

4. Use formulas correctly: Know when to use $P(n,r)$ vs $C(n,r)$

5. Verify answer: Check if number seems reasonable

12.3 Quick Reference

• Arrangement/Order matters: Permutations

• Selection/Order doesn't matter: Combinations

• Identical objects: Divide by factorial of identical counts

• Circular arrangement: $(n-1)!$

• At least problems: Consider all cases or use complement

• Never together: Total - together

12.4 Important Formulas to Memorize

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

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

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

4. Circular permutations: $(n-1)!$

5. Permutations with identical objects: $\frac{n!}{p!q!r!\cdots}$

6. Combinations with repetition: $C(n+r-1, r)$

This comprehensive theory covers all aspects of permutations and combinations with detailed explanations and examples, providing complete preparation for the entrance examination.