Fundamental Principles of Permutations and Combinations

Fundamental Principle of Counting

The Fundamental Principle of Counting (FPC) is used to determine the number of ways an event can occur without physically listing every possibility. It consists of two primary rules: the Principle of Multiplication and the Principle of Addition.

Fundamental Principle of Multiplication (Product Rule)

If there are two jobs $J_1$ and $J_2$ such that $J_1$ can be completed in $m$ ways, and when it has been completed in any of these $m$ ways, the second job $J_2$ can be completed in $n$ ways, then the two jobs in succession can be completed in $m \times n$ ways.

• Explanation: For each of the $m$ ways to perform the first job, there are $n$ ways to perform the second. Totaling these results in $m \times n$.

• Illustration: In a class with $10$ boys and $8$ girls, if a teacher selects one boy and one girl to represent the class, the selection can be made in $10 \times 8 = 80$ ways.

• Extension: This principle extends to any finite number of jobs.

Fundamental Principle of Addition (Sum Rule)

If there are two jobs $J_1$ and $J_2$ such that $J_1$ can be performed independently in $m$ ways and $J_2$ can be performed independently in $n$ ways, then either of the two jobs ($J_1$ or $J_2$) can be performed in $m + n$ ways.

• Illustration: In a class with $10$ boys and $8$ girls, if a teacher selects either a boy or a girl to represent the class, the selection can be made in $10 + 8 = 18$ ways.

Comparison of Principles

• Principle of Multiplication: A job is decomposed into sub-jobs that are unconnected; the full job is performed only when each sub-job is completed.

• Principle of Addition: There are multiple independent jobs, and the goal is to perform exactly one of them.

Practical Models and Counting Procedures

Basic Counting Models

• Town Travel (Model - I): To travel from Town 1 ($T_1$) to Town 3 ($T_3$) via Town 2 ($T_2$), if there are $3$ ways from $T_1$ to $T_2$ and $2$ ways from $T_2$ to $T_3$, the total ways are $3 \times 2 = 6$.

• Cinema Hall (Model - II):

  • Entering and leaving by a different door (total $5$ doors): $5 \times 4 = 20$ ways.

  • Entering and leaving by any door: $5 \times 5 = 25$ ways.

Steps to Solve Counting Problems

1. Identify the independent events involved.

2. Find the number of ways to perform each event.

3. Multiply these values to determine the total number of ways for all events to occur.

Factorial Notation and Special Results

Definition of Factorial

The continued product of the first $n$ natural numbers is called "n factorial" and is denoted as $n!$ or $\lfloor n$.

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

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

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

• $5! = 120$

• $6! = 720$

• $7! = 5040$

• Special Result: $0! = 1$

Solved Factorial Equations

• Example 1: Find $n$ if $(n+1)! = 12 \times (n-1)!$

  • $(n+1)(n)(n-1)! = 12 \times (n-1)!$

  • $n^2 + n - 12 = 0$

  • $(n+4)(n-3) = 0$

  • $n = 3$ ($n \neq -4$ as $n$ must be a natural number).

• Example 2: Find $n$ if $(n+2)! = 2550 \times n!$

  • $(n+2)(n+1) = 2550$

  • $n^2 + 3n - 2548 = 0$

  • $(n+52)(n-49) = 0$

  • $n = 49$ ($n = -52$ is rejected).

• Proof: $(2n)! = 2^n \times n! \times [1 \cdot 3 \cdot 5 \cdot \dots \cdot (2n-1)]$

  • Expanding $(2n)!$ and factoring out $2$ from every even term ($n$ terms total) yields the desired result.

Permutations

Permutation refers to the arrangement of items in a definite order. Order is critical in permutations.

Basic Theorems of Permutation

• Arrangement of $n$ distinct objects taken all at a time:

  • Symbolized as: $^nP_n = P(n, n) = n!$

  • Example: Arranging the $10$ letters of the word "GANESHPURI" results in $10!$ words.

• Arrangement of $n$ distinct objects taken $r$ at a time (0 \le r < n):

  • Formula: $^nP_r = P(n, r) = \frac{n!}{(n-r)!}$

  • Example: $5$ people in $3$ chairs: $^5P_3 = 5 \times 4 \times 3 = 60$.

Constrained Permutations

• Avoiding Adjacency: Arranging $10$ exam papers so the easiest and toughest never come together.

  • Total arrangements: $10!$

  • Arrangements with easiest and toughest together: treat them as one object ($9$ objects total) arranged in $9! \times 2!$ ways.

  • Result: $10! - (9! \times 2!) = 8 \times 9!$

• Row/Box Occupancy: Arranging the letters of "PERSON" ($6$ letters) in $8$ boxes such that no row (assuming two rows of $4$) remains empty.

  • Total ways: $^8P_6$

  • Ways with row 1 empty: $6!$

  • Ways with row 2 empty: $6!$

  • Result: $^8P_6 - (6! + 6!) = 18720$.

Permutation of Alike Objects

If there are $n$ objects where $p$ are alike of one kind, $q$ are alike of another, and $r$ are alike of a third kind, the total permutations taken all at a time is:

$\frac{n!}{p! q! r!}$

• IITJEE: $2$ I's, $2$ E's. Ways: $\frac{6!}{2! 2!} = 180$.

• ASSASSINATION: $4$ S's, $3$ A's, $2$ N's, $2$ I's. Ways: $\frac{13!}{4! 3! 2! 2!}$.

• AMERICA: $2$ A's. Ways: $\frac{7!}{2!}$.

Digit and Rank Problems

Natural Number Formation

Problems often involve forming numbers without repetition:

• One digit: $9$ numbers ($1-9$).

• Two digits: $9 \times 9 = 81$.

• Three digits: $9 \times 9 \times 8 = 648$.

• Total numbers from $1$ to $1000$ with no repeats: $9 + 81 + 648 = 738$.

Dictionary Rank

The rank is the position of a specific word when all possible permutations are listed alphabetically.

• Rank of "TOUGH":

  • Alphabetical order: G, H, O, T, U

  • Words starting with G, H, O: $3 \times 4! = 72$

  • Words starting with TG, TH: $2 \times 3! = 12$

  • Words starting with TOG, TOH: $2 \times 2! = 4$

  • Next word is TOUGH ($+1$).

  • Total Rank: $72 + 12 + 4 + 1 = 89$.

• Rank of "CRICKET":

  • Alphabetical order: C, C, E, I, K, R, T

  • Words starting with C (excluding those targeting CR): The required rank is $531$.

Combinations

Combinations refer to the selection or collection of items where information regarding the order of occurrence is not important.

Fundamental Theorems

• Number of selections of $n$ distinct things taken $r$ at a time:

  • Formula: $^nC_r = C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Properties of Combinations

1. $^nC_0 = 1$

2. $^nC_n = 1$

3. $^nC_{n-r} = ^nC_r$

4. If $^nC_x = ^nC_y$, then $x = y$ or $x + y = n$

5. Relationship with Permutation: $^nP_r = ^nC_r \times r!$

6. Pascal's Identity: $^nC_r + ^nC_{r+1} = ^{n+1}C_{r+1}$

Constrained Selections

• Items Always Included: Selecting $r$ things from $n$ where $p$ particular things must be included: $^{n-p}C_{r-p}$.

  • Example: Selecting $11$ players from $15$ where $2$ specific players are always included: $^{13}C_9$.

• Items Always Excluded: Selecting $r$ things from $n$ where $p$ particular things must be excluded: $^{n-p}C_r$.

  • Example: Selection of $6$ books from $11$ if $2$ specific books are never chosen: $^9C_6$.

Total Selections (Free Selections)

Case 1: Selection from Distinct Objects

Selecting at least one object from $n$ distinct objects:

$^nC_1 + ^nC_2 + \dots + ^nC_n = 2^n - 1$

• Application: Given $5$ green, $4$ blue, and $3$ red dyes (all distinct), the number of ways to choose at least one green and one blue dye is $(2^5 - 1)(2^4 - 1)(2^3) = 31 \times 15 \times 8 = 3720$.

Case 2: Selection from Identical Objects

• Number of ways to select $r$ objects from $n$ identical objects is $1$.

• Number of ways to select at least one object from $n$ identical objects is $n$.

• At least one selection from types of alike objects ($a_1, a_2 \dots a_n$): $(a_1+1)(a_2+1)\dots(a_n+1) - 1$.

• At least one selection from alike objects and $k$ distinct objects: $(a_1+1)(a_2+1)\dots(a_n+1)2^k - 1$.

Distribution of Alike Objects (Beggar’s Method)

Type 1: Non-negative Integral Solutions

The total number of ways to distribute $n$ identical items among $p$ persons (where each person can receive any number including zero) is:

$^{n+p-1}C_{p-1} = \frac{(n+p-1)!}{(p-1)! n!}$

• Example: Distributing $30$ mangoes among $5$ people: $^{30+5-1}C_{5-1} = ^{34}C_4$.

• Homogeneous Expressions: The number of terms in $(x_1 + x_2 + \dots + x_n)^m$ is $^{m+n-1}C_{n-1}$.

Type 2: Positive Integral Solutions

The total number of ways to distribute $n$ identical items among $p$ persons such that each receives at least one item is:

$^{n-1}C_{p-1}$

• Example: Distributing $7$ identical computers to $3$ people so each gets at least one: $^{7-1}C_{3-1} = ^6C_2$.

• Equation Application: Natural solutions for $x + y + z = 102$:

  • Subtracting $1$ from each variable yields $X + Y + Z = 99$.

  • Ways: $^{99+3-1}C_{3-1} = ^{101}C_2$.

Skill Up Solutions

• Skill Up 1: $192$ integers.

• Skill Up 2: $15552$ numbers.

• Skill Up 3: $m^n$ ways.

• Skill Up 4: $n^m$ ways.

• Skill Up 5: Evaluate for $n=5, r=2$: $10$.

• Skill Up 6: Find $x$ given $\frac{1}{8!} + \frac{1}{9!} = \frac{x}{10!}$: $100$.

• Skill Up 7: If $^nP_4 : ^nP_5 = 1 : 2$, then $n = 6$.

• Skill Up 8: If $^{12}P_r = 1320$, then $r = 3$.

• Skill Up 9: $4 digit$ even numbers from $0, 1, 2, 3, 4, 5, 6$: $420$.

• Skill Up 10: Numbers < 1000 from $1, 2, 3, 4, 5, 6$: $156$.

• Skill Up 11:

  • BANANA: $60$

  • ALLAHABAD: $7560$

  • INDEPENDENCE: $1663200$

• Skill Up 12: Row reads same backwards and forwards ($5$ A's, $6$ B's): $10$ ways.

• Skill Up 13: $10$ letters, $5$ letter words, at least one repeat: $69760$.

• Skill Up 14: $6$ friends, $3$ servants: $3^6 = 729$ ways.

• Skill Up 15: Numbers > 10^6 from $2334203$: $360$.

• Skill Up 16: Rank of "VARUN": $100$.

• Skill Up 17: Rank of "GOOGLE": $88$th.

• Skill Up 18: $r = 3$.

• Skill Up 19: $25$ students.

• Skill Up 20: $n = 6$.

• Skill Up 21: $840$ words.

• Skill Up 22: $3720$ combinations.

• Skill Up 23: $315$ ways.

• Skill Up 24: $^{12}C_3$.

• Skill Up 25: $46376$

• Skill Up 26: $35$ ways.

Answer Keys for Assignments

DPP - 01

• Level - 1: 1(c), 2(b), 3(b), 4(a), 5(a), 6(c)

• Level - 2: 1(a), 2(c)

DPP - 02

• Level - 1: 1(a), 2(a), 3(d), 4(a), 5(a), 6(d), 7(b), 8(a), 9(a), 10(b), 11(c)

• Level - 2: 1(c), 2(c), 3(a), 4(b), 5(d), 6(b), 7(a)

DPP - 03

• Level - 1: 1(b), 2(a), 3(a), 4(b), 5(c), 6(c), 7(b), 8(c)

• Level - 2: 1(d), 2(c), 3(a), 4(d), 5(b)

DPP - 04

• Level - 1: 1(c), 2(d), 3(c), 4(d), 5(a), 6(c)

• Level - 2: 1(a), 2(d), 3(c)

Mains Assignment Subjective

• Level - 1: 2(249900), 3(999), 4(246), 5(3000), 6(72), 7(161280), 8(236th), 9(20), 10(196), 11(84 ways), 12($^{n+5}C_5$), 13(30), 14(946)

• Level - 2: 1(87380), 2(i: 10878, ii: 5586), 3(17280)

Mains Assignment Objective

1(b), 2(b), 3(c), 4(c), 5(c), 6(a), 7(c), 8(c), 9(c), 10(c), 11(a), 12(d), 13(d), 14(d), 15(c), 16(d), 17(a), 18(c), 19(a), 20(b), 21(b), 22(b), 23(c), 24(a), 25(c), 26(c), 27(c), 28(d), 29(d), 30(b), 31(b), 32(b), 33(d), 34(c), 35(c), 36(a), 37(b), 38(b), 39(b), 40(d), 41(a), 42(d), 43(d), 44(c)