Kekkei - Advancing Financial Science For Everyone

Introduction

Mastering combinatorics requires more than formulas - it demands problem-solving strategies. In this lesson, we'll tackle advanced counting problems using techniques like symmetry arguments, bijective reasoning, and clever decompositions.

Learning Objectives:

Apply combinatorial arguments to complex problems
Use symmetry to simplify counting
Construct bijections between sets
Develop systematic problem-solving approaches

Symmetry Arguments

Symmetry can dramatically simplify counting problems by showing that multiple scenarios have equal counts.

Example 1: Circular Arrangements

How many ways to arrange $n$ people around a circular table?

Linear arrangement: $n!$ ways

Circular: Rotations are considered the same. Each circular arrangement corresponds to $n$ linear arrangements (rotate by 0, 1, 2, ..., $n-1$ positions).

$\frac{n!}{n} = (n-1)!$

For 5 people: $(5-1)! = 4! = 24$ circular arrangements.

python

import math

def circular_permutations(n):
    """Circular arrangements of n distinct objects"""
    return math.factorial(n - 1) if n > 0 else 0

# Circular seating for 5 people
n = 5
linear = math.factorial(n)
circular = circular_permutations(n)

print(f"Linear arrangements of {n} people: {linear:,}")
print(f"Circular arrangements of {n} people: {circular:,}")
print(f"\nRatio: {linear} / {circular} = {linear // circular}")
print(f"Each circular arrangement = {n} rotations of a linear arrangement")

# Example with names
people = ['Alice', 'Bob', 'Carol', 'Dave', 'Eve']
print(f"\nCircular arrangements: (n-1)! = {len(people)-1}! = {circular}")

Bijective Proofs

A bijection is a one-to-one correspondence between two sets. If we can construct a bijection $f: A \rightarrow B$ , then $|A| = |B|$ (equal cardinality).

Strategy: To prove $|A| = |B|$ , construct a function $f$ that:

Maps every element of $A$ to exactly one element of $B$
Every element of $B$ is the image of exactly one element of $A$

Example 2: Binary Strings and Subsets

Claim: The number of binary strings of length $n$ equals the number of subsets of an $n$ -element set, both equal to $2^n$ .

Bijection: Map each subset $S \subseteq \{1, 2, ..., n\}$ to a binary string:

Bit $i = 1$ if $i \in S$
Bit $i = 0$ if $i \notin S$

Example for $n=3$ :

$\emptyset \leftrightarrow 000$
$\{1\} \leftrightarrow 100$
$\{2, 3\} \leftrightarrow 011$
$\{1, 2, 3\} \leftrightarrow 111$

This is a perfect bijection, so both sets have size $2^3 = 8$ .

python

def subset_to_binary(subset, n):
    """Convert subset to binary string"""
    binary = ['0'] * n
    for elem in subset:
        binary[elem - 1] = '1'
    return ''.join(binary)

def binary_to_subset(binary_str):
    """Convert binary string to subset"""
    return {i + 1 for i, bit in enumerate(binary_str) if bit == '1'}

# Demonstrate bijection for n=3
n = 3
all_subsets = [
    set(), {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}
]

print(f"Bijection between subsets and binary strings (n={n}):")
print(f"{'Subset':<15} ↔ {'Binary'}")
print("-" * 30)

for subset in all_subsets:
    binary = subset_to_binary(subset, n)
    recovered = binary_to_subset(binary)
    print(f"{str(subset):<15} ↔ {binary}  (verify: {subset == recovered})")

print(f"\nTotal count: {len(all_subsets)} = 2^{n} = {2**n}")

Double Counting

Double counting proves identities by counting the same set in two different ways.

Example 3: Handshake Lemma

At a party with $n$ people, each person shakes hands with $d_i$ others. Prove:

$\sum_{i=1}^{n} d_i = 2 \cdot (\text{number of handshakes})$

Two ways to count:

By people: Each person $i$ contributes $d_i$ to the sum
By handshakes: Each handshake involves 2 people

The sum counts each handshake twice (once per person), so:

$\sum d_i = 2 \times \text{(handshakes)}$

Corollary: The sum of degrees in any graph is even!

Combinatorial Identities

Example 4: Vandermonde's Identity

Prove:

$\binom{m+n}{k} = \sum_{i=0}^{k} \binom{m}{i} \binom{n}{k-i}$

Combinatorial proof:

LHS: Choose $k$ people from a group of $m$ men and $n$ women.

RHS: Count by choosing $i$ men and $k-i$ women for each $i = 0, 1, ..., k$ :

0 men, $k$ women: $\binom{m}{0} \binom{n}{k}$
1 man, $k-1$ women: $\binom{m}{1} \binom{n}{k-1}$
...
$k$ men, 0 women: $\binom{m}{k} \binom{n}{0}$

Both count the same set!

python

from scipy.special import comb

def verify_vandermonde(m, n, k):
    """Verify Vandermonde's identity"""
    # LHS: C(m+n, k)
    lhs = int(comb(m + n, k, exact=True))

    # RHS: sum of C(m,i) * C(n, k-i) for i = 0 to k
    rhs = 0
    terms = []
    for i in range(k + 1):
        if i <= m and (k - i) <= n:
            term = int(comb(m, i, exact=True)) * int(comb(n, k - i, exact=True))
            rhs += term
            terms.append((i, k-i, term))

    return lhs, rhs, terms

# Verify for m=5, n=4, k=3
m, n, k = 5, 4, 3
lhs, rhs, terms = verify_vandermonde(m, n, k)

print(f"Vandermonde's Identity: C({m}+{n}, {k}) = Σ C({m},i)·C({n},{k}-i)")
print(f"\nLHS: C({m+n}, {k}) = {lhs}")
print(f"\nRHS breakdown:")
for i, j, term in terms:
    print(f"  i={i}: C({m},{i}) × C({n},{j}) = {int(comb(m,i,exact=True))} × {int(comb(n,j,exact=True))} = {term}")
print(f"\nRHS total: {rhs}")
print(f"\nVerified: {lhs} = {rhs} ✓" if lhs == rhs else f"Failed: {lhs} ≠ {rhs}")

Problem-Solving Framework

When facing a combinatorics problem:

Identify the structure: Ordered vs unordered? With/without repetition?
Look for symmetry: Can you simplify via rotation, reflection, or equivalence?
Try bijection: Can you map to a simpler, known problem?
Consider cases: Break into disjoint scenarios (Rule of Sum)
Use complementary counting: Sometimes $|A^c|$ is easier than $|A|$
Verify computationally: Enumerate small cases to check your reasoning

Practice Strategy: Work through problems multiple ways. An algebraic proof and a combinatorial proof give different insights. Computational verification builds confidence.

Key Takeaways

Symmetry: Exploit rotational/reflectional symmetry (circular: $(n-1)!$ )
Bijection: One-to-one mapping proves equality of cardinalities
Double counting: Count the same set two ways to prove identities
Combinatorial proofs: Tell a counting story instead of manipulating formulas
Systematic approach: Identify structure, look for patterns, verify with code

Next Module: Generating Functions - a powerful algebraic tool for counting!

Technique	Key Idea	Example
Symmetry	Equal counts for equivalent scenarios	Circular: $(n-1)!$
Bijection	1-to-1 mapping → equal sizes	Subsets ↔ Binary strings
Double counting	Count same set two ways	Handshake lemma
Vandermonde	$\binom{m+n}{k} = \sum \binom{m}{i}\binom{n}{k-i}$	Combinatorial identity

IntroductionFocusStart Focus Mode

Symmetry ArgumentsFocusStart Focus Mode

Example 1: Circular Arrangements

Bijective ProofsFocusStart Focus Mode

Example 2: Binary Strings and Subsets

Double CountingFocusStart Focus Mode

Example 3: Handshake Lemma

Combinatorial IdentitiesFocusStart Focus Mode

Example 4: Vandermonde's Identity

Problem-Solving FrameworkFocusStart Focus Mode

Key TakeawaysFocusStart Focus Mode

Introduction

Symmetry Arguments

Bijective Proofs

Double Counting

Combinatorial Identities

Problem-Solving Framework

Key Takeaways