# Stirling numbers of the second kind and combinatorics

The definition of Stirling numbers of the second kind that I use is: the $$S(n,k)$$ satisfying $$\begin{gather*}\tag{1} \newcommand{\factF}{#1^{\underline{#2}}} \newcommand{\factR}{#1^{\overline{#2}}} x^n=\sum_{k=0}^{n}S(n,k)\factF{x}{k}. \end{gather*}$$

where $$\begin{gather*}\tag{2} \factF{x}{k}=\prod_{j=0}^{k-1}(x-k). \end{gather*}$$

Lemma 1 $$\begin{gather*}\tag{3} S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n. \end{gather*}$$

Lemma 2 The number of ways to partition a set of size $$n$$ distinct objects into $$k$$ non-empty unlabelled boxes is $$\tag{4} \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}\binom{k}{j}j^n$$

My goal is to prove Lemma 1, that is (3), and what I have is (1). I see two approaches: (A) direct from (1) (I started with $$j$$-derivatives evaluated at $$0$$); or (B) using the question Combinatorial interpretation of explicit formula for Stirling numbers of the second kind, that shows Lemma 2, replace it in the r.h.s of (1) and show (3). (C) Prove that the $$S(n,k)$$ given by (1) are the number of ways to partition a set as in Lemma 2

All this computations get complicated, and before investing more time into it, I would like to know if there is some simple trick to handle the problem.

Most of what I have read, start from another definition of Stirling numbers of the second kind, the one equivalent given in Lemma 2. I've not found sources starting from the definition that I gave at the beginning of the question.

## 1 Answer

Well, the way I prove it in my class ''Discrete Mathematics'' is to show first directly that the number of surjective mappings from $$[n]$$ onto $$[k]$$ is $$k!\cdot S(n,k)$$.

Second, I prove that the number of surjective mappings from $$[n]$$ onto $$[k]$$ is given by $$\sum_{i=0}^k (-1)^i {k \choose i}(k-i)^n$$ using inclusion-exclusion. Then you have it.

In view of the first statement, I use the definition that $$S(n,k)$$ is the number of partitions of the set $$[n]$$ into $$k$$ subsets (blocks), where $$[n] = \{1,\ldots,n\}$$.

• In the first step, do you mean that you use the definition of $S(n,k)$ as per (1) in the question? That is, using $x^n=\sum_{k=0}^nS(n,k)x^{\underline{x}}$, you get that the number of surjective maps from $[n]$ onto $[k]$ is $k!\cdot S(n,k)$? – Mohamed Ali Jul 29 '19 at 10:40
• Please see my added comment. – Wuestenfux Jul 29 '19 at 11:03
• Now I understand, but the question is exactly about the use of another definition. See my last paragraph. – Mohamed Ali Jul 29 '19 at 11:06