# 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [8 references]

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

### 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⟩

Record views