DM-10

Course 10

Advanced Counting

Explore powerful counting techniques including inclusion-exclusion, generating functions, and special sequences like Catalan and Stirling numbers.

Learning Objectives

Apply inclusion-exclusion principle
Count derangements
Understand generating functions
Solve linear recurrence relations
Calculate Catalan numbers
Use Stirling numbers

1. Inclusion-Exclusion Principle

Theorem 10.1: Inclusion-Exclusion for Two Sets

|A \cup B| = |A| + |B| - |A \cap B|

Theorem 10.2: General Inclusion-Exclusion

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots

Example: Counting with Inclusion-Exclusion

How many integers from 1 to 1000 are divisible by neither 2, 3, nor 5?

Let A = div by 2, B = div by 3, C = div by 5.

$|A \cup B \cup C| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$

Answer: $1000 - 734 = 266$

2. Derangements

Definition 10.1: Derangement

A derangement is a permutation where no element appears in its original position. The number of derangements of n elements is denoted $D_n$ .

Theorem 10.3: Derangement Formula

D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n! \left(1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!}\right)

3. Generating Functions

Definition 10.2: Ordinary Generating Function

The generating function for sequence $a_0, a_1, a_2, \ldots$ is:

G(x) = \sum_{n=0}^{\infty} a_n x^n

Example: Common Generating Functions

$\frac{1}{1-x} = 1 + x + x^2 + \cdots$ (sequence 1, 1, 1, ...)
$\frac{1}{(1-x)^2} = 1 + 2x + 3x^2 + \cdots$ (sequence 1, 2, 3, ...)
$(1+x)^n = \sum \binom{n}{k} x^k$ (binomial coefficients)

4. Solving Recurrence Relations

Theorem 10.4: Solving Degree-2 Recurrences

For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ , solve the characteristic equation:

r^2 - c_1 r - c_2 = 0

If roots $r_1, r_2$ are distinct: $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n$

5. Catalan Numbers

Definition 10.3: Catalan Numbers

C_n = \frac{1}{n+1}\binom{2n}{n}

First values: $1, 1, 2, 5, 14, 42, 132, \ldots$

Example: Things Counted by Catalan Numbers

Ways to correctly match n pairs of parentheses
Full binary trees with n+1 leaves
Ways to triangulate a convex (n+2)-gon
Monotonic lattice paths that don't cross the diagonal

Practice Quiz

Advanced Counting Quiz

Questions

Correct

Accuracy

Using inclusion-exclusion, what is

|A \cup B|

|A| = 30

|B| = 20

, and

|A \cap B| = 5

Easy

Not attempted

How many integers from 1 to 100 are divisible by 2 or 3?

Medium

Not attempted

A derangement is a permutation where no element is in its original position. How many derangements of 3 elements exist?

Medium

Not attempted

What is the generating function for the sequence

1, 1, 1, 1, ...

Medium

Not attempted

The recurrence

a_n = a_{n-1} + a_{n-2}

with

a_0 = 0, a_1 = 1

defines:

Easy

Not attempted

The

n

-th Catalan number counts:

Hard

Not attempted

What is

C_3

(the 3rd Catalan number)?

Medium

Not attempted

Solve

a_n = 2a_{n-1}

with

a_0 = 3

. What is

a_n

Medium

Not attempted

The Stirling number

S(n,k)

counts:

Hard

Not attempted

As n gets large, what fraction of permutations are derangements?

Hard

Not attempted

Frequently Asked Questions

When do I use inclusion-exclusion?

Use it when counting objects that DON'T have certain properties is easier than counting those that DO.

What are generating functions good for?

They transform counting problems into algebraic manipulation—useful for solving recurrences and proving identities.

How do I recognize a Catalan number problem?

Look for: matching parentheses, binary trees, non-crossing partitions, paths below diagonals.