Combinatorics and Graph Theory · Problem 2.1.4

Inclusion-Exclusion — David Guichard

Mathematics — Combinatorics · stirling-numbers-inclusion-exclusion

Problem

Recall that

\left\{\begin{array}{c} n \\ k \end{array}\right\}

is a Stirling number of the second kind (definition 1.8.1). Prove that for

n \geq k \geq 0

\left\{\begin{array}{c} n \\ k \end{array}\right\} = \frac{1}{k!} \sum_{i=0}^{k} (-1)^{k-i} i^n \binom{k}{i}.

n = 0

as a special case, then use inclusion-exclusion for the rest. You may assume, by convention, that

0^0 = 1