The Moebius function of separable and decomposable permutations

Details The Moebius function of separable and decomposable permutations The Moebius function of separable and decomposable permutations

2011-02-08

arxiv.org/abs/1102.1611v1

Mathematics

Combinatorics

20 pages, 2 figures

Scientific paper

We give a recursive formula for the Moebius function of an interval $[\sigma,\pi]$ in the poset of permutations ordered by pattern containment in the case where $\pi$ is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1, 2, ..., k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Moebius function in the case where $\sigma$ and $\pi$ 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. A consequence of the formula is that the Moebius function of such an interval $[\sigma,\pi]$ is bounded by the number of occurrences of $\sigma$ as a pattern in $\pi$. We also show that for any separable permutation $\pi$ the Moebius function of $(1,\pi)$ is either 0, 1 or -1.

Affiliated with

Also associated with

No associations

Rating

The Moebius function of separable and decomposable permutations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Moebius function of separable and decomposable permutations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Moebius function of separable and decomposable permutations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-502550