View in EDS

The Möbius function of separable and decomposable permutations ☆ [☆] Jelínek and Steingrímsson were supported by grant No. 090038012 from the Icelandic Research Fund. Jelínek was also supported by grant Z130-N13 from the Austrian Science Foundation (FWF). Jelínková was supported by project 1M0021620838 of the Czech Ministry of Education.

Saved in:
Bibliographic Details
Title: The Möbius function of separable and decomposable permutations ☆ [☆] Jelínek and Steingrímsson were supported by grant No. 090038012 from the Icelandic Research Fund. Jelínek was also supported by grant Z130-N13 from the Austrian Science Foundation (FWF). Jelínková was supported by project 1M0021620838 of the Czech Ministry of Education.
Authors: Burstein, Alexander1 aburstein@howard.edu, Jelínek, Vít2 jelinek@kam.mff.cuni.cz, Jelínková, Eva3 eva@kam.mff.cuni.cz, Steingrímsson, Einar4 einar@alum.mit.edu
Source: Journal of Combinatorial Theory - Series A. Nov2011, Vol. 118 Issue 8, p2346-2364. 19p.
Subjects: Permutations, Mathematical formulas, Möbius function, Partially ordered sets, Embeddings (Mathematics), Mathematical decomposition, Combinatorics
Abstract: Abstract: We give a recursive formula for the Möbius function of an interval in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π 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. We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of is either 0, 1 or −1. [Copyright &y& Elsevier]
Copyright of Journal of Combinatorial Theory - Series A is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:Abstract: We give a recursive formula for the Möbius function of an interval in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π 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. We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of is either 0, 1 or −1. [Copyright &y& Elsevier]
ISSN:00973165
DOI:10.1016/j.jcta.2011.06.002