Skip to Main content Skip to Navigation
Conference papers

The Möbius function of separable permutations (extended abstract)

Abstract : 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. Using the notion of separating tree, we give a computationally efficient formula for the Möbius function of an interval $(q,p)$ in the poset of separable permutations ordered by pattern containment. A consequence of the formula is that the Möbius function of such an interval $(q,p)$ is bounded by the number of occurrences of $q$ as a pattern in $p$. The formula also implies that for any separable permutation $p$ the Möbius function of $(1,p)$ is either 0, 1 or -1.
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-01186230
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 24, 2015 - 3:43:36 PM
Last modification on : Wednesday, September 26, 2018 - 9:52:01 PM
Long-term archiving on: : Wednesday, November 25, 2015 - 4:16:00 PM

File

dmAN0156.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01186230, version 1

Collections

Citation

Vít Jelínek, Eva Jelínková, Einar Steingrímsson. The Möbius function of separable permutations (extended abstract). 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. pp.773-784. ⟨hal-01186230⟩

Share

Metrics

Record views

85

Files downloads

633