Page 1
FPM & FPA
FPM & FPA
Fundamental Principles of Counting
1. Fundamental Principle of Multiplication
Job done in 2 stages (AND) : m × n ways
- If one work can be done in m ways and, after it, another in n ways, both together : m × n.
- Extends to any number of stages : m1 × m2 × … × mk.
- Key word "and" / stages one after another ⇒ multiply.
2. Fundamental Principle of Addition
Either of 2 independent ways (OR) : m + n ways
- Mutually exclusive alternatives (cases) ⇒ add.
- Key word "or" / cases ⇒ add.
3. Distribution Pattern (Choices)
- n objects each choose 1 of m options (repetition allowed) ⇒ mn ways — power = number of objects that make the choice.
- e.g. n monkeys each choosing among m masters ⇒ mn ; if each master gets at most one monkey (m ≥ n) ⇒ m(m − 1)…(m − n + 1).
- Letter lock with 4 rings of 26 letters : 26⁴ total, only 1 opens ⇒ 26⁴ − 1 unsuccessful attempts.
- Signals with flags : sum over number of flags used (1 flag OR 2 flags OR …), each case by FPM.
Key Points :
- Routes via cities : multiply along a path, add over different paths.
- Clothing / options with "none" allowed : add 1 option per item for "not chosen" ; compulsory item has no "none" option.
- Subtract the "nothing chosen" case when at least one must be chosen.
Page 2
Words, Rank & Numbers
Words, Rank & Numbers
4. Arranging Letters
- Fill restricted places first (e.g. vowels only in odd / even positions), then the rest.
- n distinct letters in a row : n! = n(n − 1)…1 (by FPM).
- "Together" ⇒ treat the block as one unit, then arrange inside the block.
5. Dictionary Rank
- Write the letters in alphabetical order.
- Fix each smaller letter in the first place, count arrangements of the remaining letters ; then fix the actual first letter and repeat for the next place.
- Rank = (number of words before it) + 1.
6. Number Formation
- Fill the most restricted place first : leading digit ≠ 0, last digit for parity / divisibility.
- "Greater than 6000" (4-digit) ⇒ first digit ∈ {6, 7, 8, 9}.
- "Between 5000 and 10000" ⇒ 4-digit numbers with first digit ≥ 5 (exclude 5000 itself if strict).
- Repetition allowed ⇒ each place has full choice ; not allowed ⇒ choices decrease by 1 per place.
- If 0 is a digit and the last place is restricted (even), split cases : last digit 0 vs non-zero.
Key Points :
- Count the complement when "at least one" appears : total − none.
- Number of n-digit numbers = 9 × 10n−1.
Page 3
Divisibility Rules
Divisibility Rules
7. Divisibility Tests
| By | Rule |
|---|---|
| 2 | last digit 0, 2, 4, 6, 8 |
| 3 | sum of digits divisible by 3 |
| 4 | last two digits divisible by 4 |
| 5 | last digit 0 or 5 |
| 6 | divisible by 2 and 3 |
| 8 | last three digits divisible by 8 |
| 9 | sum of digits divisible by 9 |
| 10 | last digit 0 |
| 11 | (sum of odd-place digits) − (sum of even-place digits) = 0 or multiple of 11 |
8. Using the Rules in Counting
- Divisible by 3 / 9 with given digits : first choose a digit set whose sum works, then arrange.
- Divisible by 4 / 8 : list valid last-two / last-three endings, then fill the remaining places.
- Divisible by 5 : cases last digit 0 and last digit 5 (0 cannot lead).
- Divisible by 11 : split digits into odd and even positions with equal (or 11-apart) sums.
Page 4
Additional Points (from lecture)
Additional Points (from lecture)
9. Key Ideas
- P&C = "counting without actually counting (listing)".
- Must include a particular object/condition : (total) − (arrangements without it).
- Restricted positions / objects are filled first, then the rest.
- k-th word in dictionary order : fix letters from the left, count words starting with each smaller letter until the count reaches k.