Learning Objectives

• State and apply the rule of product (multiplication principle) and the rule of sum (addition principle).
• Use inclusion-exclusion for overlapping cases.
• Connect counting principles to nested loops and algorithm analysis.
• Estimate the size of search spaces using counting arguments.

Concept Overview

Rule of Product (Multiplication Principle)

If a process can be broken into sequential stages, with $a$ choices for stage 1 and $b$ choices for stage 2 (independent of stage 1's choice), then there are $a \cdot b$ total outcomes.

General form: For $k$ stages with $n_1, n_2, \ldots, n_k$ choices:

Rule of Sum (Addition Principle)

If a task can be done in one of several disjoint ways, with $a$ choices for way 1 and $b$ choices for way 2 (with no overlap), then there are $a + b$ total choices.

Inclusion-Exclusion (for overlapping cases)

When the cases overlap:

Connection to Loops

Connection to Sets (Module 4)

• Product rule: $|A \times B| = |A| \cdot |B|$ (Cartesian product)
• Sum rule: $|A \cup B| = |A| + |B|$ when $A \cap B = \emptyset$ (disjoint union)

Formal Notation

For finite sets $A, B$:

• $|A \times B| = |A| \cdot |B|$
• $|A \cup B| = |A| + |B| - |A \cap B|$
• $|A^k| = |A|^k$ (strings of length $k$ over alphabet $A$)

Worked Examples

Example 1: 4-Digit PINs

How many 4-digit PINs (digits 0–9)?

Each digit: 10 choices. By the product rule: $10^4 = 10000$.

int count = 0;
for (int d1 = 0; d1 <= 9; d1++)
  for (int d2 = 0; d2 <= 9; d2++)
    for (int d3 = 0; d3 <= 9; d3++)
      for (int d4 = 0; d4 <= 9; d4++)
        count++;
// count == 10000

Example 2: License Plates

3 letters (A–Z) followed by 3 digits (0–9):

Example 3: Strings with Constraints

How many 3-character strings over $\{a, b, c, d\}$ start with $a$ or end with $d$?

• Start with $a$: $1 \cdot 4 \cdot 4 = 16$.
• End with $d$: $4 \cdot 4 \cdot 1 = 16$.
• Start with $a$ AND end with $d$: $1 \cdot 4 \cdot 1 = 4$.
• By inclusion-exclusion: $16 + 16 - 4 = 28$.

Example 4: Loop Iteration Count

int count = 0;
for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
        count++;

By the product rule: count == m * n. This is the basis of Big-O analysis for nested loops.

Example 5: Brute-Force vs. Smart Search

Problem: Find all 8-character passwords using lowercase letters + digits.

Search space: $36^8 = 2{,}821{,}109{,}907{,}456 \approx 2.8 \times 10^{12}$.

At 1 billion checks/second: $\approx 2821$ seconds $\approx 47$ minutes.

This counting argument motivates why longer passwords and larger alphabets increase security.

Proof Techniques Spotlight

Counting Arguments as Proofs

To prove a set has a certain size, decompose the problem using sum/product rules:

1. Break into stages or cases.
2. Ensure stages are independent (product) or cases are disjoint (sum).
3. Multiply or add.

Double Counting

Count the same set two different ways to establish an identity. Example: the number of ordered pairs $(a, b) \in A \times B$ can be counted as $|A| \cdot |B|$ or by summing over elements of $A$: $\sum_{a \in A} |B| = |A| \cdot |B|$.

Java Deep Dive

import java.util.*;
import java.util.stream.*;

public class CountingPrinciples {

    // --- Counting by Enumeration ---

    /**
     * Count all strings of length k over an alphabet of size n.
     * By product rule: n^k.
     */
    public static long countStrings(int alphabetSize, int length) {
        long count = 1;
        for (int i = 0; i < length; i++) {
            count *= alphabetSize;
        }
        return count;
    }

    /**
     * Generate all strings of length k over the given alphabet.
     * The number generated should equal alphabetSize^k.
     */
    public static List<String> generateStrings(char[] alphabet, int length) {
        List<String> result = new ArrayList<>();
        generateHelper(alphabet, length, new char[length], 0, result);
        return result;
    }

    private static void generateHelper(char[] alpha, int len, char[] current,
                                        int pos, List<String> result) {
        if (pos == len) {
            result.add(new String(current));
            return;
        }
        for (char c : alpha) {
            current[pos] = c;
            generateHelper(alpha, len, current, pos + 1, result);
        }
    }

    /**
     * Count iterations of k nested loops each from 0 to n-1.
     * By product rule: n^k.
     */
    public static long countNestedLoopIterations(int n, int k) {
        long count = 1;
        for (int i = 0; i < k; i++) count *= n;
        return count;
    }

    // --- Inclusion-Exclusion ---

    /**
     * |A ∪ B| = |A| + |B| - |A ∩ B|.
     */
    public static <T> int inclusionExclusion(Set<T> a, Set<T> b) {
        Set<T> intersection = new HashSet<>(a);
        intersection.retainAll(b);
        return a.size() + b.size() - intersection.size();
    }

    /**
     * Three-set inclusion-exclusion:
     * |A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|.
     */
    public static <T> int inclusionExclusion3(Set<T> a, Set<T> b, Set<T> c) {
        Set<T> ab = new HashSet<>(a); ab.retainAll(b);
        Set<T> ac = new HashSet<>(a); ac.retainAll(c);
        Set<T> bc = new HashSet<>(b); bc.retainAll(c);
        Set<T> abc = new HashSet<>(ab); abc.retainAll(c);
        return a.size() + b.size() + c.size()
                - ab.size() - ac.size() - bc.size()
                + abc.size();
    }

    // --- Cartesian Product ---

    /**
     * Generate A × B as a list of pairs.
     * |result| should equal |A| * |B|.
     */
    public static <A, B> List<List<Object>> cartesianProduct(Set<A> setA, Set<B> setB) {
        List<List<Object>> result = new ArrayList<>();
        for (A a : setA) {
            for (B b : setB) {
                result.add(Arrays.asList(a, b));
            }
        }
        return result;
    }

    // --- Demo ---

    public static void main(String[] args) {
        System.out.println("=== Counting Principles ===\n");

        // Product rule: PINs
        System.out.println("4-digit PINs: " + countStrings(10, 4));

        // License plates
        System.out.println("License plates (3 letters + 3 digits): "
                + (countStrings(26, 3) * countStrings(10, 3)));

        // Generate small alphabet strings
        List<String> strs = generateStrings(new char[]{'a','b'}, 3);
        System.out.println("\nAll 3-char strings over {a,b}: " + strs);
        System.out.println("  Count: " + strs.size() + " (expected " + countStrings(2, 3) + ")");

        // Inclusion-exclusion
        Set<Integer> A = IntStream.rangeClosed(1, 20).filter(i -> i % 2 == 0)
                .boxed().collect(Collectors.toSet());
        Set<Integer> B = IntStream.rangeClosed(1, 20).filter(i -> i % 3 == 0)
                .boxed().collect(Collectors.toSet());
        System.out.println("\nEvens in {1..20}: " + A.size());
        System.out.println("Multiples of 3 in {1..20}: " + B.size());
        System.out.println("|A ∪ B| by inclusion-exclusion: " + inclusionExclusion(A, B));

        // Cartesian product
        Set<String> colors = Set.of("red", "blue");
        Set<Integer> sizes = Set.of(1, 2, 3);
        var cp = cartesianProduct(colors, sizes);
        System.out.println("\n{red,blue} × {1,2,3}: " + cp);
        System.out.println("  Count: " + cp.size() + " (expected " + (colors.size() * sizes.size()) + ")");

        // Nested loop counting
        System.out.println("\nNested loops (m=5, n=4): " + (5 * 4) + " iterations");
        System.out.println("3 nested loops (n=10): " + countNestedLoopIterations(10, 3));

        // Password space
        long passSpace = countStrings(36, 8);
        System.out.println("\n8-char password space (a-z + 0-9): " + passSpace);
    }
}

Historical Context

Counting principles have ancient roots. Indian mathematicians (Mahavira, 9th century) and Arabic scholars systematized combinatorial counting. Blaise Pascal (1654) and Pierre de Fermat developed counting methods through their study of gambling problems, which also launched probability theory.

The inclusion-exclusion principle was formalized by Abraham de Moivre (1718) and extended by Sylvester (1883). It is fundamentally connected to Euler's totient function, the sieve of Eratosthenes, and Möbius inversion.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. A restaurant offers 3 appetizers, 5 entrees, and 4 desserts. How many different meals can you order?

A2. How many 5-bit binary strings are there? How does this relate to the power set of a 5-element set?

A3. A program has a loop over $m$ items inside a loop over $n$ items. How many operations?

Slide Set B: Proof Problems

B1. Use counting to prove: $|A \times B| = |B \times A|$ for finite sets.

B2. Prove by inclusion-exclusion: the number of integers in $\{1, \ldots, 100\}$ divisible by 2 or 3 is 67.

B3. Prove: the number of functions from an $n$-element set to a $k$-element set is $k^n$.

Slide Set C: Java Coding Problems

C1. Write generateStrings(alphabet, length) and verify the count matches $|\text{alphabet}|^{\text{length}}$.

C2. Compute the Cartesian product of two sets. Verify $|A \times B| = |A| \cdot |B|$.

C3. Write a method counting integers in $\{1, \ldots, n\}$ divisible by $a$ or $b$. Use inclusion-exclusion.

Full Problem Set

Discrete Math Problems

DM1. How many strings of length 6 can be formed from the 26 lowercase letters if (a) repetition is allowed, (b) no letter is repeated?

DM2. How many integers in $\{1, \ldots, 1000\}$ are divisible by 2, 3, or 5? Use inclusion-exclusion.

DM3. A function $f: \{1,\ldots,n\} \to \{1,\ldots,k\}$ corresponds to a string of length $n$ over a $k$-letter alphabet. How many such functions are there? (Connect to Module 5.)

DM4. Prove: the number of subsets of $\{1,\ldots,n\}$ is $2^n$ using the product rule: for each element, choose "in" or "out." (Alternative to the induction proof from Module 6.)

DM5. How many ways can you seat $n$ people in a row? In a circle? (Introduce permutations preview.)

Java Programming Problems

JP1. Generate all binary strings of length $n$. Verify count equals $2^n$.

JP2. Implement 3-set inclusion-exclusion. Verify: integers in {1..1000} divisible by 2, 3, or 5.

JP3. Generate all strings of length 3 over $\{a,b,c,d\}$ that start with $a$ or end with $d$ (Example 3). Verify count is 28.

JP4. Compute Cartesian products of 3 sets $A \times B \times C$. Verify $|A \times B \times C| = |A| \cdot |B| \cdot |C|$.

JP5. Estimate brute-force time for an $n$-character password over a $k$-symbol alphabet at $10^9$ guesses/sec.

Bridge Problems

BR1. From Module 4: the password space $\{a,...,z,0,...,9\}^n$ is a Cartesian product. Each element is a function $f: \{1,...,n\} \to \{a,...,z,0,...,9\}$ (Module 5). How many such functions are injective? Connect to Module 5's injectivity.

BR2. From Module 2: count the number of units mod $n$ (integers coprime to $n$ in $\{1,...,n\}$) using inclusion-exclusion on prime factors. Connect to Euler's totient function $\phi(n)$.

Solutions

Discrete Math Solutions

DM1. (a) $26^6 = 308{,}915{,}776$. (b) $26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 \cdot 21 = 165{,}765{,}600$.

DM2. $|D_2| = 500, |D_3| = 333, |D_5| = 200, |D_2 \cap D_3| = |D_6| = 166, |D_2 \cap D_5| = |D_{10}| = 100, |D_3 \cap D_5| = |D_{15}| = 66, |D_2 \cap D_3 \cap D_5| = |D_{30}| = 33$.

By inclusion-exclusion: $500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$.

DM3. Each of the $n$ inputs can be mapped to any of $k$ outputs independently. By the product rule: $k^n$ functions.

DM4. For each element $x_i \in \{1,...,n\}$, there are 2 choices: include $x_i$ or exclude $x_i$. All choices are independent. By the product rule: $2^n$ subsets.

DM5. Row: $n!$. Circle: $(n-1)!$ (fix one person, permute the rest).

Learning Objectives

• Compute permutations $P(n,k)$ and combinations $C(n,k)$.
• State and prove Pascal's identity.
• Apply the binomial theorem.
• Implement factorial, $C(n,k)$, and combination generation in Java.
• Connect combinations to power sets (Module 4) and counting (Module 7 Class 1).

Concept Overview

Permutations

A permutation of $k$ elements from a set of $n$ is an ordered arrangement:

• $P(n,n) = n!$ — arrange all $n$ elements.
• $P(n,1) = n$ — choose one element.

Combinations (Binomial Coefficients)

A combination of $k$ elements from $n$ is an unordered selection:

• $\binom{n}{0} = \binom{n}{n} = 1$
• $\binom{n}{k} = \binom{n}{n-k}$ (symmetry)

Pascal's Identity

Combinatorial proof: Among the $\binom{n}{k}$ subsets of $\{1,\ldots,n\}$ of size $k$, those containing $n$ number $\binom{n-1}{k-1}$ (choose remaining $k-1$ from $\{1,\ldots,n-1\}$), and those not containing $n$ number $\binom{n-1}{k}$.

The Binomial Theorem

Special cases:

• $(1+1)^n = \sum \binom{n}{k} = 2^n$ (total subsets of an $n$-set — Module 4!)
• $(1-1)^n = \sum (-1)^k \binom{n}{k} = 0$ (equal even- and odd-sized subsets)

Pascal's Triangle

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

Row $n$: $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$.

Formal Notation

Worked Examples

Example 1: Committee Selection

How many ways to choose a 3-person committee from 10 people?

Example 2: Arranging Letters

How many arrangements of the letters in "ABCDE"? $5! = 120$.

How many 3-letter arrangements from "ABCDE"? $P(5,3) = 5 \cdot 4 \cdot 3 = 60$.

Example 3: Pascal's Identity

$\binom{5}{2} = \binom{4}{1} + \binom{4}{2} = 4 + 6 = 10$. ✓

Example 4: Subsets of Size $k$

List all 2-element subsets of $\{1,2,3,4\}$:

$\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}$ — 6 subsets = $\binom{4}{2} = 6$. ✓

Example 5: Binomial Theorem Application

$(x + 1)^4 = \binom{4}{0}x^4 + \binom{4}{1}x^3 + \binom{4}{2}x^2 + \binom{4}{3}x + \binom{4}{4} = x^4 + 4x^3 + 6x^2 + 4x + 1$

Proof Techniques Spotlight

Combinatorial Proofs

Instead of algebraic manipulation, argue by counting the same set two ways.

Example: Prove $\sum_{k=0}^{n} \binom{n}{k} = 2^n$.

Combinatorial proof: The left side counts all subsets of $\{1,...,n\}$ by size. The right side counts all subsets by the product rule ($2^n$ binary choices). Both count $|\mathcal{P}(\{1,...,n\})|$. $\blacksquare$

Algebraic Proofs of Binomial Identities

Use factorials and simplify. For Pascal's identity:

Java Deep Dive

import java.util.*;
import java.util.stream.*;

public class CombinatoricsLibrary {

    // --- Factorial ---

    public static long factorial(int n) {
        long result = 1;
        for (int i = 2; i <= n; i++) result *= i;
        return result;
    }

    // --- Binomial Coefficient ---

    /**
     * C(n, k) computed without full factorial to avoid overflow.
     * C(n,k) = n*(n-1)*...*(n-k+1) / k!
     */
    public static long binomial(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1;
        if (k > n - k) k = n - k; // symmetry: C(n,k) = C(n,n-k)
        long result = 1;
        for (int i = 0; i < k; i++) {
            result = result * (n - i) / (i + 1);
        }
        return result;
    }

    /**
     * C(n, k) via Pascal's triangle (dynamic programming).
     */
    public static long binomialDP(int n, int k) {
        long[][] dp = new long[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= Math.min(i, k); j++) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            }
        }
        return dp[n][k];
    }

    // --- Permutations ---

    public static long permutations(int n, int k) {
        long result = 1;
        for (int i = 0; i < k; i++) result *= (n - i);
        return result;
    }

    // --- Pascal's Triangle ---

    public static void printPascalsTriangle(int rows) {
        for (int n = 0; n < rows; n++) {
            // Spacing
            for (int s = 0; s < rows - n - 1; s++) System.out.print("   ");
            for (int k = 0; k <= n; k++) {
                System.out.printf("%5d ", binomial(n, k));
            }
            System.out.println();
        }
    }

    // --- Generate All k-Subsets ---

    /**
     * Generate all subsets of {0,...,n-1} of size k.
     * Count should equal C(n, k).
     */
    public static List<List<Integer>> generateCombinations(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        generateCombHelper(n, k, 0, new ArrayList<>(), result);
        return result;
    }

    private static void generateCombHelper(int n, int k, int start,
                                            List<Integer> current,
                                            List<List<Integer>> result) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < n; i++) {
            current.add(i);
            generateCombHelper(n, k, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }

    // --- Generate All Permutations ---

    public static List<List<Integer>> generatePermutations(int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> items = IntStream.range(0, n).boxed()
                .collect(Collectors.toList());
        permuteHelper(items, 0, result);
        return result;
    }

    private static void permuteHelper(List<Integer> items, int idx,
                                       List<List<Integer>> result) {
        if (idx == items.size()) {
            result.add(new ArrayList<>(items));
            return;
        }
        for (int i = idx; i < items.size(); i++) {
            Collections.swap(items, idx, i);
            permuteHelper(items, idx + 1, result);
            Collections.swap(items, idx, i);
        }
    }

    // --- Verify Identities ---

    public static void verifyIdentities(int maxN) {
        for (int n = 0; n <= maxN; n++) {
            // Sum of row = 2^n
            long rowSum = 0;
            for (int k = 0; k <= n; k++) rowSum += binomial(n, k);
            assert rowSum == (1L << n) : "Row sum failed for n=" + n;

            // Pascal's identity
            for (int k = 1; k < n; k++) {
                assert binomial(n, k) == binomial(n - 1, k - 1) + binomial(n - 1, k)
                        : "Pascal failed for n=" + n + ", k=" + k;
            }

            // Symmetry
            for (int k = 0; k <= n; k++) {
                assert binomial(n, k) == binomial(n, n - k);
            }
        }
    }

    // --- Demo ---

    public static void main(String[] args) {
        System.out.println("=== Combinatorics Library ===\n");

        // Binomial coefficients
        System.out.println("C(10,3) = " + binomial(10, 3));       // 120
        System.out.println("C(10,3) DP = " + binomialDP(10, 3));  // 120
        System.out.println("P(5,3) = " + permutations(5, 3));     // 60
        System.out.println("5! = " + factorial(5));                // 120

        // Pascal's triangle
        System.out.println("\nPascal's Triangle (8 rows):");
        printPascalsTriangle(8);

        // Generate combinations
        List<List<Integer>> combs = generateCombinations(5, 2);
        System.out.println("\nAll 2-subsets of {0..4}: " + combs);
        System.out.println("Count: " + combs.size() + " (expected " + binomial(5, 2) + ")");

        // Generate permutations
        List<List<Integer>> perms = generatePermutations(4);
        System.out.println("\nPermutations of {0..3}: " + perms.size()
                + " (expected " + factorial(4) + ")");

        // Verify identities
        verifyIdentities(20);
        System.out.println("\nAll identities verified for n = 0..20!");
    }
}

Historical Context

Blaise Pascal (1654) published the Traité du triangle arithmétique, establishing fundamental properties of binomial coefficients. However, the triangle was known centuries earlier: Pingala (India, ~200 BC), Al-Karaji (Persia, ~1000 AD), and Yang Hui (China, 1261) all studied it.

The binomial theorem for positive integers was known to Isaac Newton (1665), who extended it to non-integer exponents, creating the generalized binomial series.

Combinatorial proofs — proving identities by counting — are preferred by many mathematicians because they provide understanding, not just verification. This philosophy aligns with the course's emphasis on proofs as explanations.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. What is the difference between $P(n,k)$ and $C(n,k)$?

A2. How does $\binom{n}{k}$ relate to the number of subsets of size $k$ of an $n$-element set?

A3. Explain why $\binom{n}{k} = \binom{n}{n-k}$ without algebra (combinatorial argument).

A4. How many rows of Pascal's triangle do you need to compute $\binom{10}{3}$ using only Pascal's identity?

Slide Set B: Proof Problems

B1. Prove Pascal's identity combinatorially and algebraically.

B2. Prove: $\sum_{k=0}^n \binom{n}{k} = 2^n$.

B3. Prove: $\sum_{k=0}^n (-1)^k \binom{n}{k} = 0$ for $n \geq 1$.

B4. Prove by induction: $\binom{n}{k} \leq 2^n / 2$ for $1 \leq k \leq n-1$ and $n \geq 2$.

Slide Set C: Java Coding Problems

C1. Implement binomial(n, k) without computing full factorials. Verify against binomialDP(n, k).

C2. Generate all 3-element subsets of $\{1,...,7\}$. Verify count = $\binom{7}{3} = 35$.

C3. Build Pascal's triangle up to row 15 using dynamic programming.

Full Problem Set

Discrete Math Problems

DM1. Compute: (a) $\binom{8}{3}$, (b) $P(8,3)$, (c) $\binom{12}{4}$, (d) $P(6,6)$.

DM2. How many 5-card poker hands can be dealt from a 52-card deck?

DM3. Prove: $\binom{n}{k} \cdot \binom{k}{j} = \binom{n}{j} \cdot \binom{n-j}{k-j}$ (Vandermonde-like identity).

DM4. Prove by induction on $n$: $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.

DM5. A committee of 4 is chosen from 6 men and 5 women. How many committees have at least 2 women?

Java Programming Problems

JP1. Implement factorial, permutations, binomial. Test with known values.

JP2. Using DP, build Pascal's triangle as a 2D array. Print rows 0–15.

JP3. Generate all $k$-element subsets of $\{0,...,n-1\}$ using backtracking. Verify count = $\binom{n}{k}$.

JP4. Generate all permutations of a string. For "ABCD", verify count = 24.

JP5. Implement the binomial theorem: given $n$, expand $(x+y)^n$ as a list of terms $\binom{n}{k} x^k y^{n-k}$. Evaluate at $x = 1, y = 1$ and verify = $2^n$.

Bridge Problems

BR1. From Module 4: $|\mathcal{P}(A)| = 2^n$. From this class: $\sum_{k=0}^n \binom{n}{k} = 2^n$. These are the same fact from two perspectives. Explain the connection and implement both computations.

BR2. From Module 5: the number of injective functions $f: \{1,...,k\} \to \{1,...,n\}$ is $P(n,k)$. The number of $k$-element subsets of $\{1,...,n\}$ is $C(n,k) = P(n,k)/k!$ (quotient by the symmetry group). Verify in Java for small $n, k$.

Solutions

Discrete Math Solutions

DM1. (a) $\binom{8}{3} = 56$. (b) $P(8,3) = 336$. (c) $\binom{12}{4} = 495$. (d) $P(6,6) = 720$.

DM2. $\binom{52}{5} = 2{,}598{,}960$.

DM5. Exactly 2 women: $\binom{5}{2}\binom{6}{2} = 10 \cdot 15 = 150$. Exactly 3 women: $\binom{5}{3}\binom{6}{1} = 10 \cdot 6 = 60$. Exactly 4 women: $\binom{5}{4}\binom{6}{0} = 5$. Total: $150 + 60 + 5 = 215$.

Learning Objectives

• State and apply the pigeonhole principle (basic and generalized).
• Analyze hash table collisions using the pigeonhole principle.
• Compute basic discrete probabilities over finite sample spaces.
• Understand and estimate the birthday paradox.
• Implement hash collision detection and birthday paradox simulation in Java.

Concept Overview

The Pigeonhole Principle (PHP)

If $n$ items are placed into $m$ containers and $n > m$, then at least one container holds more than one item.

Formally: For any function $f: A \to B$, if $|A| > |B|$, then $f$ is not injective. (Module 5!)

Generalized Pigeonhole Principle

If $n$ items are placed into $m$ containers, then some container holds at least $\lceil n/m \rceil$ items.

Applications

Simple Probability

For a finite sample space $S$ where all outcomes are equally likely:

The Birthday Problem: In a group of $k$ people, what is the probability that at least two share a birthday?

At $k = 23$, $P(\text{match}) \approx 0.507$ — more than 50%.

At $k = 70$, $P(\text{match}) > 0.999$.

Birthday Paradox and Hash Collisions

For a hash table with $m$ slots, the expected number of keys before the first collision is approximately $\sqrt{\pi m / 2}$ (birthday bound). This is why a 128-bit hash gives $\approx 2^{64}$ collision resistance, not $2^{128}$.

Formal Notation

Worked Examples

Example 1: Birthday Months

In a group of 13 people, prove that at least 2 share a birth month.

Proof: There are 13 people (items) and 12 months (containers). By PHP, at least one month contains $\geq 2$ people. $\blacksquare$

Example 2: Sock Drawer

A drawer contains 10 red socks and 10 blue socks. How many must you draw (in the dark) to guarantee a matching pair?

$m = 2$ colors. Need $m + 1 = 3$ socks.

Example 3: Generalized PHP in Load Balancing

7 tasks are assigned to 3 servers. Show that some server gets at least 3 tasks.

$\lceil 7/3 \rceil = 3$. By the generalized PHP, at least one server handles $\geq 3$ tasks. $\blacksquare$

Example 4: Hash Table Collision

A hash table has 1000 slots. How many keys can be inserted before a collision is guaranteed?

Guaranteed: $1001$ keys (by PHP).

Expected (birthday bound): $\approx \sqrt{\pi \cdot 1000 / 2} \approx 39.6$, so expect a collision around 40 keys.

Example 5: Probability — Drawing Cards

From a standard 52-card deck, draw 5 cards. What is the probability of getting exactly 2 aces?

Proof Techniques Spotlight

Existence Proofs via PHP

The pigeonhole principle is a powerful tool for existence proofs — proving that something must exist without constructing it explicitly.

Theorem: Among any 5 points placed in a $1 \times 1$ square, at least two are within distance $\frac{\sqrt{2}}{2}$ of each other.

Proof: Divide the square into 4 smaller squares of side $\frac{1}{2}$. By PHP ($5$ points, $4$ squares), at least two points are in the same small square. The diameter of a $\frac{1}{2} \times \frac{1}{2}$ square is $\frac{\sqrt{2}}{2}$. $\blacksquare$

Counting Complement

To find $P(E)$, compute $P(\overline{E})$ instead:

This technique powers the birthday problem calculation and many other problems.

Java Deep Dive

import java.util.*;
import java.util.stream.*;

public class PigeonholeAndProbability {

    // --- Pigeonhole Demonstration: Hash Collisions ---

    /**
     * Insert keys into a hash table of size m.
     * Returns the number of keys inserted before the first collision.
     */
    public static int firstCollision(int[] keys, int tableSize) {
        boolean[] occupied = new boolean[tableSize];
        for (int i = 0; i < keys.length; i++) {
            int slot = Math.floorMod(keys[i], tableSize);
            if (occupied[slot]) return i + 1; // collision on (i+1)-th key
            occupied[slot] = true;
        }
        return -1; // no collision
    }

    /**
     * Demonstrate the pigeonhole principle:
     * inserting tableSize+1 distinct hash keys guarantees a collision.
     */
    public static void demonstratePHP(int tableSize) {
        int[] keys = IntStream.range(0, tableSize + 1).toArray();
        int col = firstCollision(keys, tableSize);
        System.out.println("Table size: " + tableSize + ", keys: " + (tableSize + 1)
                + " → first collision at key #" + col);
    }

    // --- Generalized PHP ---

    /**
     * Given n items in m containers, the minimum items in the
     * fullest container is ceil(n/m).
     */
    public static int generalizedPHP(int n, int m) {
        return (n + m - 1) / m; // integer ceiling
    }

    /**
     * Simulate random distribution of n items into m containers.
     * Returns the maximum load.
     */
    public static int simulateMaxLoad(int n, int m, Random rng) {
        int[] counts = new int[m];
        for (int i = 0; i < n; i++) counts[rng.nextInt(m)]++;
        return Arrays.stream(counts).max().orElse(0);
    }

    // --- Birthday Problem ---

    /**
     * Exact probability that among k people, at least two share
     * a birthday (assuming 365 equally likely birthdays).
     */
    public static double birthdayProbExact(int k) {
        if (k > 365) return 1.0;
        double pNoMatch = 1.0;
        for (int i = 1; i < k; i++) {
            pNoMatch *= (365.0 - i) / 365.0;
        }
        return 1.0 - pNoMatch;
    }

    /**
     * Monte Carlo simulation: estimate birthday collision probability.
     */
    public static double birthdayProbMonteCarlo(int k, int trials) {
        Random rng = new Random(42);
        int collisions = 0;
        for (int t = 0; t < trials; t++) {
            Set<Integer> seen = new HashSet<>();
            boolean found = false;
            for (int i = 0; i < k; i++) {
                int day = rng.nextInt(365);
                if (!seen.add(day)) { found = true; break; }
            }
            if (found) collisions++;
        }
        return (double) collisions / trials;
    }

    /**
     * Birthday bound approximation: expected keys to first collision
     * in a hash table of size m is sqrt(pi * m / 2).
     */
    public static double birthdayBound(int m) {
        return Math.sqrt(Math.PI * m / 2.0);
    }

    // --- Simple Probability ---

    /**
     * P(E) = |E| / |S| for equally likely outcomes.
     */
    public static double uniformProbability(long eventSize, long sampleSize) {
        return (double) eventSize / sampleSize;
    }

    // --- Reusing C(n,k) from Class 2 ---

    public static long binomial(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (k == 0 || k == n) return 1;
        if (k > n - k) k = n - k;
        long result = 1;
        for (int i = 0; i < k; i++) {
            result = result * (n - i) / (i + 1);
        }
        return result;
    }

    // --- Monte Carlo: First Collision in Hash Table ---

    /**
     * Simulate inserting random keys into a table of size m.
     * Returns the average number of insertions until first collision.
     */
    public static double avgFirstCollision(int m, int trials) {
        Random rng = new Random(42);
        long totalInserts = 0;
        for (int t = 0; t < trials; t++) {
            Set<Integer> used = new HashSet<>();
            int count = 0;
            while (true) {
                int slot = rng.nextInt(m);
                count++;
                if (!used.add(slot)) break;
            }
            totalInserts += count;
        }
        return (double) totalInserts / trials;
    }

    // --- Demo ---

    public static void main(String[] args) {
        System.out.println("=== Pigeonhole Principle & Probability ===\n");

        // PHP Demonstration
        demonstratePHP(10);
        demonstratePHP(100);

        // Generalized PHP
        System.out.println("\n7 tasks, 3 servers: max load >= "
                + generalizedPHP(7, 3));

        // Simulated load balancing
        Random rng = new Random(42);
        int maxLoad = simulateMaxLoad(7, 3, rng);
        System.out.println("Simulated max load (7 tasks, 3 servers): " + maxLoad);

        // Birthday problem
        System.out.println("\n--- Birthday Problem ---");
        for (int k : new int[]{10, 20, 23, 30, 50, 70}) {
            System.out.printf("k=%2d: exact=%.4f, monte carlo=%.4f%n",
                    k, birthdayProbExact(k),
                    birthdayProbMonteCarlo(k, 100000));
        }

        // Birthday bound for hash tables
        System.out.println("\n--- Birthday Bound ---");
        for (int m : new int[]{100, 1000, 1_000_000}) {
            System.out.printf("m=%,d: bound=%.1f, simulated avg=%.1f%n",
                    m, birthdayBound(m), avgFirstCollision(m, 10000));
        }

        // Probability: 2 aces in 5-card hand
        long event = binomial(4, 2) * binomial(48, 3);
        long sample = binomial(52, 5);
        System.out.printf("\nP(exactly 2 aces in 5-card hand) = %d/%d = %.4f%n",
                event, sample, uniformProbability(event, sample));
    }
}

Historical Context

The pigeonhole principle (Dirichlet's box principle) is attributed to Peter Gustav Lejeune Dirichlet (1834), though the idea was used informally much earlier. The German name Schubfachprinzip ("drawer principle") reflects its intuitive roots.

The birthday problem was posed by Richard von Mises in 1939 and is a staple of probability courses because it so effectively challenges human intuition. Hash table designers rely on its mathematics daily.

Probability theory grew from correspondence between Blaise Pascal and Pierre de Fermat in 1654 about gambling problems — the same Pascal from Class 2's triangle.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. State the pigeonhole principle. What does it guarantee?

A2. There are 367 students in a class. What can you conclude about their birthdays?

A3. Why is the birthday paradox surprising? At what group size does the probability hit 50%?

A4. How does the birthday bound relate to the security of a hash function with $n$-bit output?

Slide Set B: Proof Problems

B1. Prove: among any 5 integers, at least two have the same remainder when divided by 4.

B2. Prove: in any group of 6 people, either 3 mutually know each other or 3 mutually don't. (Hint: fix one person, apply PHP to classify the other 5.)

B3. Prove the generalized PHP: if $n$ items are in $m$ containers, some container has $\geq \lceil n/m \rceil$ items.

Slide Set C: Java Coding Problems

C1. Write a program that inserts $n$ random keys into a hash table of size $m$ and reports the first collision.

C2. Simulate the birthday problem 100,000 times for $k = 1, 2, ..., 50$ and plot exact vs simulated probabilities.

C3. Implement generalizedPHP(n, m) and verify experimentally by distributing $n$ random balls into $m$ bins.

Full Problem Set

Discrete Math Problems

DM1. A store has 6 types of fruit. How many pieces must you buy to guarantee at least 4 of the same type?

DM2. Prove: among any 10 integers, there exist two whose difference is divisible by 9.

DM3. A deck of 52 cards is dealt to 4 players (13 each). Prove that at least one player has cards of all 4 suits.

DM4. Compute $P(\text{exactly 3 heads in 8 coin flips})$.

DM5. Prove: the number of people in a room who have shaken an odd number of hands is even. (Hint: sum of degrees.)

DM6. In a round-robin tournament with 6 players, prove that at least one player has $\geq 3$ wins or $\geq 3$ losses.

Java Programming Problems

JP1. Implement firstCollision(keys, tableSize). Test with sequential and random keys.

JP2. Compute and display the birthday probability for $k = 1, ..., 60$ (exact and Monte Carlo).

JP3. Simulate the generalized PHP: distribute $n$ balls into $m$ bins 10,000 times and report the average and maximum of the max-load.

JP4. Implement a simple hash table with chaining. Insert 2000 random keys into a 1000-slot table. Report the maximum chain length and compare with $\lceil 2000/1000 \rceil = 2$ (PHP bound) vs actual.

JP5. Merge the counting functions from Classes 1–3 into a single CombinatoricsToolkit class with binomial, permutations, inclusionExclusion, birthdayProb, and firstCollision.

Bridge Problems

BR1. Module 5: $f: A \to B$ with $|A| > |B|$ is not injective. That is the pigeonhole principle. Give three different interpretations (functions, hash tables, birthdays) and implement each in Java.

BR2. Module 7 Class 1 used inclusion-exclusion. The birthday problem can also be solved with inclusion-exclusion over pairwise collisions (though it's harder). Set up the formula for $k = 3$ people and verify numerically.

BR3. Module 4: $|\mathcal{P}(A)| = 2^n$. A random subset of $A$ is equally likely to be any of $2^n$ subsets. What is $P(|S| = k)$? This equals $\binom{n}{k}/2^n$. Verify in Java by random sampling.

Solutions

Discrete Math Solutions

DM1. By generalized PHP: $\lceil n / 6 \rceil \geq 4 \Rightarrow n \geq 19$. Buy 19 pieces.

DM2. There are 9 possible remainders mod 9 ($\{0,...,8\}$). 10 integers → by PHP, two share a remainder. Their difference is divisible by 9. $\blacksquare$

DM3. The 4 players receive $4 \times 13 = 52$ cards covering all 4 suits. Each suit has 13 cards distributed among 4 players. If any player had cards of $\leq 3$ suits, those 3 suits contribute at most $13 \times 3 = 39$ cards total to those players. But we actually need a cleaner argument: Each player gets 13 cards from 4 suits. By PHP, any player with 13 cards from 4 suits needs $\lceil 13/4 \rceil = 4$ from some suit, but that doesn't immediately help. Instead: There are 4 suits. A player misses a suit only if they get 0 from that suit. Across all 4 players, total suit-appearances is $4 \times 13 = 52$. But we just need to show one player has all 4 suits. By PHP on suits: each suit has 13 cards among 4 players, so at most 3 players can miss a given suit. Across 4 suits, at most $3 \times 4 = 12$ (player, missed-suit) pairs. But there are 4 players, each with at most 3 missable suits, totalling at most 12 misses—so it's possible all miss 3. A more direct route: this is not provable in general; counterexample: deal each suit entirely to one player. Corrected statement: "at least one player has cards from at least $\lceil 13 \times 4 / 52 \rceil$ suits" is trivially 1. The correct pigeonhole application: since 13 > 4, a player with 13 cards from 4 available suits must have at least $\lceil 13/4 \rceil = 4$ cards of the same suit. But actually: each player gets 13 cards drawn from all 4 suits so must touch at least $\lceil 13/(13) \rceil = 1$ suit, and since cards come from a shuffled deck, any player could get all one suit. The claim as stated isn't necessarily true — it requires additional conditions. We replace this problem.

DM3 (Revised). 13 cards are dealt to one player from a 52-card deck containing 4 suits of 13 cards. Prove the player has at least $\lceil 13/4 \rceil = 4$ cards of the same suit. Proof: 13 cards are distributed among 4 suits (containers). By generalized PHP, at least one suit has $\lceil 13/4 \rceil = 4$ cards. $\blacksquare$

DM4. $P = \frac{\binom{8}{3}}{2^8} = \frac{56}{256} = \frac{7}{32} \approx 0.2188$.

DM5. Let $d_i$ = number of handshakes for person $i$. The sum $\sum d_i$ is even (each handshake counted twice). The people with odd $d_i$ contribute an odd amount each; for the total to be even, there must be an even number of odd contributors. $\blacksquare$

DM6. Each player plays 5 games. If a player has $\leq 2$ wins, they have $\geq 3$ losses. If a player has $\geq 3$ wins, we're done. $\blacksquare$