The Möbius function of separable and decomposable permutations (Q640846): Difference between revisions

Let \(S_n\) denote the permutations of \(\{1,\dots,n\}\); the union of all \(S_n\) (\(n \in \mathbb{N}\)) forms a poset with respect to pattern containment (also called permutation involvement). The paper is concerned with the Möbius function of this poset: first mentioned by \textit{H. Wilf} [``The patterns of permutations,'' Discrete Math. 257, No.\,2--3, 575--583 (2002; Zbl 1028.05002)], and studied by \textit{B. Sagan} and \textit{V. Vatter} for the case of layered permutations [``The Möbius function of a composition poset,'' J. Algebr. Comb. 24, No.\,2, 117--136 (2006; Zbl 1099.68081)]. Here, the authors consider the case of decomposable permutations (those expressible as direct sums of smaller permutations). They provide a recursive formula for the Möbius function of an interval \([\sigma,\pi]\) when \(\pi\) is decomposable. In the special case when \(\pi\) is separable (obtainable from \(1\) by successive sums and skew sums), the authors obtain a polynomial-time algorithm to compute the Möbius function. This leads to an alternative combinatorial interpretation for the Möbius function of separable permutations in terms of ''normal embeddings''.