Counting Principles

Counting (combinatorics) is the art of determining the number of ways to arrange, select, or distribute objects. It is fundamental to probability, algorithm analysis, and discrete mathematics.

The Addition Rule (Sum Rule)

If task A can be done in m ways and task B can be done in n ways, and the tasks cannot be done simultaneously (mutually exclusive), then doing A or B can be done in:

m + n ways

Generalized: If tasks A₁, A₂, ..., Aₖ are mutually exclusive with nᵢ ways each:

n₁ + n₂ + ... + nₖ ways

Example: A student can choose a project from list A (5 projects) or list B (8 projects), but not both. Total choices: 5 + 8 = 13.

In set theory terms: if A ∩ B = ∅, then |A ∪ B| = |A| + |B|.

The Multiplication Rule (Product Rule)

If task A can be done in m ways, and for each way of doing A, task B can be done in n ways, then doing A and B can be done in:

m × n ways

Generalized: If a procedure consists of k sequential steps with nᵢ choices at step i:

n₁ × n₂ × ... × nₖ ways

Example: A license plate has 3 letters followed by 4 digits. Total plates: 26³ × 10⁴ = 175,760,000.

Example: How many bit strings of length 8 are there? Each position has 2 choices: 2⁸ = 256.

In set theory terms: |A × B| = |A| × |B|.

Subtraction Rule (Complement Counting)

If task A can be done in n ways total, and there are m ways that satisfy an unwanted condition, then the number of ways not satisfying the condition is:

n - m

Example: How many bit strings of length 8 have at least one 1?

Total strings: 2⁸ = 256. Strings with no 1s (all zeros): 1.

Answer: 256 - 1 = 255.

Example: How many 4-digit numbers (1000-9999) are not divisible by 5?

Total 4-digit numbers: 9000. Divisible by 5: those ending in 0 or 5 = 9 × 10 × 10 × 2 = 1800.

Answer: 9000 - 1800 = 7200.

Inclusion-Exclusion Principle

For non-mutually-exclusive events, the addition rule overcounts. The inclusion-exclusion principle corrects this.

Two sets:

|A ∪ B| = |A| + |B| - |A ∩ B|

Three sets:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

General formula for n sets:

|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| - Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| - ... + (-1)^(n+1)|A₁ ∩ A₂ ∩ ... ∩ Aₙ|

Example: How many integers from 1 to 1000 are divisible by 3 or 5 or 7?

Let A = multiples of 3, B = multiples of 5, C = multiples of 7.

|A| = ⌊1000/3⌋ = 333
|B| = ⌊1000/5⌋ = 200
|C| = ⌊1000/7⌋ = 142
|A ∩ B| = ⌊1000/15⌋ = 66
|A ∩ C| = ⌊1000/21⌋ = 47
|B ∩ C| = ⌊1000/35⌋ = 28
|A ∩ B ∩ C| = ⌊1000/105⌋ = 9

|A ∪ B ∪ C| = 333 + 200 + 142 - 66 - 47 - 28 + 9 = 543

Derangements via Inclusion-Exclusion

A derangement is a permutation where no element appears in its original position.

The number of derangements of n elements:

Dₙ = n! · Σᵢ₌₀ⁿ (-1)ⁱ / i!

This comes from inclusion-exclusion: subtract permutations where element 1 is fixed, or element 2 is fixed, etc., add back where both are fixed, etc.

D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9, D₅ = 44

As n → ∞, Dₙ / n! → 1/e ≈ 0.3679.

Pigeonhole Principle (Generalized)

Basic: If n + 1 objects are placed in n boxes, some box has ≥ 2 objects.

Generalized: If N objects are placed in k boxes, some box has at least ⌈N/k⌉ objects.

Example: Among 100 people, at least ⌈100/12⌉ = 9 share a birth month.

Example: Prove that in any set of 6 integers, there exist two whose difference is divisible by 5.

Proof: The possible remainders mod 5 are {0, 1, 2, 3, 4} — 5 boxes. By pigeonhole (6 integers in 5 boxes), two have the same remainder, so their difference is divisible by 5. ∎

Example: In a 6×6 grid, place 19 pieces. Some row has ≥ ⌈19/6⌉ = 4 pieces.

Permutations

A permutation is an arrangement of objects in a specific order.

Permutations of n objects

The number of ways to arrange n distinct objects:

P(n) = n! = n × (n-1) × (n-2) × ... × 2 × 1

Example: Arrange 5 books on a shelf: 5! = 120.

k-Permutations (Partial Permutations)

The number of ways to select and arrange k objects from n distinct objects:

P(n, k) = n! / (n - k)! = n × (n-1) × ... × (n-k+1)

Example: Choose a president, VP, and secretary from 10 people: P(10, 3) = 10 × 9 × 8 = 720.

Permutations with Repetition

If we have n objects with n₁ identical of type 1, n₂ identical of type 2, ..., nₖ identical of type k (where n₁ + n₂ + ... + nₖ = n):

n! / (n₁! · n₂! · ... · nₖ!)

This is also called a multinomial coefficient.

Example: Arrangements of the letters in "MISSISSIPPI":

• M: 1, I: 4, S: 4, P: 2. Total: 11 letters.
• 11! / (1! · 4! · 4! · 2!) = 39,916,800 / (1 · 24 · 24 · 2) = 34,650.

Combinations

A combination is a selection of objects where order doesn't matter.

The number of ways to choose k objects from n distinct objects:

C(n, k) = (n choose k) = n! / (k! · (n-k)!)

Also written as C(n,k), ₙCₖ, or $\binom{n}{k}$.

Example: Choose a committee of 3 from 10 people: C(10, 3) = 10! / (3! · 7!) = 120.

Properties of Binomial Coefficients

Symmetry: C(n, k) = C(n, n-k).

Pascal's Identity: C(n, k) = C(n-1, k-1) + C(n-1, k).

This gives rise to Pascal's Triangle:

         1
        1 1
       1 2 1
      1 3 3 1
     1 4 6 4 1
    1 5 10 10 5 1

Vandermonde's Identity: C(m+n, r) = Σₖ C(m, k) · C(n, r-k).

Row sum: C(n, 0) + C(n, 1) + ... + C(n, n) = 2ⁿ.

Alternating sum: C(n, 0) - C(n, 1) + C(n, 2) - ... = 0.

Binomial Theorem

(x + y)ⁿ = Σₖ₌₀ⁿ C(n, k) · xⁿ⁻ᵏ · yᵏ

Example: (x + y)³ = x³ + 3x²y + 3xy² + y³.

Setting x = y = 1: 2ⁿ = Σ C(n, k) (total subsets of an n-set). Setting x = 1, y = -1: 0 = Σ (-1)ᵏ C(n, k) (equal number of even and odd subsets).

Multinomial Coefficients

The multinomial coefficient:

(n choose k₁, k₂, ..., kₘ) = n! / (k₁! · k₂! · ... · kₘ!)

where k₁ + k₂ + ... + kₘ = n.

Multinomial theorem:

(x₁ + x₂ + ... + xₘ)ⁿ = Σ (n choose k₁,...,kₘ) · x₁^k₁ · x₂^k₂ · ... · xₘ^kₘ

Stars and Bars

Counts the number of ways to distribute n identical objects into k distinct bins.

Theorem: The number of ways to put n indistinguishable balls into k distinguishable boxes is:

C(n + k - 1, k - 1) = C(n + k - 1, n)

Visualization: Represent n balls as stars and k-1 dividers as bars.

Example: Distribute 10 identical candies among 4 children.

★★|★★★★|★|★★★

Answer: C(10 + 4 - 1, 4 - 1) = C(13, 3) = 286.

With Minimum Constraints

If each bin must have ≥ 1 object: First give 1 to each bin (uses k), then distribute remaining n - k freely:

C(n - 1, k - 1)

Example: Positive integer solutions to x₁ + x₂ + x₃ = 12: C(11, 2) = 55.

Double Counting

Prove two expressions count the same thing by counting it in two different ways.

Example: Prove C(n, 2) = n(n-1)/2.

Method 1: By definition, C(n, 2) = n! / (2!(n-2)!) = n(n-1)/2.

Method 2: Count handshakes among n people. Each person shakes n-1 hands, giving n(n-1) total. But each handshake is counted twice, so there are n(n-1)/2 handshakes.

Vandermonde's identity by double counting: Choose r people from m men and n women. LHS: C(m+n, r). RHS: Σₖ C(m,k)·C(n,r-k) (choose k men and r-k women).

Summary of Counting Formulas

| Problem | Formula | |---|---| | Arrange n distinct objects | n! | | k-permutation of n objects | P(n,k) = n!/(n-k)! | | Choose k from n (unordered) | C(n,k) = n!/(k!(n-k)!) | | Permutations with repetition (n₁ + ... + nₖ = n) | n!/(n₁!·...·nₖ!) | | k items from n with replacement, order matters | nᵏ | | k items from n with replacement, order doesn't matter | C(n+k-1, k) | | Distribute n identical into k distinct bins | C(n+k-1, k-1) | | Derangements of n | n! · Σ (-1)ⁱ/i! |

Real-World Applications

• Password strength: Number of possible passwords of length k from alphabet of size n = nᵏ. Entropy = k · log₂(n) bits.
• Algorithm analysis: Counting comparisons in sorting, counting recursive calls, analyzing hash collisions.
• Probability: P(event) = favorable outcomes / total outcomes. Requires counting both.
• Networking: Number of possible subnets, routing paths, IP addresses.
• Database query optimization: Estimating join cardinality, index selectivity.
• Error-correcting codes: Hamming distance, weight enumerators use binomial coefficients.
• Machine learning: Feature subset selection from n features = 2ⁿ possibilities.