Mathematics.

counting

Counting Principles

Combinatorics20 minDifficulty2 out of 10

You should know: natural numbers

Overview

Counting principles are the basic rules for determining how many ways a sequence of choices can be made, without listing every possibility. The two foundational rules are the addition principle (for mutually exclusive choices) and the multiplication principle (for independent, sequential choices) — together they underlie all of combinatorics, including permutations and combinations.

Intuition

If you're choosing a meal with 3 appetizers OR 4 entrées (not both), you have 3+4=7 options — that's the addition principle. If instead you're choosing 1 appetizer AND 1 entrée, you have 3×4=12 combined meals — that's the multiplication principle. Nearly every counting problem reduces to combining these two rules.

Formal Definition

Definition

The two fundamental counting rules:

∣A∪B∣=∣A∣+∣B∣if A∩B=∅|A \cup B| = |A| + |B| \quad \text{if } A \cap B = \emptyset
Addition principle
N=n1×n2×⋯×nkN = n_1 \times n_2 \times \cdots \times n_k

For k independent sequential choices with nᵢ options each

Multiplication principle

Properties

Inclusion-exclusion (2 sets)

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A \cup B| = |A| + |B| - |A \cap B|

Applications

Counting principles determine the size of a search space, e.g. the number of possible passwords or program states.

Worked Examples

  1. Independent sequential choices multiply.

    4×6=244 \times 6 = 24

Answer: 24

Practice Problems

Difficulty 2/10

A menu has 5 soups or 3 salads as a starter (pick exactly one), then 1 of 8 entrées. How many total meals?

Difficulty 5/10

A system password is exactly 8 characters, each a lowercase letter (26) or digit (10). How many possible passwords are there, and why does this matter for security?

Difficulty 4/10

A license plate format is 3 letters followed by 4 digits. How many distinct plates are possible?

Common Mistakes

Common Mistake

Multiplying when choices are mutually exclusive (OR) instead of adding.

Use addition when picking exactly one from disjoint groups (OR); use multiplication only when making independent, sequential selections (AND).

Quiz

You make a sequence of independent choices with 3, then 4, then 5 options. The total number of outcomes is:
The ADDITION principle (rather than multiplication) applies when:
Doubling the length of a fixed-alphabet password roughly does what to the number of possibilities?

Summary

  • Addition principle: for mutually exclusive choices, add the counts.
  • Multiplication principle: for independent sequential choices, multiply the counts.
  • These two rules underlie all counting problems, including permutations and combinations.
  • Inclusion-exclusion corrects the addition principle when sets overlap.

References

  1. WebsiteWikipedia — Combinatorial principles