Episode 8 — Aptitude and Reasoning / 8.14 — Permutations and Combinations

8.14.a Concepts and Formulas -- Permutations and Combinations

1. Fundamental Counting Principle (FCP)

Multiplication Principle

If a task can be broken into stages, and:

Stage 1 can be done in m ways
Stage 2 can be done in n ways

Then the total number of ways to complete both stages (in sequence) is:

Total ways = m x n

This extends to any number of stages:

Total ways = n1 x n2 x n3 x ... x nk

Example: A restaurant offers 3 starters, 4 main courses, and 2 desserts. The total number of different meals (one from each category):

Total meals = 3 x 4 x 2 = 24

Addition Principle

If a task can be done by Method A in m ways OR by Method B in n ways (mutually exclusive), then:

Total ways = m + n

Example: Travelling from City X to City Y, there are 3 bus routes and 2 train routes. Total ways to travel:

Total ways = 3 + 2 = 5

Key Distinction

AND (sequential stages) --> Multiply
OR (alternative methods) --> Add

2. Factorials

Definition

The factorial of a non-negative integer n (written as n!) is the product of all positive integers from 1 to n.

n! = n x (n-1) x (n-2) x ... x 3 x 2 x 1

Important Values

0! = 1        (by definition)
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 3,62,880
10! = 36,28,800

Properties of Factorials

Property 1:  n! = n x (n-1)!
Property 2:  n! / (n-1)! = n
Property 3:  n! / (n-2)! = n x (n-1)
Property 4:  0! = 1
Property 5:  Factorials are defined only for non-negative integers

Trailing Zeros in n!

The number of trailing zeros in n! is determined by the number of times 10 is a factor, which depends on the number of times 5 is a factor (since 2s are always more plentiful):

Trailing zeros in n! = floor(n/5) + floor(n/25) + floor(n/125) + ...

Example: Trailing zeros in 100!

= floor(100/5) + floor(100/25) + floor(100/125)
= 20 + 4 + 0
= 24

3. Permutations (nPr)

Definition

A permutation is an arrangement of objects where order matters.

Formula

The number of permutations of r objects chosen from n distinct objects:

nPr = n! / (n - r)!

Also written as P(n, r) or ^nP_r.

Derivation

When arranging r objects from n:

1st position: n choices
2nd position: n - 1 choices
3rd position: n - 2 choices
...
rth position: n - r + 1 choices

nPr = n x (n-1) x (n-2) x ... x (n-r+1)

     = n! / (n-r)!

Special Cases

nPn = n!              (arrange all n objects)
nP1 = n               (pick 1 from n)
nP0 = 1               (do nothing -- one way)
1Pr = 1   (if r <= 1)

Examples

Example 1: How many 3-letter "words" can be formed from {A, B, C, D, E}?

5P3 = 5! / (5-3)! = 5! / 2! = 120 / 2 = 60

Example 2: In how many ways can a president, vice-president, and secretary be chosen from 10 people?

10P3 = 10! / 7! = 10 x 9 x 8 = 720

4. Combinations (nCr)

Definition

A combination is a selection of objects where order does NOT matter.

Formula

The number of combinations of r objects chosen from n distinct objects:

nCr = n! / [r! x (n - r)!]

Also written as C(n, r), ^nC_r, or the binomial coefficient (n choose r).

Relationship Between nPr and nCr

nCr = nPr / r!

This is because every combination of r objects can be arranged in r! ways, giving all permutations.

Special Cases and Properties

nC0 = 1                        (select nothing)
nCn = 1                        (select everything)
nC1 = n                        (select one)
nCr = nC(n-r)                  (symmetry property)
nCr + nC(r-1) = (n+1)Cr        (Pascal's identity)
nC0 + nC1 + nC2 + ... + nCn = 2^n

Examples

Example 1: In how many ways can a committee of 3 be formed from 8 people?

8C3 = 8! / (3! x 5!)
    = (8 x 7 x 6) / (3 x 2 x 1)
    = 336 / 6
    = 56

Example 2: From a deck of 52 cards, in how many ways can 5 cards be selected?

52C5 = 52! / (5! x 47!)
     = (52 x 51 x 50 x 49 x 48) / (5 x 4 x 3 x 2 x 1)
     = 311,875,200 / 120
     = 2,598,960

5. Difference Between Permutations and Combinations

Aspect	Permutation (nPr)	Combination (nCr)
Order	Matters	Does not matter
Meaning	Arrangement	Selection
Formula	n!/(n-r)!	n!/[r!(n-r)!]
Value	Always >= nCr	Always <= nPr
Keywords	arrange, order, rank, sequence, position, digits	choose, select, committee, group, team, hand

Quick Test

Ask yourself: "If I rearrange the chosen items, do I get a different outcome?"

Yes --> Permutation
No --> Combination

Example:

Choosing 3 books from a shelf to read in order --> Permutation
Choosing 3 books from a shelf to give away --> Combination

6. Permutations with Repetition

Case 1: Arranging n Objects Where Some Are Identical

If among n objects, there are p identical objects of one kind, q of another kind, r of another, etc., then:

Number of distinct arrangements = n! / (p! x q! x r! x ...)

Example: How many distinct arrangements of the letters in "MISSISSIPPI"?

Total letters = 11
M = 1, I = 4, S = 4, P = 2

Arrangements = 11! / (1! x 4! x 4! x 2!)
             = 39,916,800 / (1 x 24 x 24 x 2)
             = 39,916,800 / 1,152
             = 34,650

Case 2: Filling r Positions from n Distinct Items (Repetition Allowed)

When each position can be filled by any of the n items:

Total arrangements = n^r

Example: How many 4-digit PINs can be formed using digits 0-9 (repetition allowed)?

Total PINs = 10^4 = 10,000

Case 3: Permutations of n Objects Taken All at a Time with Repetition

If you have n types of objects available in unlimited supply and must fill r positions:

Total = n^r

7. Circular Permutations

Definition

Arranging objects in a circle (e.g., around a table).

Why Different from Linear?

In a linear arrangement, shifting all elements by one position creates a new arrangement. In a circle, it does not (the relative order is the same).

Formula

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

Derivation

In a line: n! arrangements. Since the circle has no fixed starting point, each circular arrangement is counted n times (once for each rotation). So:

Circular permutations = n! / n = (n-1)!

Special Case: Necklace/Bracelet (Clockwise = Anticlockwise)

If the arrangement can be flipped (like a necklace), clockwise and anticlockwise are treated as the same:

Arrangements = (n-1)! / 2

Examples

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

(6-1)! = 5! = 120

Example 2: In how many ways can 8 beads be arranged on a necklace?

(8-1)! / 2 = 7! / 2 = 5,040 / 2 = 2,520

8. Combinations with Restrictions

Case 1: Particular Item(s) Always Included

If from n items you must select r, and k specific items must be included:

Ways = (n - k)C(r - k)

You have already chosen those k items. Now select the remaining (r - k) from the remaining (n - k).

Example: From 10 players, select a team of 5 such that the captain is always included.

Captain is fixed. Choose remaining 4 from 9.
= 9C4 = 9! / (4! x 5!) = 126

Case 2: Particular Item(s) Always Excluded

If k specific items must not be selected:

Ways = (n - k)Cr

Example: From 10 players, select 5, but two specific players are NOT available.

Choose 5 from remaining 8.
= 8C5 = 8! / (5! x 3!) = 56

Case 3: At Least / At Most Conditions

Use complementary counting or case-by-case addition.

"At least 1" = Total - (none selected)

At least 1 = nCr - (cases with 0 of the required type)

Example: From 6 men and 4 women, select a committee of 4 with at least 1 woman.

Total ways (no restriction) = 10C4 = 210

Ways with 0 women (all men) = 6C4 = 15

At least 1 woman = 210 - 15 = 195

9. Selection from Groups

Choosing from Multiple Distinct Groups

When selecting items from different groups, multiply the combinations from each group.

Example: From 5 boys and 4 girls, select 3 boys and 2 girls.

Ways = 5C3 x 4C2
     = 10 x 6
     = 60

Distributing Identical Objects into Distinct Groups

The number of ways to distribute n identical objects into r distinct groups:

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

This is the "Stars and Bars" theorem.

Example: Distribute 10 identical chocolates among 3 children.

(10 + 3 - 1)C(3 - 1) = 12C2 = 66

Distributing Identical Objects (Each Group Gets At Least 1)

(n - 1)C(r - 1)

Example: Distribute 10 identical chocolates among 3 children such that each gets at least 1.

(10 - 1)C(3 - 1) = 9C2 = 36

10. Committee Formation

Committee formation is one of the most commonly tested applications of combinations.

Basic Committee

From n people, form a committee of r:

Ways = nCr

Committee with Conditions

Type 1: With a fixed chairperson

Choose the chairperson first (or it is given), then select the remaining members.

Ways = 1 x (n-1)C(r-1)

Type 2: Committee must have members from different categories

Example: From 7 men and 5 women, form a committee of 5 with exactly 3 men and 2 women.

Ways = 7C3 x 5C2 = 35 x 10 = 350

Type 3: Committee with at least one from each category

Use total minus restricted cases.

Example: Committee of 4 from 6 men and 4 women, at least 1 man and at least 1 woman.

Total = 10C4 = 210
All men = 6C4 = 15
All women = 4C4 = 1

Required = 210 - 15 - 1 = 194

Type 4: Two specific people cannot serve together

Ways = Total - (both included)
     = nCr - (n-2)C(r-2)

Example: Committee of 5 from 10, but persons A and B cannot both be on the committee.

Total = 10C5 = 252
Both A and B included: choose remaining 3 from 8 = 8C3 = 56

Required = 252 - 56 = 196

Type 5: Two specific people must serve together or not at all

Ways = (both included) + (both excluded)
     = (n-2)C(r-2) + (n-2)Cr

Example: Committee of 5 from 10, persons A and B are either both in or both out.

Both in: 8C3 = 56
Both out: 8C5 = 56

Required = 56 + 56 = 112

11. Summary of All Key Formulas

+--------------------------------------------------+-------------------------------+
| Concept                                          | Formula                       |
+--------------------------------------------------+-------------------------------+
| Factorial                                        | n! = n x (n-1) x ... x 1     |
| Permutation                                      | nPr = n! / (n-r)!            |
| Combination                                      | nCr = n! / [r!(n-r)!]        |
| Permutations with identical objects              | n! / (p! x q! x r! x ...)    |
| Permutations with repetition (r positions, n types)| n^r                         |
| Circular permutations                            | (n-1)!                        |
| Necklace/bracelet                                | (n-1)! / 2                   |
| Stars and Bars (n identical into r groups)       | (n+r-1)C(r-1)                |
| Stars and Bars (each group >= 1)                 | (n-1)C(r-1)                  |
| Always include k items                           | (n-k)C(r-k)                  |
| Always exclude k items                           | (n-k)Cr                      |
| Sum of all combinations                          | nC0+nC1+...+nCn = 2^n        |
+--------------------------------------------------+-------------------------------+

12. Important Identities

1.  nCr = nC(n-r)
2.  nCr + nC(r-1) = (n+1)Cr          [Pascal's Identity]
3.  nC0 + nC1 + nC2 + ... + nCn = 2^n
4.  nC0 - nC1 + nC2 - nC3 + ... = 0   (for n >= 1)
5.  nC1 + nC2 + ... + nCn = 2^n - 1    (non-empty subsets)
6.  nPr = r! x nCr
7.  (n+1)Cr = nCr + nC(r-1)
8.  If nCa = nCb, then a = b or a + b = n

Next: 8.14.b Tips, Tricks, and Shortcuts