Counting Principles and the Extended Binomial Theorem

The product principle

If one choice can be made in m ways and another in n ways, together they can be made in m × n ways.

Permutations (order matters)

• n distinct objects in a row: n!
• r objects chosen from n, in order: ⁿPᵣ = n!/(n − r)!

Example. 8 runners, 1st, 2nd and 3rd places: 8 × 7 × 6 = 336.

Combinations (order does not matter)

ⁿCᵣ = C(n, r) = n!/(r!(n − r)!)

Example. A committee of 3 from 10 people: C(10, 3) = 120.

Restrictions

• Together: treat the group as one object, then arrange inside it. 5 people in a row with A and B together: 4! × 2! = 48.
• Apart: total minus together: 120 − 48 = 72.
• Repeated letters: divide by the factorials of repeats. Arrangements of LEVEL: 5!/(2!2!) = 30.

Extended binomial theorem

For any rational n and abs(x) < 1:

(1 + x)ⁿ = 1 + nx + n(n − 1)x²/2! + n(n − 1)(n − 2)x³/3! + ...

Example. (1 + x)^(−1) = 1 − x + x² − x³ + ...

Example. √(1 + x) = (1 + x)^(1/2) ≈ 1 + x/2 − x²/8, valid for abs(x) < 1.

For (a + bx)ⁿ, factor out aⁿ first: (a + bx)ⁿ = aⁿ(1 + bx/a)ⁿ, valid for abs(bx/a) < 1.

Quick summary

• Order matters: permutations; order does not: combinations.
• Together: group; apart: total minus together.
• Extended binomial needs abs(x) < 1.