Combinatorics of Permutations, 2nd Edition

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 ...