Guichard-Combinatorics-Graph-Theory · Problem 2.1.4

Inclusion-Exclusion

Mathematics — Probability · stirling-numbers-inclusion-exclusion

Problem

Recall that {nk}\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≥k≥0n \geq k \geq 0, {nk}=1k!∑i=0k(−1)k−iin(ki).\left\{\begin{array}{c} n \\ k \end{array}\right\} = \frac{1}{k!} \sum_{i=0}^{k} (-1)^{k-i} i^n \binom{k}{i}. Do n=0n = 0 as a special case, then use inclusion-exclusion for the rest. You may assume, by convention, that 00=10^0 = 1.

Related theory

Browse the problem library