8.14.c Solved Examples -- Permutations and Combinations

---

Basic Level

---

Example 1: Simple Permutation

Problem: In how many ways can 5 students be arranged in a row for a photograph?

Solution:

This is a linear arrangement of 5 distinct objects.

Ways = 5! = 5 x 4 x 3 x 2 x 1 = 120

Answer: 120

---

Example 2: Simple Combination

Problem: From a group of 9 students, in how many ways can a team of 4 be selected?

Solution:

Order does not matter (team selection).

Ways = 9C4 = 9! / (4! x 5!)
     = (9 x 8 x 7 x 6) / (4 x 3 x 2 x 1)
     = 3024 / 24
     = 126

Answer: 126

---

Example 3: Fundamental Counting Principle

Problem: A person has 4 shirts, 3 trousers, and 2 pairs of shoes. In how many ways can he dress up?

Solution:

Each choice is independent.

Ways = 4 x 3 x 2 = 24

Answer: 24

---

Example 4: Permutation -- Choosing Officers

Problem: A club has 12 members. In how many ways can a president, vice-president, and treasurer be elected?

Solution:

Order matters (different positions).

Ways = 12P3 = 12 x 11 x 10 = 1,320

Answer: 1,320

---

Example 5: Factorial Simplification

Problem: Simplify: 10! / (8! x 2!)

Solution:

10! / (8! x 2!) = (10 x 9 x 8!) / (8! x 2!)
                = (10 x 9) / (2 x 1)
                = 90 / 2
                = 45

Note: This is simply 10C2 = 45

Answer: 45

---

Intermediate Level

---

Example 6: Word Formation -- Distinct Letters

Problem: How many 4-letter words (with or without meaning) can be formed using the letters of "COMPUTER" such that no letter is repeated?

Solution:

"COMPUTER" has 8 distinct letters.
Choose 4 and arrange them.

Ways = 8P4 = 8! / (8-4)! = 8! / 4!
     = 8 x 7 x 6 x 5
     = 1,680

Answer: 1,680

---

Example 7: Word Formation -- Repeated Letters

Problem: How many distinct arrangements can be made using all the letters of "ALLAHABAD"?

Solution:

Letters: A=4, L=2, H=1, B=1, D=1
Total letters = 9

Arrangements = 9! / (4! x 2! x 1! x 1! x 1!)
             = 362,880 / (24 x 2)
             = 362,880 / 48
             = 7,560

Answer: 7,560

---

Example 8: Number Formation with Restrictions

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

Solution:

For the number to be even, the units digit must be 2 or 4.

Case 1: Units digit = 2
  Remaining 3 positions from {1, 3, 4, 5} = 4P3 = 24

Case 2: Units digit = 4
  Remaining 3 positions from {1, 2, 3, 5} = 4P3 = 24

Total = 24 + 24 = 48

Answer: 48

---

Example 9: Committee Formation -- Basic

Problem: In how many ways can a committee of 5 be formed from 6 men and 4 women so that the committee has at least 2 women?

Solution:

At least 2 women means: exactly 2W, or exactly 3W, or exactly 4W.

Case 1: 2 women, 3 men = 4C2 x 6C3 = 6 x 20 = 120
Case 2: 3 women, 2 men = 4C3 x 6C2 = 4 x 15 = 60
Case 3: 4 women, 1 man  = 4C4 x 6C1 = 1 x 6  = 6

Total = 120 + 60 + 6 = 186

Answer: 186

---

Example 10: Circular Arrangement

Problem: In how many ways can 8 children sit around a circular table?

Solution:

Circular permutation of 8 distinct objects.

Ways = (8 - 1)! = 7! = 5,040

Answer: 5,040

---

Example 11: Handshakes

Problem: In a party, every person shakes hands with every other person exactly once. If there were 66 handshakes in total, how many people were at the party?

Solution:

Each handshake involves 2 people. Total handshakes = nC2.

nC2 = 66
n(n-1)/2 = 66
n(n-1) = 132
n^2 - n - 132 = 0
(n - 12)(n + 11) = 0
n = 12  (rejecting negative value)

Answer: 12 people

---

Example 12: Vowels Together

Problem: In how many ways can the letters of "EQUATION" be arranged so that all vowels are together?

Solution:

Letters: E, Q, U, A, T, I, O, N (8 letters)
Vowels: E, U, A, I, O (5 vowels)
Consonants: Q, T, N (3 consonants)

Step 1: Treat all 5 vowels as a single unit.
        Units to arrange: {(EUAIO), Q, T, N} = 4 units
        Arrangements = 4! = 24

Step 2: Vowels within the unit can be rearranged.
        Internal arrangements = 5! = 120

Total = 24 x 120 = 2,880

Answer: 2,880

---

Example 13: Selection with Restrictions

Problem: A box contains 5 red, 4 blue, and 3 green balls. In how many ways can 4 balls be selected such that at least one ball of each colour is included?

Solution:

We need at least 1 red, 1 blue, 1 green, and total = 4.
So one colour contributes 2 balls, the other two contribute 1 each.

Case 1: 2R, 1B, 1G = 5C2 x 4C1 x 3C1 = 10 x 4 x 3 = 120
Case 2: 1R, 2B, 1G = 5C1 x 4C2 x 3C1 = 5 x 6 x 3  = 90
Case 3: 1R, 1B, 2G = 5C1 x 4C1 x 3C2 = 5 x 4 x 3  = 60

Total = 120 + 90 + 60 = 270

Answer: 270

---

Example 14: Diagonals of a Polygon

Problem: How many diagonals does a 12-sided polygon have?

Solution:

Diagonals = nC2 - n = n(n-3)/2

For n = 12:
Diagonals = 12(12-3)/2 = 12 x 9 / 2 = 54

Answer: 54

---

Advanced Level

---

Example 15: Permutation with Digit Restrictions

Problem: How many 5-digit numbers can be formed using digits {0, 1, 2, 3, 4, 5} without repetition that are divisible by 4?

Solution:

A number is divisible by 4 if its last two digits form a number divisible by 4.

Possible last two digits (from {0,1,2,3,4,5}, no repetition, divisible by 4):
04, 12, 20, 24, 32, 40, 52

For each case, fill the first 3 positions from remaining 4 digits.
But the first digit cannot be 0.

Case: Last two digits = 04
  Remaining digits: {1, 2, 3, 5}. First digit cannot be 0 (already used).
  All 4 digits are non-zero, so arrangements = 4 x 3 x 2 = 24

Case: Last two digits = 12
  Remaining: {0, 3, 4, 5}. First digit: 3 choices (not 0). Others: 3 x 2.
  = 3 x 3 x 2 = 18

Case: Last two digits = 20
  Remaining: {1, 3, 4, 5}. All non-zero.
  = 4 x 3 x 2 = 24

Case: Last two digits = 24
  Remaining: {0, 1, 3, 5}. First digit: 3 choices (not 0).
  = 3 x 3 x 2 = 18

Case: Last two digits = 32
  Remaining: {0, 1, 4, 5}. First digit: 3 choices (not 0).
  = 3 x 3 x 2 = 18

Case: Last two digits = 40
  Remaining: {1, 2, 3, 5}. All non-zero.
  = 4 x 3 x 2 = 24

Case: Last two digits = 52
  Remaining: {0, 1, 3, 4}. First digit: 3 choices (not 0).
  = 3 x 3 x 2 = 18

Total = 24 + 18 + 24 + 18 + 18 + 24 + 18 = 144

Answer: 144

---

Example 16: Circular Arrangement with Conditions

Problem: In how many ways can 4 boys and 4 girls sit around a circular table such that no two boys sit together?

Solution:

Step 1: Fix boys in a circle.
        Circular arrangement of 4 boys = (4-1)! = 3! = 6

Step 2: This creates 4 gaps between boys.
        Place 4 girls in these 4 gaps.
        Ways = 4! = 24

Total = 6 x 24 = 144

Answer: 144

---

Example 17: Distribution Problem

Problem: In how many ways can 8 identical apples be distributed among 3 children such that each child gets at least 1 apple?

Solution:

Using Stars and Bars with each child getting at least 1:

Give 1 apple to each child first. Remaining = 8 - 3 = 5 apples.
Distribute 5 identical apples among 3 children (0 or more each).

Ways = (5 + 3 - 1)C(3 - 1) = 7C2 = 21

Answer: 21

---

Example 18: Committee with Restrictions

Problem: From 7 men and 6 women, a committee of 5 is to be formed such that: (i) The committee must have at least 3 men. (ii) The committee must include a particular woman.

Find the number of ways.

Solution:

The particular woman is always included. Remaining selection: 4 from (7 men + 5 women).
And the committee must have at least 3 men.

Since 1 woman is fixed, we need at least 3 men in the 4 remaining picks.

Case 1: 3 men, 1 woman (from remaining 5 women)
  = 7C3 x 5C1 = 35 x 5 = 175

Case 2: 4 men, 0 women
  = 7C4 x 5C0 = 35 x 1 = 35

Total = 175 + 35 = 210

Answer: 210

---

Example 19: Words with No Two Vowels Adjacent

Problem: In how many ways can the letters of "SACHIN" be arranged such that no two vowels are adjacent?

Solution:

Letters: S, A, C, H, I, N
Vowels: A, I (2 vowels)
Consonants: S, C, H, N (4 consonants)

Step 1: Arrange consonants.
        Ways = 4! = 24

Step 2: Gaps for vowels: _S_C_H_N_ = 5 gaps
        Place 2 vowels in 5 gaps = 5P2 = 20

Total = 24 x 20 = 480

Answer: 480

---

Example 20: Grouping Problem

Problem: In how many ways can 12 people be divided into 3 groups of 4?

Solution:

If the groups are UNNAMED (indistinguishable):

Ways = 12! / [(4!)^3 x 3!]
     = 479,001,600 / [24 x 24 x 24 x 6]
     = 479,001,600 / 82,944
     = 5,775

The 3! in the denominator accounts for the groups being interchangeable.

Answer: 5,775

---

Example 21: Rank of a Word

Problem: If all the letters of the word "SACHIN" are arranged in alphabetical order, what is the rank of the word "SACHIN"?

Solution:

Alphabetical order of letters: A, C, H, I, N, S

Words starting with A: remaining 5 letters = 5! = 120
Words starting with C: remaining 5 letters = 5! = 120
Words starting with H: remaining 5 letters = 5! = 120
Words starting with I: remaining 5 letters = 5! = 120
Words starting with N: remaining 5 letters = 5! = 120
Words starting with S (our word starts here):

  S, A _ _ _ _ : Now fix SA.
  Words starting with SA:
    SA, C _ _ _ :
      SAC, H _ _ :
        SACH, I, N: = SACHIN (this is the word!)
        SACH, N, I: = SACHIN would come before SACHNI

  So SACH is followed by I then N.
  
  Let us count systematically:
  
  After S:
    S, A, _ , _ , _ , _
    After SA:
      SA, C, _, _, _ 
      After SAC:
        SAC, H, _, _
        After SACH:
          SACH, I, N --> this is "SACHIN"

  Words before "SACHIN":
  Starting with A____: 5! = 120
  Starting with C____: 5! = 120
  Starting with H____: 5! = 120
  Starting with I____: 5! = 120
  Starting with N____: 5! = 120
  (Total so far = 600)

  Starting with SA___: 
    SAC___:
      SACH__:
        SACHIN is the first arrangement of remaining {I, N} in order.
        SACHIN: I before N (alphabetically correct -- this is the first).
  
  So SACHIN comes right after the 600 words.
  
Rank = 600 + 1 = 601

Answer: 601

---

Example 22: Necklace Problem

Problem: Find the number of ways to arrange 6 different coloured beads to form a necklace.

Solution:

Necklace can be flipped, so clockwise = anticlockwise.

Ways = (n-1)! / 2 = (6-1)! / 2 = 5! / 2 = 120 / 2 = 60

Answer: 60

---

Example 23: Selection from Identical Groups

Problem: There are 4 copies of one book, 3 copies of a second book, and 2 copies of a third book. In how many ways can one or more books be selected?

Solution:

For book 1 (4 copies): can select 0, 1, 2, 3, or 4 copies = 5 choices
For book 2 (3 copies): can select 0, 1, 2, or 3 copies = 4 choices
For book 3 (2 copies): can select 0, 1, or 2 copies = 3 choices

Total selections (including selecting none) = 5 x 4 x 3 = 60
Subtract 1 for the case of selecting none.

Ways = 60 - 1 = 59

Answer: 59

---

Example 24: Geometry -- Triangles from Points

Problem: There are 10 points in a plane, no three of which are collinear except 4 which are collinear. How many triangles can be formed?

Solution:

Total triangles if no 3 were collinear = 10C3 = 120
Subtract triangles that would be formed by the 4 collinear points = 4C3 = 4

Triangles = 120 - 4 = 116

Answer: 116

---

Example 25: Two Specific People Together / Apart

Problem: 10 people are to be seated in a row. (a) In how many ways if two specific people must sit together? (b) In how many ways if those two specific people must NOT sit together?

Solution:

(a) Must sit together:
    Treat them as one unit. Total units = 9.
    Arrange 9 units = 9! = 362,880
    The pair can swap internally = 2!
    Total = 9! x 2! = 362,880 x 2 = 725,760

(b) Must NOT sit together:
    Total arrangements = 10! = 3,628,800
    Together (from part a) = 725,760

    Not together = 3,628,800 - 725,760 = 2,903,040

Answer: (a) 725,760 (b) 2,903,040

---

Example 26: Stars and Bars -- Equation Solutions

Problem: Find the number of non-negative integer solutions to x + y + z = 15.

Solution:

This is equivalent to distributing 15 identical objects into 3 distinct groups.

Using Stars and Bars:
Ways = (15 + 3 - 1)C(3 - 1) = 17C2 = (17 x 16) / 2 = 136

Answer: 136

---

Example 27: Permutations with Restrictions on Positions

Problem: In how many ways can the digits {1, 2, 3, 4, 5} be arranged such that 1 and 2 are never adjacent?

Solution:

Total arrangements = 5! = 120

Arrangements where 1 and 2 ARE adjacent:
  Treat (1,2) as a block. Units = {(1,2), 3, 4, 5} = 4 units.
  Arrangements = 4! x 2! = 24 x 2 = 48

Not adjacent = 120 - 48 = 72

Answer: 72

---

Previous: 8.14.b Tips, Tricks, and Shortcuts | Next: 8.14 Practice MCQs