Permutations and Combinations

Permutation: order matters. nPr = n! / (n − r)!

Combination: order doesn't matter. nCr = n! / [r! · (n − r)!]

Read the question carefully: "in how many ways can they sit / be arranged" → permutation. "How many committees / teams / subsets" → combination.

Pattern 1: With repetition allowed.

• Permutations of n objects taken r at a time: n^r.
• Example: 4-digit numbers using digits 0-9 with repetition: 10⁴ = 10,000.

Pattern 2: Without repetition.

• Permutations: nPr.
• Combinations: nCr.

Pattern 3: Identical objects in arrangement.

• Arrangements of n objects of which p are alike, q alike, r alike: n! / (p! q! r!).
• Example: arrangements of letters in MISSISSIPPI = 11! / (4! · 4! · 2!) = 34,650.

Pattern 4: Circular arrangements.

• n distinct objects in a circle: (n − 1)! arrangements.
• If clockwise = anticlockwise (as in a necklace): (n − 1)! / 2.

Useful identities (verify, don't memorize blindly):

• nC0 + nC1 + nC2 + ... + nCn = 2^n
• nCr = nC(n−r)
• nCr + nC(r−1) = (n+1)Cr (Pascal's identity)

Worked example. From a group of 7 men and 5 women, form a committee of 5 with at least 2 women.

Cases: (2W, 3M), (3W, 2M), (4W, 1M), (5W, 0M).
= 5C2·7C3 + 5C3·7C2 + 5C4·7C1 + 5C5·7C0
= 10·35 + 10·21 + 5·7 + 1·1
= 350 + 210 + 35 + 1 = 596.