We shall show an upper bound on the Stirling number of the second kind, a byproduct of a homework exercise of Probabilistic Combinatorics offered by Prof. Tom Bohman.

Definition. A Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of $n$ objects into $k$ non-empty subsets and is denoted by $S(n,k)$.

Proposition. For all $n, k$, we have

Proof. Consider a random bipartite graph with partite sets $U:=[n], V:=[k]$. For each vertex $u\in U$, it (independently) connects to exactly one of the vertices in $V$ uniformly at random. Suppose $X$ is the set of non-isolated vertices in $V$. It is easy to see that

On the other hand, we claim that for any $\emptyset \neq A \subset [k]$ and $i \in [k]\setminus A$,

Note that the claim is equivalent to

Consider the same random bipartite graph with $V$ replaced by $V':=[k]\setminus \{i\}$ and let $X'$ be the set of non-isolated vertices in $V'$. The claim is justified since

Set $A:=[i-1]$ in above for $i = 2, \ldots, k$. Using the multiplication rule with telescoping the conditional probability, we obtain