Clear Notion
Login

Concepts

Read through concept notes with worked explanations and diagrams, chapter by chapter.

Concept 01 / 09Permutations and Combinations

Fundamental Principles of Counting and Factorial Notation

The multiplication and addition principles and when each applies, tree diagrams, counting with the complement, factorials and their properties, and the exponent of a prime in n! (Legendre's formula).

Figure 1
All of combinatorics rests on two principles. They look obvious, but most counting errors come from applying the wrong one. Multiplication principle (AND). If a task is done in successive stages, with mm ways for the first stage and, for each of those, nn ways for the second stage, the whole task can be done in m×nm \times n ways. The tree diagram shows 33 choices followed by 22 choices, giving 66 complete outcomes. The crucial requirement is that the number of options at the second stage is the same no matter what was chosen at the first; the options themselves can differ. The principle extends to any number of stages. Addition principle (OR). If a task can be done in one of several mutually exclusive ways (cases that cannot happen together), with mm ways in the first case and nn in the second, the total is m+nm + n. If the cases overlap, adding double-counts the overlap, which must be subtracted (inclusion-exclusion). A reliable habit: describe the construction of one outcome in words. Each 'and then' multiplies; each 'or' between disjoint cases adds. For example, the number of 33-digit numbers with distinct digits: the hundreds digit has 99 choices (11 to 99), the tens digit 99 (any digit except the one used, now including 00), and the units digit 88, giving 9×9×8=6489 \times 9 \times 8 = 648. Choosing the most restricted position first (here the hundreds digit, which cannot be 00) keeps the number of options at later stages independent of earlier choices. Complementary counting. When 'at least one' or 'not all' appears, count the opposite and subtract from the total. The number of 44-digit numbers with at least one repeated digit is 9000−9×9×8×7=9000−4536=44649000 - 9 \times 9 \times 8 \times 7 = 9000 - 4536 = 4464. Factorials. n!=1×2×⋯×nn! = 1 \times 2 \times \cdots \times n, with 0!=10! = 1. The convention 0!=10! = 1 is not arbitrary: it is the number of ways to arrange zero objects (one way, do nothing), and it keeps formulas such as n!=n×(n−1)!n! = n \times (n - 1)! and (n0)=1\binom{n}{0} = 1 valid. Factorials grow very fast: 10!=362880010! = 3628800. Useful facts: n!n! is divisible by every integer from 11 to nn; (n+1)!−n!=n⋅n!(n + 1)! - n! = n \cdot n!, which makes sums like ∑k⋅k!\sum k \cdot k! telescope to (n+1)!−1(n + 1)! - 1. Exponent of a prime in n!n! (Legendre's formula). The power of the prime pp dividing n!n! is Ep(n!)=⌊np⌋+⌊np2⌋+⌊np3⌋+⋯E_{p}(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^{2}} \right\rfloor + \left\lfloor \frac{n}{p^{3}} \right\rfloor + \cdots The first term counts the multiples of pp up to nn, each contributing at least one factor pp; the second counts multiples of p2p^{2}, each contributing one extra factor; and so on. The number of trailing zeros of n!n! is E5(n!)E_{5}(n!), because factors of 22 are always more plentiful than factors of 55. Key Takeaways: - AND (successive stages) multiplies; OR (disjoint cases) adds. - Fill the most restricted position first so later counts do not depend on earlier choices. - 'At least one' questions: total minus 'none'. - 0!=10! = 1; n!=n(n−1)!n! = n(n - 1)!; ∑k=1nk⋅k!=(n+1)!−1\sum_{k=1}^{n} k \cdot k! = (n + 1)! - 1. - Ep(n!)=∑k≥1⌊n/pk⌋E_{p}(n!) = \sum_{k \ge 1}\lfloor n/p^{k} \rfloor; trailing zeros of n!n! equal E5(n!)E_{5}(n!). - Pitfall: adding cases that overlap, or multiplying stages whose option counts depend on earlier choices. - Pitfall: forgetting that a leading digit cannot be 00. Brain-Teaser 1: How many 44-digit even numbers can be formed with distinct digits? Solution: The units digit must be even, and the thousands digit cannot be 00; these two constraints interact, so split into cases. Case 1, units digit 00: the thousands digit has 99 choices, then 88 and 77 for the middle, giving 9×8×7=5049 \times 8 \times 7 = 504. Case 2, units digit 2,4,62, 4, 6 or 88 (44 choices): the thousands digit cannot be 00 or the units digit, so 88 choices; the remaining two positions have 88 and 77. That gives 4×8×8×7=17924 \times 8 \times 8 \times 7 = 1792. Total: 504+1792=2296504 + 1792 = 2296. The case split is needed because whether 00 has been used changes the number of choices for the thousands digit. Brain-Teaser 2: How many trailing zeros does 100!100! have, and what is the highest power of 33 dividing 100!100!? Solution: E5(100!)=⌊100/5⌋+⌊100/25⌋=20+4=24E_{5}(100!) = \lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor = 20 + 4 = 24, so 100!100! ends in 2424 zeros. Numbers like 2525, 5050, 7575 and 100100 contribute two factors of 55 each, which is why the second term is needed. E3(100!)=33+11+3+1=48E_{3}(100!) = 33 + 11 + 3 + 1 = 48. The exponent of 22 is 50+25+12+6+3+1=9750 + 25 + 12 + 6 + 3 + 1 = 97, far more than 2424, confirming that factors of 55 are the bottleneck for trailing zeros. Brain-Teaser 3: In how many ways can 55 letters be posted in 33 letter boxes? In how many ways can 33 letter boxes receive 55 letters if each box must get at least one? Solution: Each letter independently chooses a box: 35=2433^{5} = 243. (Not 535^{3}: the choosers are the letters, so the number of choices, 33, is the base.) For every box non-empty, subtract the assignments that miss a box using inclusion-exclusion: 35−(31)25+(32)15=243−96+3=1503^{5} - \binom{3}{1}2^{5} + \binom{3}{2}1^{5} = 243 - 96 + 3 = 150. The first question is a direct multiplication; the second needs the complement and inclusion-exclusion because 'every box non-empty' is a condition on the whole outcome, not on individual stages.

Practice this concept

Free · no account required · instant solutions

Fundamental Principles of Counting and Factorial Notation — DPP

4 questionsSee the solution the moment you answer

Practice