Enumeration of permutations classified by length of longest monotone subsequences
Isamu Kobayashi, Hiroyoshi Morita, М. Hoshi · 2002
The aim of the paper is to look at the distance structure of the permutation space S/sub n/ from the viewpoint of monotone subsequences. An insertion-deletion (moving) operation on permutations which is considered to be the dual concept of monotone subsequencer L is introduced, under which the authors obtain a n formula to clarify the distance structure of the space. As a by-product of the recursion formula, another combinatorial proof for c/spl les/2 is obtained.>