Todd Trimble 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}}$ .

Lemma

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!}$ .

Proof

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) =

A MathOverflow question

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