# 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.