The Möbius function of separable and decomposable permutations

Alexander Burstein, Vít Jelínek, Eva Jelínková, Einar Steingrimsson

Research output: Contribution to journalArticle

11 Citations (Scopus)
148 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)2346–2364
Number of pages19
JournalJournal of Combinatorial Theory Series A
Volume118
Issue number8
DOIs
Publication statusPublished - Nov 2011

Fingerprint

Decomposable
Pi
Permutation
Interval
Recursive Formula
Poset
Skew
Explicit Formula

Keywords

  • Möbius function
  • poset
  • permutations
  • pattern containment

Cite this

Burstein, Alexander ; Jelínek, Vít ; Jelínková, Eva ; Steingrimsson, Einar. / The Möbius function of separable and decomposable permutations. In: Journal of Combinatorial Theory Series A . 2011 ; Vol. 118, No. 8. pp. 2346–2364.
@article{bb938ef24e94410f8027d50c40f98227,
title = "The M{\"o}bius function of separable and decomposable permutations",
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.",
keywords = "M{\"o}bius function , poset , permutations, pattern containment",
author = "Alexander Burstein and V{\'i}t Jel{\'i}nek and Eva Jel{\'i}nkov{\'a} and Einar Steingrimsson",
year = "2011",
month = "11",
doi = "10.1016/j.jcta.2011.06.002",
language = "English",
volume = "118",
pages = "2346–2364",
journal = "Journal of Combinatorial Theory Series A",
issn = "0097-3165",
number = "8",

}

The Möbius function of separable and decomposable permutations. / Burstein, Alexander; Jelínek, Vít; Jelínková, Eva; Steingrimsson, Einar.

In: Journal of Combinatorial Theory Series A , Vol. 118, No. 8, 11.2011, p. 2346–2364.

Research output: Contribution to journalArticle

TY - JOUR

T1 - The Möbius function of separable and decomposable permutations

AU - Burstein, Alexander

AU - Jelínek, Vít

AU - Jelínková, Eva

AU - Steingrimsson, Einar

PY - 2011/11

Y1 - 2011/11

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

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

KW - Möbius function

KW - poset

KW - permutations

KW - pattern containment

U2 - 10.1016/j.jcta.2011.06.002

DO - 10.1016/j.jcta.2011.06.002

M3 - Article

VL - 118

SP - 2346

EP - 2364

JO - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

SN - 0097-3165

IS - 8

ER -