7.1 The Two Basic Rules

• Product rule: a task done in a sequence of stages with n1, n2, ..., nk choices per stage has n1·n2···nk outcomes. Example: passwords of 3 letters followed by 2 digits: 26^3 · 10^2 = 17576 · 100 = 1,757,600.
• Sum rule: if a task is done either one way (m options) or another (n options) with no overlap, there are m + n outcomes. Example: pick one book from 5 Java or 7 Python books: 12 ways. If the option sets overlap, subtract the overlap — that generalizes to inclusion–exclusion (7.5).

7.2 Permutations — Order Matters

An r-permutation is an ordered arrangement of r objects from n distinct objects:

P(n, r) = n!/(n − r)! = n(n − 1)···(n − r + 1)

Example: gold/silver/bronze among 8 runners: P(8, 3) = 8·7·6 = 336.

With repeated objects: arrangements of n objects where object types repeat n1, n2, ..., nk times: n!/(n1!·n2!···nk!).

Worked: arrangements of MISSISSIPPI (11 letters: I×4, S×4, P×2, M×1): 11!/(4!·4!·2!) = 39,916,800/(24·24·2) = 39,916,800/1152 = 34,650.

Circular permutations of n objects: (n − 1)! (rotations are identical).

7.3 Combinations — Order Ignored

An r-combination is an unordered selection: C(n, r) = n!/(r!(n − r)!). Each combination corresponds to r! permutations, so P(n, r) = C(n, r)·r!.

Key identities:

• Symmetry: C(n, r) = C(n, n − r) — choosing r to keep = choosing n − r to discard.
• Pascal's identity: C(n, r) = C(n − 1, r − 1) + C(n − 1, r) — split on whether a fixed element is chosen. This recurrence builds Pascal's triangle and is a textbook dynamic-programming example.
• Row sum: C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n (count all subsets two ways).

7.4 Worked Example 1 — Committee with a Constraint

Problem: From 6 men and 4 women, form a 5-member committee with at least 2 women. Count by cases on the number of women:

1. 2 women, 3 men: C(4, 2)·C(6, 3) = 6·20 = 120
2. 3 women, 2 men: C(4, 3)·C(6, 2) = 4·15 = 60
3. 4 women, 1 man: C(4, 4)·C(6, 1) = 1·6 = 6

Total = 120 + 60 + 6 = 186. Cross-check by complement: all committees C(10, 5) = 252; with 0 women: C(6, 5) = 6; with 1 woman: C(4, 1)·C(6, 4) = 4·15 = 60. 252 − 6 − 60 = 186. ✔

7.5 The Binomial Theorem

(x + y)^n = Σ (r = 0 to n) C(n, r) x^(n−r) y^r, with general term T(r+1) = C(n, r) x^(n−r) y^r. The coefficients are exactly Pascal's triangle rows — hence the name binomial coefficients.

Worked Example 2 — a specific coefficient. Find the coefficient of x^3 in (2x + 3)^5.

1. T(r+1) = C(5, r)·(2x)^(5−r)·3^r; the power of x is 5 − r, so set 5 − r = 3 → r = 2.
2. T(3) = C(5, 2)·(2x)^3·3^2 = 10·8x^3·9 = 720·x^3. Coefficient = 720.

7.6 Inclusion–Exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|; for three sets add singles, subtract pairs, add back the triple.

Worked: How many integers in 1..100 are divisible by 2, 3, or 5?

1. Singles: ⌊100/2⌋ = 50, ⌊100/3⌋ = 33, ⌊100/5⌋ = 20.
2. Pairs (divisible by lcm): ⌊100/6⌋ = 16, ⌊100/10⌋ = 10, ⌊100/15⌋ = 6.
3. Triple: ⌊100/30⌋ = 3.
4. Answer: 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74. (So 26 integers are coprime to 30's prime set — the same computation behind Euler's totient.)

7.7 Common Mistakes & CS Applications

• Using P(n, r) when order is irrelevant (committee ≠ podium). Ask: does swapping two chosen items give a new outcome?
• Cases that overlap ("at least 2 women" counted as C(4,2)·C(8,3) double-counts committees with 3+ women).
• Forgetting to subtract overlap when applying the sum rule.
• Applications: counting drives complexity analysis (n! orderings force Ω(n log n) comparison sorting); the birthday paradox (collision probability among C(n, 2) pairs) sizes hash tables and breaks naive cryptographic schemes; C(n, r) counts k-subsets in test-case generation; entropy of an 8-character password is log2(95^8) ≈ 52.6 bits by the product rule.

🎯 Exam Focus

1. How many 4-digit even numbers with distinct digits can be formed? (Careful: leading digit ≠ 0.)
2. Prove Pascal's identity combinatorially.
3. Find the term independent of x in (x^2 + 1/x)^9.
4. In how many ways can the letters of ENGINEERING be arranged?
5. How many integers from 1 to 500 are divisible by neither 3 nor 7?
6. A byte is 8 bits. How many bytes contain (a) exactly three 1s, (b) at least seven 1s, (c) an even number of 1s?