Counting arrangements and selections without listing them
The fundamental principle of counting says that if one task can be done in m ways and a second, independent task in n ways, both together can be done in m × n ways, so a shirt chosen from 4 and trousers from 3 give 12 outfits. Factorial notation, n! = n × (n − 1) × … × 2 × 1 with 0! = 1, counts the ways to arrange n different objects in a row: 5 books can be arranged on a shelf in 120 ways.
A permutation is an arrangement in which order matters. The number of ways to arrange r objects chosen from n different objects is ⁿPᵣ = n! ÷ (n − r)!. When some objects repeat, divide by the factorial of each repeated count, so the letters of APPLE can be arranged in 5!/2! = 60 ways. A combination is a selection in which order does not matter, ⁿCᵣ = n! ÷ [r!(n − r)!]. Choosing 3 students from 10 for a committee can be done in ¹⁰C₃ ways, but appointing a captain, vice-captain and secretary from them can be done in ¹⁰P₃ = 720 ways.
Why it matters
Counting methods work out the number of possible passwords, lottery outcomes, seating plans and tournament fixtures, and they are the foundation of probability. The coefficients ⁿCᵣ reappear in the binomial theorem. Deciding whether order matters is the single most important step in each question, and this chapter is a frequent source of JEE and aptitude-test problems.
Key terms
- Factorial
- The product of all positive integers from 1 up to n, written n!.
- Permutation
- An arrangement of objects in which the order of the objects matters.
- Combination
- A selection of objects in which the order of the objects does not matter.
- Fundamental counting principle
- Independent choices with m and n options can be made together in m × n ways.