Fundamental Principle of Counting
If an event can occur in m different ways, followed by another event in n different ways, the two events together occur in m × n ways. Try the pant–shirt example from the textbook — pick how many pants and shirts Mohan owns, and watch the tree diagram build every outfit.
Three-event version — flags on a staff
Extend the rule to 3 events: choosing among p flags to fill 3 vacant places in succession (repetition of a flag not allowed in a signal).
Factorial Notation
n! = n × (n−1) × (n−2) × ... × 2 × 1 and by definition 0! = 1. Factorial counts the ways to arrange n distinct objects in a row, all at a time.
Growth of n!
Notice how quickly factorial explodes — 10! is already over 3.6 million!
Permutations of Distinct Objects — nPr
Arranging r objects chosen from n distinct objects, order matters, no repetition: ⁿPᵣ = n(n−1)(n−2)···(n−r+1) = n! / (n−r)!
Click letters below in order to build one arrangement. Slots show how many choices remain at each step.
Permutations When Repetition Is Allowed
If each of the r vacant places can be filled by any of the n objects again and again: Number of arrangements = nʳ
Worked example — 2-digit even numbers
Digits 1,2,3,4,5, repetition allowed. Units place must be even (2 or 4): 2 choices. Tens place: any of 5 digits.
Permutations With Some Objects Alike
When n objects contain groups of identical items — p₁ of one kind, p₂ of another kind, ... — the distinct arrangements are: n! / (p₁! p₂! ... pₖ!)
Combinations — nCr
Choosing r objects out of n, where order does not matter: ⁿCᵣ = n! / (r! (n−r)!)
Click objects (max r) to build a team. Duplicate teams (different order, same members) are shown struck through in the permutation list to demonstrate why we divide by r!.
Relationship: ⁿPᵣ = ⁿCᵣ × r!
Every combination of r objects can be internally rearranged in r! ways to give distinct permutations. So permutations = combinations × (ways to order each team).
| ⁿCᵣ (unordered teams) | × r! (orderings each) | = ⁿPᵣ (ordered arrangements) |
|---|---|---|