Permutations, Combinations & Binomial Theorem

This week introduces the fundamental counting principles that underpin combinatorics and discrete mathematics. We cover ordered and unordered selections with and without replacement, binomial coefficients, the Binomial Theorem, and Pascal's triangle. These tools are essential for counting arguments that appear throughout graph theory.

Learning Objectives

Distinguish between ordered and unordered selections with and without replacement

Compute binomial coefficients and prove key identities combinatorially

State and apply the Binomial Theorem

Construct and use Pascal's triangle

Key Concepts

Counting Principles

The foundation of combinatorics rests on two principles:

-Product Rule: If task A can be done in $m$ ways and task B in $n$ ways, then A followed by B can be done in $m \cdot n$ ways
-Sum Rule: If task A can be done in $m$ ways OR task B in $n$ ways (mutually exclusive), then there are $m + n$ ways total

These extend to ordered selections: permutations count arrangements where order matters, while combinations count selections where order does not.

-
Permutations of $n$ objects: $n!$
-
$P(n,k) = n \cdot (n-1) \cdot \ldots \cdot (n-k+1)$
-
$\binom{n}{k} = \binom{n}{n-k}$ (symmetry)
-
Selections with replacement: $n^k$ ordered, $\binom{n+k-1}{k}$ unordered (stars and bars)

Binomial Coefficients & Identities

Binomial coefficients $\binom{n}{k}$ count the number of ways to choose $k$ items from $n$ . They satisfy many useful identities:

-Pascal's Rule: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
-Vandermonde's Identity: $\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k}\binom{n}{r-k}$
-Sum of row: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

-
Pascal's triangle row $n$ gives the coefficients of $(x+y)^n$
-
Setting $x=y=1$ gives $2^n = \sum \binom{n}{k}$
-
Setting $x=1, y=-1$ gives $0 = \sum (-1)^k \binom{n}{k}$ (equal number of even/odd subsets)

W2: Graphs, Isomorphism & Connectivity