📋 Prerequisites

• Counting Basics

Permutations count arrangements (order matters). Combinations count selections (order doesn't matter). \(The binomial coefficient \binom{n}{k}\) — "n choose k" — is the workhorse of combinatorics. It appears in Pascal's triangle, the binomial theorem, and countless competition problems.

📚 Key Concepts

Combinations: n Choose k

The number of ways to choose k objects from n distinct objects, where order doesn't matter:

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

\(Also written \binom{n}{k} or\) ^{n}C_k.

Intuition: Start with permutations P(n,k) = n!/(n-k)! and divide by k! to account for the fact that the k chosen items can be arranged in k! ways but all count as the same combination.

\(Example: \binom{5}{2} = 10 ways to choose 2 out of 5 items.\)

Key Properties of Binomial Coefficients

• Symmetry: $ \binom{n}{k} = \binom{n}{n-k} $ — choosing k to keep = choosing n-k to leave out
• Boundary: $ \binom{n}{0} = \binom{n}{n} = 1 $
• Single element: $ \binom{n}{1} = n $
• Pascal's identity: $ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} $

Pascal's Triangle

\(Each entry is the sum of the two entries above it. Row n (starting from 0), position k = \binom{n}{k}.\)

          1          row 0
         1 1         row 1
        1 2 1        row 2
       1 3 3 1       row 3
      1 4 6 4 1      row 4
     1 5 10 10 5 1    row 5
      

Row sums: each row n sums to \(2^{n}.\) (All subsets of n elements.)

Combinatorial Proofs

Instead of algebraically manipulating formulas, prove identities by telling a counting story.

\(Example: prove \binom{n}{k} = \binom{n}{n-k} by saying\) "choosing k winners = choosing n-k losers."

Example: prove Pascal's identity by saying "\(the nth element is either included (\binom{n-1}{k-1}) or excluded (\binom{n-1}{k}).\)"

Combinatorial proofs are elegant and often appear in Olympiad problems.

Stars and Bars (隔板法)

Number of ways to distribute n identical objects into k distinct bins:

\[ \binom{n + k - 1}{k - 1} \]

Why: Arrange n stars (objects) and k-1 bars (dividers). Total n+k-1 positions, choose k-1 for bars.

\(Example: distribute 7 identical candies to 3 kids: \binom{7+3-1}{3-1} = \binom{9}{2} = 36 ways.\)

Positive version \((each bin gets at least 1): \binom{n-1}{k-1}\) — put 1 in each bin first, then distribute the rest freely.

Block Method (捆绑法)

When certain items must be adjacent, treat them as a single "block."

Example: arrange 5 people A,B,C,D,E where A and B must sit together.

\(Treat AB as 1 block: 4 items to arrange \\to 4! ways. Times 2! for AB or BA = 4! \\times 2! = 48.\)

Gap Method (插空法)

When certain items must NOT be adjacent, place the other items first, then insert the restricted items into the gaps.

Example: arrange 5 people where A and B must NOT sit together.

Arrange C,D,E first: 3! = 6 ways. Creates 4 gaps (_ C _ D _ E _). Choose 2 gaps for A,B: P(4,2) = 12.

\(Total: 6 \\times 12 = 72. (Check: total arrangements 120, together 48, apart = 120-48 = 72\) ✓)

Complementary Counting (Bridge to Next Module)

Often "at least one" or "not all" problems are easier via complement.

Answer = Total - Bad

We'll develop this fully in the complementary-counting module.

✏️ Example Problems