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
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
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


Publisher files allowed on an open archive




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, ⟨10.46298/dmtcs.2805⟩. ⟨hal-01186230⟩



Record views


Files downloads