Counting and Combinatorics

How finite counting starts from sum and product rules, then moves into permutations, combinations, pigeonhole arguments, and inclusion-exclusion.
Modified

April 26, 2026

Keywords

counting, combinatorics, permutations, combinations, pigeonhole principle

1 Role

This page opens the discrete-math module.

It teaches the first finite-structure habit that keeps returning across the rest of the site:

before computing anything probabilistic or algorithmic, first count the right objects cleanly

2 First-Pass Promise

Read this page first in Discrete Math.

If you stop here, you should still understand:

  • the difference between sum and product rules
  • when order matters and when it does not
  • why permutations and combinations answer different questions
  • how complement counting can simplify a problem
  • what the pigeonhole principle is really saying

3 Why It Matters

Counting is one of the first places where discrete math stops being a bag of formulas and becomes a way of organizing structure.

The same ideas reappear in:

  • probability on finite sample spaces
  • algorithmic runtime bounds
  • graph counting
  • hashing and collision arguments
  • coding and information questions

When counting is weak, later pages often feel mysterious because the real issue is not probability or algorithms yet. The issue is that the space of possibilities was never described correctly.

4 Prerequisite Recall

  • a finite set can often be partitioned into disjoint cases
  • and usually signals a sequence of choices
  • or often signals a split into alternative cases
  • order and repetition are separate modeling decisions

5 Intuition

Most counting problems reduce to one of four questions:

  1. are we splitting into separate cases?
  2. are we making a sequence of choices?
  3. does order matter?
  4. is it easier to count the complement?

That is why the subject starts with very small structural moves:

  • sum rule for disjoint alternatives
  • product rule for chained choices
  • permutations when order matters
  • combinations when order does not

Then two more ideas quickly become load-bearing:

  • pigeonhole principle: enough objects forced into too few boxes creates a collision
  • inclusion-exclusion: if cases overlap, you cannot just add them blindly

6 Formal Core

Definition 1 (Definition: Sum Rule) If a finite set of outcomes is partitioned into disjoint cases

\[ A_1, A_2, \dots, A_k, \]

then the total number of outcomes is

\[ |A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_k|. \]

The key word is disjoint. If the cases overlap, simple addition overcounts.

Definition 2 (Definition: Product Rule) If an object is built by making a sequence of choices, and:

  • the first choice has \(n_1\) possibilities
  • the second choice has \(n_2\) possibilities
  • …
  • the \(k\)th choice has \(n_k\) possibilities

then the total number of possible objects is

\[ n_1 n_2 \cdots n_k. \]

This is the main reason finite counting often looks like multiplication.

Definition 3 (Definition: Permutations and Combinations) If order matters and repetition is not allowed, the number of ordered selections of \(k\) objects from \(n\) distinct objects is

\[ P(n,k) = n(n-1)\cdots(n-k+1). \]

If order does not matter, the number of size-\(k\) subsets of an \(n\)-element set is

\[ \binom{n}{k} = \frac{n!}{k!(n-k)!}. \]

The difference is conceptual:

  • permutations count arrangements
  • combinations count selections

Theorem 1 (Theorem Idea: Pigeonhole Principle) If more than \(n\) objects are placed into \(n\) boxes, then at least one box contains at least two objects.

More generally, if \(m\) objects are placed into \(n\) boxes, then some box contains at least

\[ \left\lceil \frac{m}{n} \right\rceil \]

objects.

This is not a formula trick. It is a structural impossibility statement.

Theorem 2 (Theorem Idea: Inclusion-Exclusion) For finite sets \(A\) and \(B\),

\[ |A \cup B| = |A| + |B| - |A \cap B|. \]

The subtraction is the correction for double counting.

This is the first version of a general habit:

if two counting descriptions overlap, fix the overlap explicitly

7 Worked Example

How many four-digit codes over the digits \(0,1,\dots,9\) contain at least one repeated digit?

Here a code is allowed to begin with \(0\), so we are really counting all length-\(4\) strings over ten symbols.

7.1 Step 1: Count everything

By the product rule,

\[ 10 \cdot 10 \cdot 10 \cdot 10 = 10^4 = 10000 \]

codes are possible in total.

7.2 Step 2: Count the complement

It is easier to count codes with all digits distinct.

For those:

  • the first digit has \(10\) choices
  • the second has \(9\)
  • the third has \(8\)
  • the fourth has \(7\)

So the number of all-distinct codes is

\[ 10 \cdot 9 \cdot 8 \cdot 7 = 5040. \]

7.3 Step 3: Subtract

Therefore the number of codes with at least one repeated digit is

\[ 10000 - 5040 = 4960. \]

This example matters because it shows the main first-pass workflow:

  • model the object correctly
  • use the product rule for sequential choices
  • switch to complement counting if the direct constraint is awkward

8 Computation Lens

When a counting problem shows up, this checklist is usually more useful than memorizing formulas:

  1. decide what object is being counted
  2. decide whether the problem splits into disjoint cases
  3. decide whether the object is built by sequential choices
  4. decide whether order matters
  5. decide whether repetition is allowed
  6. check whether counting the complement is simpler
  7. if cases overlap, ask whether inclusion-exclusion is needed

That is the computational habit behind most first-pass combinatorics.

9 Application Lens

One reason counting matters so much is that finite probability often starts here.

If all outcomes are equally likely, then probability becomes:

\[ \mathbb{P}(A) = \frac{|A|}{|\Omega|}. \]

So before you can do the probability calculation, you often need a combinatorics calculation.

The same idea appears in:

  • birthday-collision intuition
  • occupancy and hashing arguments
  • counting paths or matchings in graphs
  • measuring how large a search space really is

10 Stop Here For First Pass

If you can now explain:

  • when to add and when to multiply
  • why permutations and combinations answer different questions
  • how complement counting helps
  • what the pigeonhole principle forces

then this page has done its job.

11 Go Deeper

The next pages in this module are:

The strongest adjacent bridges are:

12 Optional Deeper Reading After First Pass

13 Sources and Further Reading

Sources checked online on 2026-04-25:

  • MIT 6.1200J course page
  • MIT 6.042J course page
  • Stanford CS103 counting lecture
  • CMU 15-151 course page
Back to top