6533b834fe1ef96bd129cc3e
RESEARCH PRODUCT
More restrictive Gray codes for some classes of pattern avoiding permutations
Jean-luc Barilsubject
Fibonacci number010103 numerical & computational mathematics0102 computer and information sciences01 natural sciencesComputer Science ApplicationsTheoretical Computer ScienceCatalan numberCombinatoricsGray codePermutation010201 computation theory & mathematics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]Signal ProcessingOrder (group theory)0101 mathematicsComputingMilieux_MISCELLANEOUSBinomial coefficientInformation SystemsMathematicsdescription
In a recent article [W.M.B. Dukes, M.F. Flanagan, T. Mansour, V. Vajnovszki, Combinatorial Gray codes for classes of pattern avoiding permutations, Theoret. Comput. Sci. 396 (2008) 35-49], Dukes, Flanagan, Mansour and Vajnovszki present Gray codes for several families of pattern avoiding permutations. In their Gray codes two consecutive objects differ in at most four or five positions, which is not optimal. In this paper, we present a unified construction in order to refine their results (or to find other Gray codes). In particular, we obtain more restrictive Gray codes for the two Wilf classes of Catalan permutations of length n; two consecutive objects differ in at most two or three positions which is optimal for n odd. Other refinements have been found for permutation sets enumerated by the numbers of Schroder, Pell, even index Fibonacci numbers and the central binomial coefficients. A general efficient generating algorithm is also given.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-06-01 | Information Processing Letters |