
In One Line and Close. Permutations as Linear Orders. 13
objects. Take a permutation p counted by A(n, k). The k ascending runs of
p then naturally define an ordered partition of [n]intok parts. If k = r,then
there is nothing left to do. If k<r, then we will split up some of the ascending
runs into several blocks of consecutive elements, in order to get an ordered
partition of r blocks. As we currently have k blocks, we have to increase the
number of blocks by r − k. This can be achieved by choosing r − k of the
n −k “gap positions” (gaps between two consecutive entries within the same
block).
This shows that we can generate
r
k=0
A(n, k)
n−k
r−k
ordered ...