Mathematics: Class 11 — Chapter 6: Permutations and Combinations

The fundamental principle of counting is stated as follows:

"If an event can occur in $m$ different ways, following which another event can occur in $n$ different ways, then the total number of occurrence of the events in the given order is $m \times n$."

Generalization to $k$ Events: If an event $E_1$ can occur in $n_1$ ways, followed by $E_2$ in $n_2$ ways, followed by $E_3$ in $n_3$ ways, and so on up to $E_k$ in $n_k$ ways, then the total number of ways the sequence of events can occur is:

Mathematical Problem Statement: Mohan has $3$ pants and $2$ shirts. How many different pairs of a pant and a shirt can he dress up with?

---

Step-by-Step Algorithmic Solution Trace:

1. Identify the first event: Choosing a pant. There are $3$ available options, so $m = 3$.
2. Identify the second event: Choosing a shirt. There are $2$ available options, so $n = 2$.
3. Apply the multiplication principle: Total pairs = $m \times n = 3 \times 2$.

Final Evaluation Output: $6$ pairs

Mathematical Problem Statement: Find the number of $4$-letter words, with or without meaning, which can be formed out of the letters of the word ROSE, where the repetition of the letters is not allowed.

---

Step-by-Step Algorithmic Solution Trace:

1. There are $4$ vacant places to be filled by the $4$ distinct letters: R, O, S, E.
2. The first place can be filled in $4$ different ways by any of the $4$ letters.
3. Since repetition is not allowed, the second place can be filled in $3$ different ways by any of the remaining $3$ letters.
4. The third place can be filled in $2$ different ways.
5. The fourth place can be filled in $1$ way.
6. By the multiplication principle, the total number of ways is $4 \times 3 \times 2 \times 1$.

Final Evaluation Output: $24$ words

Mathematical Problem Statement: How many $2$-digit even numbers can be formed from the digits $1, 2, 3, 4, 5$ if the digits can be repeated?

---

Step-by-Step Algorithmic Solution Trace:

1. A $2$-digit number has a unit's place and a ten's place.
2. For the number to be even, the unit's place must be filled with an even digit. From the set $\{1, 2, 3, 4, 5\}$, the even digits are $2$ and $4$. Thus, the unit's place can be filled in $2$ ways.
3. Since repetition of digits is allowed, the ten's place can be filled by any of the $5$ given digits in $5$ ways.
4. By the multiplication principle, the total number of even numbers is $5 \times 2$.

Final Evaluation Output: $10$ even numbers

The notation $n!$ (read as n factorial) represents the product of the first $n$ natural numbers:

Core Properties of Factorials:

• $0! = 1$ (by definition)
• $1! = 1$
• $n! = n \times (n-1)!$
• $n! = n \times (n-1) \times (n-2)!$ for $n \ge 2$

Theorem 1: The number of permutations of $n$ different objects taken $r$ at a time, where $0 < r \le n$ and the objects do not repeat, is denoted by $^nP_r$ and is given by:

Multiplying the numerator and denominator by $(n-r)!$, we obtain the standard factorial formula:

Theorem 2: The number of permutations of $n$ different objects taken $r$ at a time, where repetition is allowed, is:

Theorem 3: The number of permutations of $n$ objects, where $p$ objects are of the same kind and the rest are all different, is:

Theorem 4: The number of permutations of $n$ objects, where $p_1$ objects are of one kind, $p_2$ are of a second kind, ..., $p_k$ are of a $k$-th kind, and the rest (if any) are of different kinds, is:

Mathematical Problem Statement: Find the number of permutations of the letters of the word ALLAHABAD.

---

Step-by-Step Algorithmic Solution Trace:

1. Count the total number of letters in ALLAHABAD: $n = 9$.
2. Identify the repeating letters and their frequencies:
   • Letter 'A' appears $4$ times ($p_1 = 4$).
   • Letter 'L' appears $2$ times ($p_2 = 2$).
   • The remaining letters (H, B, D) are distinct and appear $1$ time each.
3. Apply Theorem 4: Total arrangements = $\frac{9!}{4! \times 2!}$.
4. Calculate the value:$$\frac{9 \times 8 \times 7 \times 6 \times 5 \times 4!}{4! \times 2} = \frac{15120}{2} = 7560$$

Final Evaluation Output: $7560$ arrangements

Mathematical Problem Statement: How many numbers lying between $100$ and $1000$ can be formed with the digits $0, 1, 2, 3, 4, 5$, if the repetition of the digits is not allowed?

---

Step-by-Step Algorithmic Solution Trace:

1. Every number between $100$ and $1000$ is a $3$-digit number.
2. The total number of permutations of $6$ distinct digits taken $3$ at a time is:$$^6P_3 = \frac{6!}{(6-3)!} = 6 \times 5 \times 4 = 120$$
3. However, this includes numbers where $0$ is at the $100$'s place (which makes them $2$-digit numbers).
4. To find the number of such invalid configurations, fix $0$ at the $100$'s place. The remaining $2$ places must be filled using the remaining $5$ digits:$$^5P_2 = \frac{5!}{(5-2)!} = 5 \times 4 = 20$$
5. Subtract the invalid configurations from the total permutations:$$\text{Required Numbers} = ^6P_3 - ^5P_2 = 120 - 20 = 100$$

Final Evaluation Output: $100$ numbers

The number of combinations of $n$ different objects taken $r$ at a time is denoted by $^nC_r$ and is given by:

Theorem 5 (Relation between $^nP_r$ and $^nC_r$):

• Symmetric Property: Selecting $r$ objects is equivalent to rejecting $(n-r)$ objects:$$^nC_r = ^nC_{n-r}$$
• Equality Condition: If $^nC_a = ^nC_b$, then either:$$a = b \quad \text{or} \quad n = a + b$$
• Theorem 6 (Pascal's Identity):$$^nC_r + ^nC_{r-1} = ^{n+1}C_r$$
• Boundary Values:$$^nC_0 = 1, \quad ^nC_n = 1$$

Mathematical Problem Statement: If $^nC_9 = ^nC_8$, find $^nC_{17}$.

---

Step-by-Step Algorithmic Solution Trace:

1. Use the equality condition $^nC_a = ^nC_b \implies n = a + b$ (since $9 \neq 8$).
2. Calculate $n$:$$n = 9 + 8 = 17$$
3. Substitute $n = 17$ into the target expression $^nC_{17}$:$$^{17}C_{17} = 1$$

Final Evaluation Output: $1

Mathematical Problem Statement: A committee of $3$ persons is to be constituted from a group of $2$ men and $3$ women. In how many ways can this be done? How many of these committees would consist of $1$ man and $2$ women?

---

Step-by-Step Algorithmic Solution Trace:

1. Part 1: Total ways to form the committee
   • Total number of people = $2 \text{ men} + 3 \text{ women} = 5$ people.
   • We need to select $3$ people out of $5$. Since order does not matter, use combinations:$$^5C_3 = \frac{5!}{3!2!} = \frac{5 \times 4}{2} = 10$$
2. Part 2: Committee with $1$ man and $2$ women
   • Select $1$ man from $2$ available men: $^2C_1 = 2$ ways.
   • Select $2$ women from $3$ available women: $^3C_2 = ^3C_1 = 3$ ways.
   • By the multiplication principle, the total number of such committees is:$$^2C_1 \times ^3C_2 = 2 \times 3 = 6$$

Final Evaluation Output: Total committees = $10$; Committees with $1$ man and $2$ women = $6$

Mathematical Problem Statement: Find the $50$-th word if all permutations of the letters of the word AGAIN are arranged as in a dictionary.

---

Step-by-Step Algorithmic Solution Trace:

1. The letters of AGAIN in alphabetical order are: A, A, G, I, N.
2. Words starting with A: Fix A at the first position. Arrange the remaining letters (A, G, I, N):$$\text{Number of words} = 4! = 24$$
3. Words starting with G: Fix G at the first position. Arrange the remaining letters (A, A, I, N):$$\text{Number of words} = \frac{4!}{2!} = 12$$Cumulative total = $24 + 12 = 36$.
4. Words starting with I: Fix I at the first position. Arrange the remaining letters (A, A, G, N):$$\text{Number of words} = \frac{4!}{2!} = 12$$Cumulative total = $36 + 12 = 48$.
5. Words starting with N: The next words will start with N.
   • The $49$-th word (first word starting with N alphabetically): NAAGI
   • The $50$-th word (next alphabetical word): NAAIG

Final Evaluation Output: NAAIG

Mathematical Problem Statement: In how many ways can $5$ girls and $3$ boys be seated in a row so that no two boys are together?

---

Step-by-Step Algorithmic Solution Trace:

1. First, seat the $5$ girls in a row. This can be done in:$$5! = 120 \text{ ways}$$
2. This arrangement creates $6$ potential gaps (including the ends) where boys can be seated:$$\times \text{ G } \times \text{ G } \times \text{ G } \times \text{ G } \times \text{ G } \times$$
3. Select $3$ gaps out of the $6$ available gaps and arrange the $3$ boys in them:$$^6P_3 = \frac{6!}{(6-3)!} = 6 \times 5 \times 4 = 120 \text{ ways}$$
4. By the multiplication principle, the total number of seating arrangements is:$$\text{Total Ways} = 5! \times ^6P_3 = 120 \times 120 = 14400$$

Final Evaluation Output: $14400$ ways