The Möbius function of separable and decomposable permutations

Burstein, Alexander and Jelínek, Vít and Jelínková, Eva and Steingrimsson, Einar (2011) The Möbius function of separable and decomposable permutations. Journal of Combinatorial Theory Series A, 118 (8). 2346–2364. (https://doi.org/10.1016/j.jcta.2011.06.002)

[thumbnail of mobius.pdf]
Preview
 PDF. Filename: mobius.pdf
Preprint
Download (400kB)| Preview

Abstract

We give a recursive formula for the Moebius 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 Moebius 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. A consequence of the formula is that the Moebius function of such an interval $[\sigma,\pi]$ is bounded by the number of occurrences of $\sigma$ as a pattern in $\pi$. We also show that for any separable permutation $\pi$ the Moebius function of $(1,\pi)$ is either 0, 1 or -1.

ORCID iDs

Burstein, Alexander, Jelínek, Vít, Jelínková, Eva and Steingrimsson, Einar ORCID logoORCID: https://orcid.org/0000-0003-4611-0849;
  • Item type:Article
    ID code:33802
    Dates:
    Date
    Event
    November 2011
    Published
    Keywords:Möbius function , poset , permutations, pattern containment, Electronic computers. Computer science, Discrete Mathematics and Combinatorics, Computational Theory and Mathematics, Theoretical Computer Science
    Subjects:Science > Mathematics > Electronic computers. Computer science
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:19 Oct 2011 15:40
    Last modified:23 Feb 2022 01:17
    URI:https://strathprints.strath.ac.uk/id/eprint/33802
CORE (COnnecting REpositories)