Another formulation for Stirling numbers of the second kind

Question

I find another formulation for Stirling numbers of the second kind:

Let $n\ge k\ge 1$. Denote by $$\mathbb N_<^n := \{ \alpha = (\alpha_1,\cdots,\alpha_n): 0\le \alpha_1\le\cdots\le\alpha_n, \alpha_n>0 \}$$ the set of nondecreasing $n$-multi-indices with a positive last element. Now I divide the (increasing) multi-index $(1,\cdots,n)$ into a summation of $k$ multi-indices $\{\alpha^j: j = 1,\cdots k\} \subset \mathbb N_<^n$, i.e., \begin{array}{c} \sum_{j=1}^k \alpha^j_i = i, \quad i = 1,\cdots,n, \\ 0\le \alpha^j_1\le\cdots\le\alpha^j_n, \quad \alpha^j_n>0, \quad j = 1,\cdots k. \end{array} I find that the number of ways of such partitions is the Stirling number of the second kind $\left\{ n\atop k \right\}$.

I can check it by hand. For example, when $n=4$ and $k=2$, we have the following $7$ ways of partitions: \begin{array}{cccc} \hline 0 & 0 & 0 & 1 \\ 1 & 2 & 3 & 3 \\ \hline 0 & 0 & 1 & 1 \\ 1 & 2 & 2 & 3 \\ \hline 0 & 1 & 1 & 1 \\ 1 & 1 & 2 & 3 \\ \hline 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 1 & 2 \\ 1 & 2 & 2 & 2 \\ \hline 0 & 1 & 1 & 2 \\ 1 & 1 & 2 & 2 \\ \hline 0 & 1 & 2 & 2 \\ 1 & 1 & 1 & 2 \\ \hline \end{array} We know from this table that $\left\{ 4\atop 2 \right\} = 7$.

But I don't know how to prove this rigorously. Is it already well-known in combinatorics? Any hints or references will be appreciated.

Answer 1

I get an answer by myself.

Basically, we can find a one-to-one correspondence between partitions of the multi-index $(1,\cdots,n)$ into $k$ multi-indices in $\mathbb N_<^n$ and partitions of the set $\{1,\cdots,n\}$ into $k$ non-empty subsets.

Fix a $k$-partition $\{\alpha^j: j = 1,\cdots, k\} \subset \mathbb N_<^n$ of $(1,\cdots,n)$. Fix a $j$. The locations (from the left) where all nonzero integers in the multi-index $\alpha^j = (\alpha_1^j,\cdots,\alpha_n^j)$ first appear form a set of positive integers, which I denote by $S_j$ and call the location set of $\alpha^j$. I claim that the set of location sets $\{S_j : j = 1,\cdots, k \}$ forms a $k$-partition of $\{1,\cdots,n\}$.

Before proving the claim, let us check an example. Consider the last partition of $(1,2,3,4)$ in the above question, that is, $\{(0,1,2,2), (1,1,1,2)\}$. There are two nonzero integers in $(0,1,2,2)$, which are $1$ and $2$. The location where $1$ first appear is $2$ and that for $2$ is $3$. Thus the location set of $(0,1,2,2)$ is $\{2,3\}$. Similarly, the location set of $(1,1,1,2)$ is $\{1,4\}$. The two location sets $\{2,3\}$ and $\{1,4\}$ exactly form a partition of $\{1,2,3,4\}$.

Now we prove the claim:

• Non-empty: Since there is at least one nonzero element in $\alpha^j$ due to the definition of $\mathbb N_<^n$, the location set $S_j$ must be non-empty.
• Subsets: Since the length of $\alpha^j$ is $n$, the location set $S_j$ must be a subset of $\{1,\cdots,n\}$.
• Disjoint: Suppose on the contrary that the location sets $S_{j_1}$ and $S_{j_2}$ of $\alpha^{j_1}$ and $\alpha^{j_2}$, $j_1\ne j_2$, has a common element, say $i \in \{1,\cdots,n\}$. Then both $\alpha^{j_1}$ and $\alpha^{j_2}$ have a nonzero element appearing firstly at the location $i$. Clearly, $i$ cannot be $1$, since the first elements of $\alpha^{j_1}$ and $\alpha^{j_2}$ are either $1$ or $0$ which cannot be both nonzero. Then $2\le i\le n$. It follows that $\alpha^{j_1}_{i-1} \le \alpha^{j_1}_i - 1$ and $\alpha^{j_2}_{i-1} \le \alpha^{j_2}_i - 1$. Since all other $\alpha^j$'s satisfy $\alpha^j_{i-1} \le \alpha^j_i$ by the definition of $\mathbb N_<^n$, we have $$\sum_{j=1}^k \alpha^j_{i-1} = i-1 \le \sum_{j=1}^k \alpha^j_i - 2 = i-2,$$ which leads to a contradiction. Thus, $S_{j_1}$ and $S_{j_2}$ are disjoint.
• Full union: Suppose on the contrary that there is an integer $i \in \{1,\cdots,n\}$ not included in any $S_j, j = 1,\cdots, k$. This means that none of the integers in $\{1,\cdots,n\}$ first appear in the location $i$ of any $\alpha^j, j = 1,\cdots, k$. This location $i$ cannot be $1$ since only one of $\alpha^j$'s has nonzero first element $1$. Then $2\le i\le n$. It follows that the $i$-th elements of all $\alpha^j$'s are repetitious, i.e., $\alpha^j_i = \alpha^j_{i-1}$ for all $j = 1,\cdots, k$. Thus, $$\sum_{j=1}^k \alpha^j_{i-1} = i-1 = \sum_{j=1}^k \alpha^j_i = i,$$ a contradiction. Thus, the union of $S_j, j = 1,\cdots, k$ is $\{1,\cdots,n\}$.

---

PS: I'm new to combinatorics. I think this formulation for Stirling numbers of the second kind may be classical in some textbooks of combinatorics. If anyone knows references about it, please don't hesitate to put them in the comments. Thanks in advance.