Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools


Counting Principles



The Addition Rule
The Multiplication Rule
Complementary Counting
Double Counting
The Pigeonhole Principle
Putting the Principles Together
Related Concepts
Counting Principles at a Glance



The Logic Beneath the Formulas


Before any specific formula in combinatorics — before permutations, combinations, or the binomial theorem — there are a small number of logical rules that govern how counts combine. Every counting argument in the section, however elaborate, is a structured application of these rules.

Two of them are foundational. The addition rule applies when a count splits into mutually exclusive cases; the multiplication rule applies when an outcome is built from a sequence of independent steps. Three further principles extend or vary these ideas: complementary counting (count what fails the condition and subtract), double counting (count the same set two ways and equate), and the pigeonhole principle (more items than containers forces a repeat).

Each principle answers a structural question about a counting problem rather than computing a specific number. Recognizing which principle applies is the first step in any counting argument.



The Addition Rule


The addition rule applies when a count splits into cases that cannot occur simultaneously. If an outcome can be achieved by method 1 in m1m_1 ways, by method 2 in m2m_2 ways, and so on through method kk in mkm_k ways, with no outcome belonging to more than one method, then the total number of outcomes is

Addition Rule
∣A1∪A2∪⋯∪Ak∣=∣A1∣+∣A2∣+⋯+∣Ak∣,Ai∩Aj=∅ for i≠j.|A_1 \cup A_2 \cup \cdots \cup A_k| = |A_1| + |A_2| + \cdots + |A_k|, \quad A_i \cap A_j = \emptyset \text{ for } i \neq j.
Learn more about this formula: Addition Rule →


The linguistic marker for the addition rule is the word or — pick method 1 OR method 2 OR method 3. Each "or" between mutually exclusive cases contributes its own count to the sum.

In the language of set theory, the rule is the cardinality identity ∣A∪B∣=∣A∣+∣B∣|A \cup B| = |A| + |B| when A∩B=∅A \cap B = \emptyset, generalized to any number of pairwise disjoint sets.

Example


A traveller can reach the city by 2 bus routes, by 3 train routes, or by 4 taxi routes. Since these options are mutually exclusive — one trip uses one mode of transport — the total number of route choices is

2+3+4=9.2 + 3 + 4 = 9.


The Mutual-Exclusion Condition


The rule requires that the cases be mutually exclusive. When two methods share outcomes, naive addition counts the shared outcomes twice. The systematic correction for this case is the inclusion–exclusion principle, which extends the addition rule by alternating additions and subtractions of intersection sizes.

The Multiplication Rule


The multiplication rule applies when an outcome is built from a sequence of independent steps, each contributing its own number of options. If step 1 has m1m_1 outcomes, step 2 has m2m_2 outcomes, and so on through step kk with mkm_k outcomes, and the steps are independent, then the combined sequence has

Multiplication Rule
∣A1×A2×⋯×Ak∣=∣A1∣⋅∣A2∣⋯∣Ak∣=m1⋅m2⋯mk.|A_1 \times A_2 \times \cdots \times A_k| = |A_1| \cdot |A_2| \cdots |A_k| = m_1 \cdot m_2 \cdots m_k.
Learn more about this formula: Multiplication Rule →


possible outcomes.

The linguistic marker for the multiplication rule is the word and — choose step 1 AND step 2 AND step 3. Each "and" between independent steps multiplies the count.

In set-theoretic terms, the rule is the cardinality of the Cartesian product, ∣A×B∣=∣A∣⋅∣B∣|A \times B| = |A| \cdot |B|, extended to any finite number of factors.

Example


A lunch combo is built from 3 main courses, 2 drinks, and 4 desserts. Each main can be paired with each drink, and each pairing with each dessert, giving

3×2×4=243 \times 2 \times 4 = 24


possible meals.

The Independence Condition


The rule requires that the number of options at each step not depend on the choices made at earlier steps. When the option count at a later step shifts based on earlier choices, the multiplication rule does not apply directly and the count must be broken down further — usually by splitting into cases via the addition rule.

The multiplication rule is the engine behind every permutation formula. Arranging nn distinct items in a line uses the rule with decreasing counts at each step: nn choices for the first position AND (n−1)(n-1) for the second AND (n−2)(n-2) for the third, down to 11, yielding n!n! total arrangements. Combinations build on the same product, with a division step to remove the ordering.
Aspect Addition rule Multiplication rule
Linguistic marker "or" — method 1 OR method 2 OR … "and" — step 1 AND step 2 AND …
Structural condition cases are mutually exclusive (no outcome belongs to two methods) steps are independent (count per step does not depend on earlier choices)
Formula m₁ + m₂ + … + mk m₁ × m₂ × … × mk
Set-theory identity |A ∪ B| = |A| + |B| for disjoint A, B |A × B| = |A| · |B| (Cartesian product)
Example 2 bus + 3 train + 4 taxi routes → 9 total 3 mains × 2 drinks × 4 desserts → 24 meals

Complementary Counting


Some counting problems are easier to solve in reverse. Counting the cases that fail a condition can be significantly simpler than counting the cases that satisfy it, especially when the condition has the form "at least one" — its negation, "none", often collapses into a single tractable count.

If UU is the universe of all outcomes and A⊆UA \subseteq U is the set of desired outcomes, then

Complementary Counting
∣A∣=∣U∣−∣U∖A∣=∣U∣−∣Ac∣.|A| = |U| - |U \setminus A| = |U| - |A^c|.
Learn more about this formula: Complementary Counting →


The strategy is to count the total, count the complement, and subtract.

Example


The number of arrangements of nn distinct items in which at least one item ends up in a specific designated position is awkward to count directly — multiple items can satisfy the condition independently, and the cases overlap. The complementary count — arrangements in which no item is in that position — partitions cleanly: the designated position holds one of the n−1n-1 non-designated items, and the remaining n−1n-1 items fill the rest. Subtracting this count from n!n! gives the desired number.

Structural Note


In set-theoretic notation, complementary counting expresses ∣A∣=∣U∣−∣Ac∣|A| = |U| - |A^c|, where AcA^c is the complement of AA in the universe. This is the addition rule applied to the partition A∪Ac=UA \cup A^c = U — complementary counting is a strategic application of the addition rule rather than an independent principle.

Double Counting


Double counting is a proof technique rather than a counting formula. The set in question is counted in two genuinely different ways; the two resulting expressions both equal the size of the set, so they equal each other. The output is an identity, not a numerical count.

If ∣S∣|S| can be expressed as f(n)f(n) by one argument and as g(n)g(n) by another argument, then

Double Counting
∣S∣=f(n)=g(n)  ⟹  f(n)=g(n).|S| = f(n) = g(n) \implies f(n) = g(n).
Learn more about this formula: Double Counting →


The Handshake Lemma


A canonical illustration: in a group of people who have shaken hands in various pairings, the sum of the number of hands each person shook equals twice the total number of handshakes. The reason is that each handshake is counted once from each participant's perspective — the same set (handshakes) counted two ways. In graph theory this becomes ∑vdeg⁡(v)=2∣E∣\sum_{v} \deg(v) = 2|E|, where the left side sums degrees over all vertices and the right side counts each edge from both endpoints.

Combinatorial Identities


Many of the identities involving the binomial coefficient — including Vandermonde's identity and the hockey stick identity — are most naturally proved by double counting. A subset count is interpreted in two ways: by selecting members directly, and by partitioning the selection into stages or cases. The two expressions for the same subset count then equate to produce the identity. Algebraic proofs of these identities exist, but the combinatorial proofs are typically shorter and more illuminating.

The Pigeonhole Principle


The pigeonhole principle does not count outcomes — it guarantees the existence of a particular kind of outcome. The statement is existential: it certifies that something must occur without identifying where.

Basic Form


If nn items are distributed among kk containers and n>kn > k, then at least one container holds at least two items.

Formally:

Pigeonhole Principle
n>k  ⟹  ∃ container with ≥2 items.n > k \implies \exists \text{ container with } \ge 2 \text{ items}.
Learn more about this formula: Pigeonhole Principle →


The reasoning is direct: if every container held at most one item, the total number of items would be at most kk, contradicting n>kn > k.

Generalized Form


If nn items are distributed among kk containers, then at least one container holds at least ⌈n/k⌉\lceil n/k \rceil items, where ⌈⋅⌉\lceil \cdot \rceil denotes the ceiling function. The basic form is the case n=k+1n = k+1, which forces ⌈n/k⌉=2\lceil n/k \rceil = 2.

Formally:

Pigeonhole Principle (Generalized)
n items into k containers  ⟹  ∃ container with ≥⌈n/k⌉ items.n \text{ items into } k \text{ containers} \implies \exists \text{ container with } \ge \lceil n/k \rceil \text{ items}.
Learn more about this formula: Pigeonhole Principle (Generalized) →


Examples


In any group of 13 people, at least two share a birth month — the 13 people are distributed among 12 months, so the basic form applies.

Among any 5 integers chosen from {1,2,…,8}\{1, 2, \ldots, 8\}, at least two come from one of the four pairs {1,2},{3,4},{5,6},{7,8}\{1,2\}, \{3,4\}, \{5,6\}, \{7,8\} — 5 items distributed into 4 pairs forces at least one pair to contain two of the chosen integers, and those two differ by exactly 1.

One-Sided Nature


The pigeonhole principle is asymmetric. It proves that a collision must occur, but says nothing about which container holds it or how to find it. The principle yields existence proofs in number theory, geometry, and combinatorics, often in settings where direct construction is hard or impossible.

In the language of functions, the principle states that no injection exists from a finite set into a strictly smaller finite set — any function from a larger finite set to a smaller one must map at least two elements of the domain to the same target.

Putting the Principles Together


Most counting problems are not solved by applying a single principle. They require chaining several — addition to split a problem into cases, multiplication within each case to count its outcomes, complementary counting to simplify a case that is easier in reverse.

A Worked Example


Count the number of 3-digit positive integers whose digits are all distinct.

The first digit cannot be 0 (or the number would not be a 3-digit number), so it has 9 choices. The second digit can be any digit except the one already used, giving 9 remaining choices (now including 0). The third digit can be any digit except the two already used, giving 8 choices. By the multiplication rule:

9×9×8=648.9 \times 9 \times 8 = 648.


Now consider the complementary question: how many 3-digit positive integers contain at least one repeated digit?

The total number of 3-digit positive integers is 9×10×10=9009 \times 10 \times 10 = 900 — 9 choices for the first digit and 10 each for the other two. Subtracting the 648 with all-distinct digits gives

900−648=252900 - 648 = 252


with at least one repetition.

A direct count of the "at least one repetition" set would require case analysis: exactly two digits equal and one different, all three digits equal, and the various positional arrangements. The complementary route converts the multi-case problem into a single subtraction.

When Each Principle Applies


The addition rule splits a count across mutually exclusive cases. The multiplication rule builds a count from independent steps. Complementary counting reframes a hard "at least one" problem as a simpler "none" problem and subtracts. Double counting produces identities by counting the same set two different ways. The pigeonhole principle proves that a configuration must exist when items outnumber containers.

These five principles together cover the logical foundation of every formula that appears in the rest of the section.

Related Concepts


• Set Theory — the language of unions, intersections, complements, and Cartesian products that the counting rules formalize as cardinality identities.

• Functions — the pigeonhole principle is the statement that no injection exists from a finite set into a strictly smaller finite set.

Counting Principles at a Glance


The page covered five logical rules behind every counting argument: the addition and multiplication rules for combining counts, complementary counting for "at least one" problems, double counting as a proof technique for identities, and the pigeonhole principle for existence guarantees. The table below collects each principle with its linguistic marker, its purpose, and a canonical example.
Principle Marker / form What it does Canonical example
Addition rule "or" across mutually exclusive cases sum the counts of each case 2 + 3 + 4 = 9 route choices
Multiplication rule "and" across independent steps multiply the step counts 3 × 2 × 4 = 24 lunch combos
Complementary counting "at least one" → count its negation "none" |A| = |U| − |U ∖ A|; subtract the complement 900 − 648 = 252 three-digit integers with a repeated digit
Double counting count the same set two different ways equate the two expressions → identity, not a number handshake lemma: Σ deg(v) = 2|E|
Pigeonhole principle items > containers at least one container holds ≥ ⌈n⁄k⌉ items (existence, not location) 13 people, 12 months → two share a birth month