Let $H(n,k)$ be the number of sequences $b_1,b_2, \ldots, b_n$ such: that the largest element is $k$, all numbers $1,2,\ldots,k$ do occur, and the first occurrence of $i$ occurs before the first occurence of $i+1$ for all $i \in \{1,2,\cdots, k-1\}$.
My goal is to show that $H(n,k)= S_{n,k}$ where $S_{n,k}$ denotes the Stirling number of the second kind.
Here is my approach: I started by understanding how these sequences look like and I came up with the following:
$H(2,1) = |\{11\}| =1 = S_{2,1}$
$H(2,2) = |\{12\}| =1 = S_{2,2}$
- $H(3,2) = |\{112, 121,122\}| =3 = S_{3,2}$
I computed couple more to see whats going on. Here is my observation: I realized that $$H(3,2)=1+2(1) = H(2,1) + H(2,2)$$ and that quickly let me realize that $H(n,k)$ will satisfy the well known Stirling number of the second kind relation reccurence which is $$S_{n,k}= S_{n-1,k-1}+ kS_{n-1,k}.$$ Thus, I claim that $H(n,k)= S_{n,k}$.
I tried to show this by induction but I am not show if this make sense: $$H_{n+1,k+1}=H_{n,k} + (k+1) H_{n,k+1}= S_{n,k} + (k+1) S_{n,k+1}= S_{n+1,k+1}$$
I figured this question is related to Express $F(n,k)$ through Stirling Numbers if ...
Is this enough? Any help on this will appreciated.
It's easiest to do this by bijection: given a partition of $\{1,2,\dots,n\}$ into $k$ parts (the things counted by the Stirling numbers) sort the parts by their smallest element, and write down a sequence $b_1, b_2, \dots, b_n$ where $b_i$ is the index of the part containing $i$.
For example, for the partition $\{1,3,7\}, \{2\}, \{4,5,6\}$, we would write down the sequence $1, 2, 1, 3, 3, 3, 1$.
Of course we need to check that distinct partitions give distinct sequences, and that every sequence with maximum $k$ in which the first occurrence of $i$ occurs before the first occurrence of $i+1$ is obtained in this way.
If you want to prove that $H(n,k) = S_{n,k}$ by showing that they satisfy the same recurrence, it's also important to check that they have the same base cases: that they're both $1$ when $k=1$ or $n=k$.