• Practice
  • About 18 min
  • 5 practice questions

Fundamental principles of counting

Count choices with the sum rule and the product rule, correct over-counting with inclusion-exclusion, draw tree diagrams, and use the pigeonhole principle.

If something looks wrong, please tell us.

By the end of this lesson you can

  • Use the sum rule when exactly one of several tasks is done.
  • Use the product rule when a task is done in stages, one after another.
  • Use inclusion-exclusion, n(A ∪ B) = n(A) + n(B) − n(A ∩ B), to avoid counting twice.
  • Count numbers and strings with conditions by filling places one at a time.
  • Count the ways of placing n distinct objects in m places, and state the pigeonhole principle.

Combinatorics is the mathematics of counting. How many mobile numbers can a network issue? How many passwords can a computer system allow? Listing every possibility is slow and error-prone, so we need rules that count without listing. The chapter in the Tamil Nadu textbook starts with three such rules, and every later idea in the chapter, permutations and combinations included, is built from them.

The sum rule

If one task can be done in M ways and a second task in N ways, and the two cannot be done together, then one of the two tasks can be done in M + N ways. The rule extends to any number of tasks: if tasks T₁, T₂, ..., Tₙ can be done in m₁, m₂, ..., mₙ ways and only one of them is done, there are m₁ + m₂ + ... + mₙ ways.

Example. A school canteen offers 6 kinds of dosa and 4 kinds of idli, and a student may take only one item. The student picks either a dosa (6 ways) or an idli (4 ways), not both, so there are 6 + 4 = 10 choices. The key word is or.

The product rule

If a task has two stages, the first can be done in M ways and, after it, the second can be done in N ways, then the whole task can be done in M × N ways. More generally, with stages P₁, P₂, ..., Pₙ done in m₁, m₂, ..., mₙ ways one after another, the task can be done in m₁ × m₂ × ... × mₙ ways. The key word is and then.

Example. To go from Madurai to Chennai through Trichy, a traveller has 3 bus services from Madurai to Trichy and 4 trains from Trichy to Chennai. Each bus can be followed by any of the 4 trains, so the number of journeys is 3 × 4 = 12. A tree diagram shows this clearly: 3 branches for the bus, and from the end of each, 4 branches for the train, giving 12 end points.

Sum rule or product rule?

  • Sum rule: add
    • Do ONE of the tasks
    • The tasks cannot happen together
    • Key word: or
    • 6 dosas or 4 idlis: 6 + 4 = 10
  • Product rule: multiply
    • Do ALL the stages, in turn
    • Each stage follows the previous one
    • Key word: and then
    • 3 buses and then 4 trains: 3 × 4 = 12
Ask: does the job finish after one choice, or after a chain of choices?

The inclusion-exclusion principle

When two tasks A and B can be done together, adding their counts counts the common cases twice. We correct this by subtracting the common part once: n(A ∪ B) = n(A) + n(B) − n(A ∩ B). This is the same formula you met in the chapter on sets.

Worked example 1: divisible by 3 or 5

How many integers from 1 to 500 are divisible by 3 or by 5? Working: let A be the multiples of 3 and B the multiples of 5. Since 500 ÷ 3 = 166.6..., n(A) = 166. Since 500 ÷ 5 = 100, n(B) = 100. A number divisible by both 3 and 5 is divisible by 15, and 500 ÷ 15 = 33.3..., so n(A ∩ B) = 33. Hence n(A ∪ B) = 166 + 100 − 33 = 233.

Worked example 2: the least possible overlap

In a made-up survey of a street, 70% of the families keep a cow and 60% keep goats. What is the least percentage that keep both? Working: n(C ∩ G) = n(C) + n(G) − n(C ∪ G). The union can be at most 100%, so n(C ∩ G) is at least 70 + 60 − 100 = 30%.

Filling places one by one

Many problems ask for numbers or strings (letters written one after another in a row) with conditions. Draw one box for each place, fill the most restricted place first, and multiply the number of choices for each box.

Worked example 3: strings with a condition

Strings of length 5 are formed from the letters of TIGER, each letter used once. How many start with T or end with R? Working: starting with T, the other 4 places take I, G, E, R in 4 × 3 × 2 × 1 = 24 ways. Ending with R, similarly 24 ways. Starting with T and ending with R, the middle 3 places take I, G, E in 3 × 2 × 1 = 6 ways. By inclusion-exclusion the answer is 24 + 24 − 6 = 42. All strings number 5 × 4 × 3 × 2 × 1 = 120, so 120 − 42 = 78 strings neither start with T nor end with R.

Worked example 4: even numbers with a zero among the digits

How many 3-digit even numbers can be made from the digits 0, 1, 2, 3, 5 without repetition? Two conditions apply: the hundreds place cannot be 0, and the units place must be 0 or 2. Split into cases. Case 1, units digit 0: the hundreds place has 4 choices (1, 2, 3, 5) and the tens place 3 choices, giving 4 × 3 = 12. Case 2, units digit 2: the hundreds place cannot be 0 or 2, so it has 3 choices (1, 3, 5); the tens place may now use 0, leaving 3 choices; this gives 3 × 3 = 9. By the sum rule there are 12 + 9 = 21 numbers.

Objects into places, and switches

If n different objects are placed in m places and each object may go to any place, each object has m choices, so the count is m × m × ... × m = mⁿ. Count from the objects: take each object in turn and ask where it can go. For example, 4 different letters can be posted in 3 letter boxes in 3⁴ = 81 ways, but 3 letters in 4 boxes gives 4³ = 64 ways. Tossing 6 coins gives 2⁶ = 64 outcomes. If 6 fans in a hall work on independent switches, there are 2⁶ = 64 on-off patterns; leaving out the one pattern with every fan off, the hall can have at least one fan running in 2⁶ − 1 = 63 ways.

The pigeonhole principle

If k + 1 or more objects are placed in k boxes, at least one box holds two or more objects. It sounds obvious, but it proves things that would be hard to check directly. Among any 13 people, at least two were born in the same month, because there are only 12 months. If 8 classes are given 7 rooms, at least two classes must share a room.

One task OR another: add. Stage AND THEN stage: multiply. Overlap counted twice: subtract it once. n objects into m places: mⁿ.

— The counting rules

Key takeaways: decide first whether the choices are alternatives (add) or stages (multiply). Fill the most restricted place first and split into cases when one place affects another, as with 0 in the leading place. Use inclusion-exclusion whenever two conditions can hold together.

Check your understanding

  1. 1. A shop sells 5 kinds of pens and 3 kinds of pencils. In how many ways can a student buy exactly one item, either a pen or a pencil?

    1. 15
    2. 8
    3. 5
    4. 2
    Show answer

    Answer: B. Buying a pen and buying a pencil are alternatives, and only one item is bought, so the sum rule applies: 5 + 3 = 8. The product 15 would count buying one pen AND one pencil.

  2. 2. How many 3-digit numbers can be formed from the digits 1, 2, 3, 4, 5 if digits may be repeated?

    1. 125
    2. 60
    3. 243
    4. 15
    Show answer

    Answer: A. Each of the three places can take any of the 5 digits, and no digit is 0, so there is no leading-zero problem: 5 × 5 × 5 = 125. Without repetition it would be 5 × 4 × 3 = 60.

  3. 3. In how many ways can 4 different letters be posted in 5 letter boxes?

    1. 4⁵ = 1024
    2. 5 × 4 = 20
    3. 5⁴ = 625
    4. 5 + 4 = 9
    Show answer

    Answer: C. Count from the objects: each of the 4 letters can go into any of the 5 boxes, so there are 5 × 5 × 5 × 5 = 5⁴ = 625 ways. 4⁵ would be the count for 5 letters into 4 boxes.

  4. 4. How many integers from 1 to 100 are divisible by 2 or by 3?

    1. 83
    2. 50
    3. 66
    4. 67
    Show answer

    Answer: D. Multiples of 2: 50. Multiples of 3: 100 ÷ 3 = 33.3..., so 33. Multiples of both, that is of 6: 100 ÷ 6 = 16.6..., so 16. By inclusion-exclusion, 50 + 33 − 16 = 67.

  5. 5. What is the least number of people needed to be sure that at least two of them were born on the same day of the week?

    1. 7
    2. 8
    3. 14
    4. 2
    Show answer

    Answer: B. There are 7 days (boxes). With 7 people each could be born on a different day. With 8 people, by the pigeonhole principle, some day must have at least two of them.

Privacy · Terms · Refunds · Delivery