'Permutations and Combinations'

Fundamental Principle of Counting

Multiplication Principle

If an event can occur in m different ways and following this another event can occur in n different ways, then the two events together can occur in m x n ways.

Addition Principle

If an event can occur in m ways and another independent event can occur in n ways, then either of the two events can occur in m + n ways.

Example: A restaurant offers 3 appetizers and 4 main courses. Number of meal combinations = 3 x 4 = 12.

Example: From a set of 6 men and 5 women, choosing a representative can be done in 6 + 5 = 11 ways (either a man or a woman).

Factorial Notation

n! (read as 'n factorial') is the product of first n natural numbers. n! = n x (n-1) x (n-2) x ... x 3 x 2 x 1

Special cases:

• 0! = 1 (by definition)
• 1! = 1
• n! = n x (n-1)!

Key Factorial Values

• 5! = 120
• 6! = 720
• 7! = 5040
• 8! = 40320

Permutations (Arrangements)

A permutation is an arrangement of objects in a definite order.

Number of Permutations

The number of ways to arrange n distinct objects taking r at a time: P(n, r) = n!/(n - r)!, where 0 <= r <= n

Derivation: For first position, n choices; second position, (n-1) choices; ... rth position, (n-r+1) choices. By multiplication principle, n(n-1)(n-2)...(n-r+1) = n!/(n-r)!.

Key Results

• P(n, 0) = 1
• P(n, 1) = n
• P(n, n) = n!
• P(n, n-1) = n!

Permutations with Repetition

If each of r positions can be filled from n distinct objects with repetition allowed: n^r ways.

Permutations with Identical Objects

If there are n objects with n_1 of one type, n_2 of another, ..., n_k of kth type, the number of distinct permutations is: n!/(n_1! n_2! ... n_k!)

Circular Permutations

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

Combinations (Selections)

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

Number of Combinations

The number of ways to select r objects from n distinct objects: C(n, r) = n!/(r!(n - r)!)

Relationship Between Permutations and Combinations

P(n, r) = C(n, r) x r!

This makes intuitive sense: first select r objects, then arrange them in r! ways.

Key Properties of Combinations

• C(n, r) = C(n, n-r) (complementary selection)
• C(n, 0) = C(n, n) = 1
• C(n, 1) = n
• C(n, r) + C(n, r-1) = C(n+1, r) (Pascal's identity)
• C(n, r) = C(n, n-r)

Derivation of nPr and nCr

nPr derivation: To arrange r objects from n distinct objects: Position 1: n ways Position 2: (n-1) ways ... Position r: (n-r+1) ways By multiplication: nPr = n(n-1)(n-2)...(n-r+1) = n!/(n-r)!

nCr derivation: Each selection of r objects yields r! arrangements. So nCr x r! = nPr Therefore nCr = nPr/r! = n!/(r!(n-r)!)

Worked Examples

Example 1: How many 3-digit numbers can be formed using digits 1-9 without repetition? Solution: P(9, 3) = 9!/6! = 9 x 8 x 7 = 504

Example 2: In how many ways can 5 books be arranged on a shelf? Solution: 5! = 120 ways.

Example 3: From a group of 7 men and 4 women, a committee of 5 with at least 3 men is to be formed. How many ways? Solution: Cases: 3M+2W, 4M+1W, 5M+0W. C(7,3)xC(4,2) + C(7,4)xC(4,1) + C(7,5)xC(4,0) = 35x6 + 35x4 + 21x1 = 210 + 140 + 21 = 371

Common Mistakes

1. Permutation vs Combination confusion: Arrangement = order matters (permutation). Selection = order does not matter (combination).
2. Over-counting and under-counting: Be systematic in case analysis.
3. Missing the complement trick: Sometimes total - unwanted is easier than direct counting.
4. Ignoring constraints: 'At least' and 'at most' problems require casewise analysis.

ISC Exam Focus

• Theory (70%): nPr and nCr derivations, factorial operations, property proofs.
• Application (30%): Word problems, committee selections, number formation, arrangement problems.
• Typical 6-mark questions: "Find the number of ways to form a committee with constraints."
• ISC emphasises practical application problems over theoretical derivations.

Self-Test Questions

Q1: Find P(10, 3). Answer: P(10, 3) = 10 x 9 x 8 = 720

Q2: Find C(8, 3). Answer: C(8, 3) = 8!/(3!5!) = (8 x 7 x 6)/(3 x 2 x 1) = 56

Q3: How many 4-letter words can be formed from the letters of the word 'MATHEMATICS'? Answer: This requires handling repeated letters (M, A, T each appear twice). Multiple cases based on repetition pattern.

Q4: In how many ways can 6 people sit around a circular table? Answer: (6-1)! = 5! = 120 ways.

Q5: A committee of 5 is to be formed from 6 men and 4 women. In how many ways can it be done if it must include at least 2 women? Answer: Cases: 2W+3M, 3W+2M, 4W+1M. C(4,2)C(6,3) + C(4,3)C(6,2) + C(4,4)C(6,1) = 6x20 + 4x15 + 1x6 = 120 + 60 + 6 = 186.

Q6: Prove that C(n, r) = C(n, n-r). Answer: C(n, n-r) = n!/((n-r)!(n-(n-r))!) = n!/((n-r)! r!) = C(n, r).