Some combinatorics on trees and functions

Throughout, we let ${|S|}$ denote the cardinality of a finite set $S$.

Recall that the Stirling numbers of the second kind $S(n, k)$ can be defined as the coefficients that express powers of an indeterminate $x$ as linear combinations of falling powers of $x$:

$x^n = \sum_k S(n, k) x^{\underline{k}}$

where $x^{\underline{0}} \coloneqq 1$ and $x^{\underline{k}} \coloneqq x \cdot (x-1)^{\underline{k-1}}$.

Let $Surj(n, k)$ be the number of surjections from an $n$-element set to a $k$-element set. Then $S(n, k) = \frac{Surj(n, k)}{k!}$.

The assertion is the polynomial identity

$x^n = \sum_k Surj(n, k) \binom{x}{k}$

but this is clear since it holds whenever $x$ is an integer $j$, by a bijective proof: $j^n$ counts the number of functions from an $n$-element set to a $j$-element set, and each such function $f$ factors as a surjection onto some $k$-element subset (of the $j$-element set), followed by the subset inclusion. There are `\binom(j}{k}`

such subset inclusions.

It is well-known (and can be proven by any number of methods, e.g., generating functions) that

$\binom(j}S(n, k) =$

Created on April 27, 2013 at 00:44:04
by
Todd Trimble