In this problem, we define a class of words, so-called generalized rhyme schemes.
Notations are as follows,
$[k]:=\{1, 2, 3, \cdots, k\}$ and $\max^j S$ is the $j$-th largest number in the array $S$.
For example, $\max^1 \{2,4,4,1\}=4$, $\max^2 \{2,4,4,1\}=4$, $\max^3 \{2,4,4,1\}=2$ and $\max^4 \{2,4,4,1\}=1$.
We say a word $w=w_1w_2\cdots w_n$ is a rhyme scheme if
for $j=1$, $w_j\in [1]$,
for $j \gt 1$, $w_j\in [1+\max^1 \{w_1w_2 \cdots w_{j-1}\}]$.
For example, there are $5$ rhyme schemes of length $5$, namely, $1~1~1, 1~1~2, 1~2~1, 1~2~2, 1~2~3$. Rhyme schemes were first studied in Becker's 1946 paper
Rooks and Rhymes. The number of distinct rhyme schemes of length $n$ is counted by famous Bell numbers (
A000110).
Now we want to introduce generalized rhyme schemes.
We say a word $w=w_1w_2\cdots w_n$ is a $k$-rhyme scheme if
for $j=k$, $w_j\in [1]$,
for $j \gt k$, $w_j\in [1+\max^k \{w_1w_2 \cdots w_{j-1}\}]$.
Suppose $a_n^k$ is the number of distinct $k$-rhyme schemes of length $n$. For example, $a_4^2 = 4$ beacause there are four $2$-rhyme schemes, namely, $1~1~2~1, 1~1~2~2, 1~1~1~2, 1~1~1~1$. Apparently, $a_n^1$ is just $n$-th Bell number.
Find $a_n^k$.