The Mobius function of separable and decomposable permutations

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:118

Article

Burstein, Alexander¹  Jelinek, Vit²  Jelinkova, Eva³  Steingrimsson, Einar⁴ 

[1] Howard Univ, Dept Math, Washington, DC 20059 USA

[2] Univ Vienna, Fak Math, A-1090 Vienna, Austria

[3] Charles Univ Prague, Dept Appl Math, Prague 11000, Czech Republic

[4] Univ Strathclyde, Dept Comp & Informat Sci, Glasgow G1 1XH, Lanark, Scotland

关键词: Mobius function;    Pattern poset;    Decomposable permutations;    Separable permutations;   

DOI  :  10.1016/j.jcta.2011.06.002

来源: Elsevier

【 摘 要 】

We give a recursive formula for the Mobius function of an interval [sigma, pi] in the poset of permutations ordered by pattern containment in the case where pi is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1,2, ... , k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Mobius function in the case where sigma and pi are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142. We also show that the Mobius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Mobius function of an interval [sigma, pi] of separable permutations is bounded by the number of occurrences of sigma as a pattern in pi. Another consequence is that for any separable permutation pi the Mobius function of (1, pi) is either 0, 1 or -1. (C) 2011 Elsevier Inc. All rights reserved.

【 授权许可】

Free