---
abstract: 'We present a two term formula for the Möbius function of intervals in the poset of all permutations, ordered by pattern containment. The first term in this formula is the number of so called normal occurrences of one permutation in another. Our definition of normal occurrences is similar to those that have appeared in several variations in the literature on the Möbius function of this and other posets, but simpler than most of them. The second term in the formula is complicated, but we conjecture that it equals zero for a significant proportion of intervals. We present some cases where the second term vanishes and others where it is nonzero. Computing the Möbius function recursively from its definition has exponential complexity, whereas the computation of the first term in our formula is polynomial and the exponential part is isolated to the second term, which seems to often vanish. We also present a result on the Möbius function of posets connected by a poset fibration.'
address: |
    Department of Computer and Information Sciences\
    University of Strathclyde, Glasgow, UK
author:
- Jason P Smith
title: A Formula for the Möbius function of the Permutation Poset Based on a Topological Decomposition
---

Introduction
============

Let $\sigma$ and $\pi$ be permutations of positive integers. We define an *occurrence* of $\sigma$ in $\pi$ to be a subsequence of $\pi$ with the same relative order of size as the letters in $\sigma$. For example, $132$ occurs twice in $23541$, as the subsequences 254 and 354. The *permutation poset* $\mathcal{P}$ consists of all permutations with the partial order $\sigma\le\pi$ if there is an occurrence of $\sigma$ in $\pi$. An *interval* $[\sigma,\pi]$ in $\mathcal{P}$ is the subposet $\{z\in\mathcal{P}\,|\,\sigma\le z\le\pi\}$. The *Möbius function* for a poset is defined recursively as: $\mu(a,b)=0$ if $a\not\le b$, $\mu(a,a)=1$ for all $a$ and, for $a<b$: $$\mu(a,b)=-\sum_{a\le z< b}\mu(a,z).$$

The first systematic study of the Möbius function of general posets appeared in [@Rota64] and the first result pertaining to the Möbius function of intervals of $\mathcal{P}$ appeared in [@SagVat06], where a formula for intervals of *layered* permutations was presented. A layered permutation is the direct sum of decreasing permutations, where the *direct sum* $\sigma\oplus\pi$ of two permutations $\sigma$ and $\pi$ is obtained by appending $\pi$ to $\sigma$ after adding the length of $\sigma$ to each letter of $\pi$. For example, $312\oplus213=312546$. There is an analogous *skew sum* $\sigma\ominus\pi$ where $\pi$ is appended to $\sigma$ after the length of $\pi$ is added to each element of $\sigma$. In [@BJJS11] a formula for the Möbius function is presented for intervals of *decomposable* permutations, that is, permutations that can be written as the direct sum of two or more non-empty permutations. This formula, however, is recursive and bottoms out in intervals bounded by indecomposable permutations, for which there is no general formula for the Möbius function.

Furthermore, in [@BJJS11] a formula is presented for intervals of *separable* permutations, that is, permutations that avoid 2413 and 3142, or equivalently, permutations that can be written using only direct sums, skew sums and the singleton permutation 1. A formula for the Möbius function of intervals of permutations with a fixed number of descents is given in [@Smith14], where a *descent* occurs at position $i$ in a permutation $\pi=\pi_1\ldots\pi_n$ if $\pi_i>\pi_{i+1}$. Further results have been presented in [@McSt13; @Smith13; @SteTen10]. However, the proportion of intervals $[\sigma,\pi]$ which satisfy any of these properties approaches zero as the length of $\pi$ increases. There are indications that the formula we present here reduces the computation of the Möbius function to polynomial time for a significant proportion of intervals.

Many of the results on the Möbius function of intervals of $\mathcal{P}$, and also of some posets of words, are linked to the number of what have been termed *normal occurrences*, or *normal embeddings*, in the literature, see [@Bjo90; @Bjo93; @BJJS11; @SagVat06; @Smith14]. The first appearance of normal occurrences is in Björner’s paper [@Bjo90] where a formula for the Möbius function of intervals of words with subword order is presented. The definition of a normal occurrence has varied in these papers, but all follow a similar theme.

Our definition of normal occurrences, which is simpler than most previous ones, is based upon the *adjacencies* of a permutation, where an adjacency in a permutation is a maximal sequence of increasing or decreasing consecutively valued letters in consecutive positions and the *tail* of an adjacency is all but its first letter. A *normal occurrence* of $\sigma$ in $\pi$, in our definition, is any occurrence that includes all the tails of all the adjacencies of $\pi$. This definition of normal occurrences based on adjacencies does not seem to have been considered previously, but in [@Smith14] we presented a slightly different version.

We present a formula, in Theorem \[thm:main\], that shows the Möbius function of $[\sigma,\pi]$ is, up to a sign, equal to the number of normal occurrences of $\sigma$ in $\pi$ plus an extra term that seems to vanish for a significant proportion of intervals. For example, we know this extra term vanishes if $\sigma$ and $\pi$ have the same number of descents, which is a consequence of the result in [@Smith14]. Using *interval blocks*, which appear in [@SteTen10], we prove that if for all permutations $\lambda\in[\sigma,\pi)$ there is a singleton interval block, that is, a letter of $\pi$ which belongs to no occurrence of $\lambda$, the second term of the formula vanishes. The above mentioned cases are of zero proportion when the length of $\pi$ goes to infinity, but computer tests indicate that for a substantial proportion of intervals the second term of our formula vanishes. Why that is the case is still a mystery, but this suggests that many more families of intervals than are now known may turn out to have a tractable Möbius function.

It is shown in [@McSt13] that if $\pi$ is decomposable and has equal consecutive components then for any subpermutation $\sigma$ obtained by removing $k>1$ of the equal components, the interval $[\sigma,\pi]$ contains a disconnected subinterval. Many of the definitions of normal occurrences have an extra condition for the case when $\pi$ has this property. We prove a result that indicates the second term of our formula for the Möbius function is often non-zero in this case. Exactly what the connection is between this second term and the topology of such intervals is another mystery.

Computing the Möbius function using the original recursive formula has exponential complexity, whereas our formula splits the computation into two parts. The first part, that is, computing the number of normal occurrences, can be done in polynomial time and the second part has exponential complexity in the general case, but computational evidence suggests that in a significant proportion of cases this second term vanishes. Our formula here is the first formula for arbitrary intervals of permutations that seems to have polynomial time complexity for a significant proportion of intervals.

In Section \[sec:defn\] we introduce some definitions, give a brief introduction to the topology of posets and present a poset fibration of $[\sigma,\pi]$ that we later use to compute $\mu(\sigma,\pi)$. In Section \[sec:result\] we present and prove our main result, that the Möbius function of intervals of $\mathcal{P}$ equals the number of normal occurrences plus an extra term that we define. In Section \[sec:fibration\] we present a result that links the Möbius function of two posets connected by a poset fibration satisfying a certain condition. This indicates there is possibly a more general condition for the main result of Björner, Wachs and Welker in [@Bjo05]. In Section \[sec:app\] we apply our formula to show that the Möbius function of $[\sigma,\pi]$ equals the number of normal occurrences of $\sigma$ in $\pi$ if for each $\lambda\in[\sigma,\pi)$ there is at least one letter of $\pi$ which is not in any occurrence of $\lambda$. We also show that the value of the second term of our formula for the Möbius function of $[\sigma,\pi]$ is often nonzero when $\pi$ has a decomposition into a direct sum with consecutive equal components. Furthermore, we consider for which permutations all occurrences are normal.

Definitions and Preliminaries {#sec:defn}
=============================

In this section we introduce some definitions required to present our main result. We begin with an important property of permutations that is fundamental to our results:

\[defn:emb\] An *adjacency* in a permutation is a maximal sequence, of length $\ell\ge1$, of increasing or decreasing consecutively valued letters in consecutive order. The *tail* of an adjacency of length at least 2 is all but the first letter of the adjacency. An adjacency of length 1 does not have a tail.

The permutation $\pi=2314765$ has adjacencies 23, 1, 4 and 765 and the tails are 3 and 65.

Next we define embeddings and our version of normal embeddings. Embeddings are in one-to-one correspondence with occurrences, and we use embeddings instead of occurrences throughout the rest of the paper because they allow for easier presentation of the required definitions.

\[defn:normal\] Consider permutations $\sigma\le\pi$. An *embedding* $\eta$ of $\sigma$ in $\pi$ is a sequence of the same length as $\pi$ such that the nonzero letters in $\eta$ are the letters of an occurrence of $\sigma$ in $\pi$ and in the same positions in $\eta$ as in $\pi$.

An embedding $\eta$ of $\sigma$ in $\pi$ is *normal* if the positions of all the letters in all the tails of the adjacencies in $\pi$ are nonzero in $\eta$. We denote the number of normal embeddings of $\sigma$ in $\pi$ as $\operatorname{\text{\rm NE}}(\sigma,\pi)$.

For $\sigma=132$ and $\pi=2314765$ the sequence $0300065$ is the only normal embedding of $\sigma$ in $\pi$, so $\operatorname{\text{\rm NE}}(\sigma,\pi)=1$.

\[prop:complexity\] Computing $\operatorname{\text{\rm NE}}(\sigma,\pi)$ for a fixed $\sigma$ can be done in time polynomial in the length of $\pi$.

Counting the number of occurrences of $\sigma$ in $\pi$, of lengths $k$ and $n$, respectively, can be done in polynomial time $\mathcal{O}(n^k)$ by exhaustive search, and testing for normality is linear.

We use the adjacencies of a permutation to break down the permutation and embeddings into smaller components.

Consider permutations $\sigma\le\pi$ and an embedding $\eta$ of $\sigma$ in $\pi$. Let $\hat{\pi}=(\hat{\pi}_1,\ldots,\hat{\pi}_t)$ be the decomposition of $\pi$ into its adjacencies, that is, $\hat{\pi}_i$ is a maximal increasing or decreasing permutation corresponding to the $i$’th adjacency of $\pi$.

Define $\hat{\eta}:=(\hat{\eta}_1,\ldots,\hat{\eta}_t)$ where $\hat{\eta}_i$ is the permutation obtained from the nonzero letters that $\eta$ embeds in the $i$’th adjacency of $\pi$. If $\eta$ does not embed in any letters of the $i$’th adjacency then $\hat{\eta}_i=\emptyset$.

If $\sigma=132$ and $\pi=2314765$ then $\hat{\pi}=(12,1,1,321)$ and the embedding $\eta=0010760$ gives $\hat{\eta}=(\emptyset,1,\emptyset,21)$.

When considering embeddings the selection of letters within an adjacency is usually irrelevant. This is made formal by the following equivalence relation.

Let $E^{\sigma,\pi}$ be the set of embeddings of $\sigma$ in $\pi$. Define an equivalence relation on embeddings where $\eta\sim\psi$ if the only differences between $\eta$ and $\psi$ occur within adjacencies of $\pi$. Define $\widehat{E}^{\sigma,\pi}$ as the set containing the rightmost embedding, that is, the embedding where the nonzero letters are the furthest right, of each equivalence class of $E^{\sigma,\pi}\slash\sim$.

Consider $\eta\in \widehat{E}^{\sigma,\pi}$ and define the zero set of $\eta$ as $Z(\eta)=\{i\,|\, \eta_i=0\}$. Define $EZ^{\sigma,\pi}$ to be the set of sets of embeddings in $\widehat{E}^{\sigma,\pi}$ such that for each set $S\in EZ^{\sigma,\pi}$ we have $\bigcap_{\eta\in S}Z(\eta)=\emptyset$.

When defining $\widehat{E}^{\sigma,\pi}$ we choose the rightmost embedding to ensure that all normal embeddings are in $\widehat{E}^{\sigma,\pi}$. Note that if $\eta\sim\psi$ then $\hat{\eta}=\hat{\psi}$, which can be used as an equivalent definition of the equivalence relation. The set $EZ^{\sigma,\pi}$ is upwards closed under containment because if we take any set $S\in EZ^{\sigma,\pi}$ adding a new embedding to $S$ will result in a set that still has empty intersection of zero sets.

\[ex:3\] If $\sigma=132$ and $\pi=413265$ then the embedding $013200$ has zero set $Z(013200)=\{1,5,6\}$ and $$\begin{aligned}
E^{\sigma,\pi}=&\{013200,\,400065,\,010065,\,003065,\,000265\},\\ \widehat{E}^{\sigma,\pi}=&\{013200,\,400065,\,010065,\,000265\}, \\EZ^{\sigma,\pi}=&\{\{013200,\,400065\},\{013200,\,400065,\,010065\},\\ &\{013200,\,400065,\,000265\},\{013200,\,400065,\,010065,\,000265\}\}.\end{aligned}$$

Using our decomposition we build posets from embeddings in the following way:

Given an embedding $\eta\in E^{\sigma,\pi}$ define the poset $P(\eta):=[\hat{\eta}_1,\hat{\pi}_1]\times\cdots\times[\hat{\eta}_t,\hat{\pi}_t]$ and $$A^{\sigma,\pi}:=\bigcup_{\eta\in \widehat{E}^{\sigma,\pi}}P(\eta)^o,$$ where $P(\eta)^o$ denotes the interior of $P(\eta)$, that is, $P(\eta)$ with the top and bottom elements removed.

Consider $[132,413265]$ and let $\eta_1,\eta_2,\eta_3$ and $\eta_4$ be the embeddings listed in $\widehat{E}^{\sigma,\pi}$ in Example \[ex:3\]. Then $\hat{\pi}=(1,1,21,21)$ and $\hat{\eta}_1=(\emptyset,1,21,\emptyset)$, $\hat{\eta}_2=(1,\emptyset,\emptyset,21)$, $\hat{\eta}_3=(\emptyset,1,\emptyset,21)$ and $\hat{\eta}_4=(\emptyset,\emptyset,1,21)$. See Figure \[fig:exA\] for $P(\eta_i)$ and $A^{132,413265}$.

The poset $A^{\sigma,\pi}$ consists of the elements $\hat{\eta}$ for all $\eta\in\widehat{E}^{\lambda,\pi}$ and all $\lambda\in(\sigma,\pi)$. Therefore, we define a surjective poset map $f$ from $A^{\sigma,\pi}$ to $(\sigma,\pi)$ in the following way:

\[defn:map\] Let $f:A^{\sigma,\pi}\rightarrow(\sigma,\pi)$ be the map which maps all elements $\hat{\eta}$, where $\eta\in\widehat{E}^{\lambda,\pi}$, to $\lambda$.

If $[132,413265]$ and $\hat{\eta}=(1,\emptyset,1,21)$ then $\eta=400265\in \widehat{E}^{2143,\pi}$, so $f(\hat{\eta})=2143$.

The Topology of a Poset
-----------------------

We study the topology of a poset by constructing a simplicial complex from the poset in the following way:

Let $P$ be a poset. A *chain* in $P$ is a totally ordered subset $\{z_1<\cdots<z_t\}$. The *order complex* of $P$, denoted $\Delta(P)$, is the simplicial complex whose vertices are the elements of $P$ and whose faces are the chains of $P$.

When we refer to the order complex of an interval $[\sigma,\pi]$ we mean the order complex of the interior $(\sigma,\pi)$, which we denote $\Delta(\sigma,\pi)$.

Consider the interval $I=[123,4567123]$. An example of a chain in $(123,4567123)$ is $4123<456123$. The order complex and Hasse diagram of $I$ are given in Figure \[fig:ordercomplex\].

We refer to a poset and its order complex interchangeably, so a topological property of a poset refers to that property of its order complex. For further background on order complexes and poset topology in general see [@Wac07].

We can use the order complex of $[\sigma,\pi]$ to calculate $\mu(\sigma,\pi)$ due to the following formula, which is an application of the Philip Hall Theorem and the Euler-Poincaré formula for the reduced Euler characteristic, see [@Wac07 Section 1.2]: $$\label{eq:Euler}
\mu(\sigma,\pi)=\tilde{\chi}(\Delta(\sigma,\pi))=\sum_{i=-1}^{|\pi|-|\sigma|}(-1)^i \tilde{\beta}_i(\Delta(\sigma,\pi)),$$ where $\tilde{\chi}$ is the reduced Euler characteristic and $\tilde{\beta}_i$ is the $i$’th reduced Betti number, that is, the rank of the $i$’th reduced homology group. Therefore, by calculating the homology of $[\sigma,\pi]$ we can compute the Möbius function. For example, if we can show that $\Delta(\sigma,\pi)$ is contractible this implies $\mu(\sigma,\pi)=0$, and if $\Delta(\sigma,\pi)$ and $\Delta(\alpha,\beta)$ are homotopically equivalent then $\mu(\sigma,\pi)=\mu(\alpha,\beta)$.

The first explicit results on the topology of intervals of permutations appear in [@McSt13] and [@Smith13].

(-2,0) node\[fill,circle,scale=0.5pt\]; (-2,0) node\[left\] [4123]{}; (0,0) node\[fill,circle,scale=0.5pt\]; (0,0) node\[left\] [2341]{}; (2,0) node\[fill,circle,scale=0.5pt\]; (2,0) node\[right\] [1234]{}; (-2,2) node\[fill,circle,scale=0.5pt\]; (-2,2) node\[left\] [45123]{}; (0,2) node\[fill,circle,scale=0.5pt\]; (0,2) node\[left\] [34512]{}; (2,2) node\[fill,circle,scale=0.5pt\]; (2,2) node\[right\] [23451]{}; (-1,4) node\[fill,circle,scale=0.5pt\]; (-1,4) node\[left\] [456123]{}; (1,4) node\[fill,circle,scale=0.5pt\]; (1,4) node\[right\] [345612]{}; (-2,0) – (-2,2) – (-1,4) – (0,2) – (0,0) – (2,2) – (1,4) – (0,2); (2,2) – (2,0); (5,1) node\[fill,circle,scale=0.5pt\]; (5,1) node\[below\] [4123]{}; (5,4) node\[fill,circle,scale=0.5pt\]; (5,4) node\[above\] [45123]{}; (7,2.5) node\[fill,circle,scale=0.5pt\]; (7,1.7) node [456123]{}; (9,4) node\[fill,circle,scale=0.5pt\]; (9,4) node\[above\] [34512]{}; (9,1) node\[fill,circle,scale=0.5pt\]; (8.7,1) node\[below\] [2341]{}; (11,2.5) node\[fill,circle,scale=0.5pt\]; (11.75,2.5) node\[above\] [345612]{}; (11,0) node\[fill,circle,scale=0.5pt\]; (11,0) node\[below\] [23451]{}; (13,1) node\[fill,circle,scale=0.5pt\]; (13,1) node\[right\] [1234]{}; (7,2.5) – (5,1) – (5,4) – (7,2.5) – (9,4) – (9,1) – (7,2.5); (9,1) – (9,4) – (11,2.5) – (9,1) – (11,0) – (11,2.5) – (9,1); (11,0) – (13,1) – (11,2.5) – (11,0);

The Main Result {#sec:result}
===============

We use the map $f$ in Definition \[defn:map\] to calculate the Möbius function of $[\sigma,\pi]$ by calculating $\mu(A^{\sigma,\pi})$ and the effect on the Möbius function when applying $f$. First we compute $\mu(A^{\sigma,\pi})$. Given a set $A$ of posets the Möbius function of the union of $A$ can be calculated using the following inclusion-exclusion formula, which can be seen as a consequence of the inclusion-exclusion formula for the Euler characteristic and Equation : $$\label{eq:incexGen}\mu\left(\bigcup_{a\in A}a\right)=\sum_{\substack{S\subseteq A\\S\not=\emptyset}}(-1)^{|S|-1}\mu\left(\bigcap_{a\in S}a\right),$$ For more background on this see [@Nar74]. Applying Equation to $A^{\sigma,\pi}$ gives: $$\label{eq:incex}\mu(A^{\sigma,\pi})=\sum_{\substack{S\subseteq \widehat{E}^{\sigma,\pi}\\S\not=\emptyset}}(-1)^{|S|-1}\,\mu(\bigcap_{\eta\in S}P(\eta)^o).$$ To calculate this we need to know the Möbius function of the intersections $\cap_{\eta\in S} P(\eta)^o$. Note that when calculating the Möbius function of a poset we add a top and bottom element. Therefore, a contractible intersection has Möbius function 0, an empty intersection has Möbius function $-1$ and $\mu(P(\eta)^o)=~\mu(\hat{\eta},\hat{\pi})$.

\[lem:inter\] If $S\subseteq \widehat{E}^{\sigma,\pi}$ and $|S|>1$ then: $$\mu(\bigcap_{\eta\in S}P(\eta)^o)=\begin{cases}-1,&\mbox{ if } S\in EZ^{\sigma,\pi}\\0,&\mbox{ otherwise }\end{cases}.$$

Let $\hat{\pi}=(\hat{\pi}_1,\ldots,\hat{\pi}_t)$ and define the *join* of $S$ to be $\vee S=(\max_{\eta\in S}(\hat{\eta}_1),\\\ldots,\max_{\eta\in S}(\hat{\eta}_t))$. The join is well defined because for each $i$ the set $\{\hat{\eta}_i\,|\,\eta\in S\}$ forms a chain, so there is an $\hat{\eta}_i$ that contains all others. The join of $S$ is the smallest element containing every embedding in $S$, so it is the bottom element of the intersection $I=\bigcap_{\eta\in S}P(\eta)^o$. Therefore, if $\vee S<\hat{\pi}$ then $I$ is contractible and so has Möbius function $0$, otherwise $\vee S=\hat{\pi}$ so $I$ is empty and thus has Möbius function $-1$. If $\vee S=\hat{\pi}$ this implies that every letter of $\pi$ is non-zero for some $\eta\in S$, that is, $S$ has empty intersection of zero sets, so $S\in EZ^{\sigma,\pi}$.

Consider our running example of $[132,413265]$. If $S^1=\{013200,\\010065\}$ then $013200$ decomposes to $(\emptyset,1,21,\emptyset)$ and $010065$ decomposes to $\\(\emptyset,1,\emptyset,21)$, so the join is: $$\vee S^1=(\max(\emptyset,\emptyset),\max(1,1),\max(21,\emptyset),\max(\emptyset,21))=(\emptyset,1,21,21).$$ Therefore, $\vee S^1<\hat{\pi}$ so the intersection is contractible. We can check this by looking at Figure \[fig:exA\] where we can see that the intersection $P(013200)\cap P(010065)$ is the single point $(\emptyset,1,21,21)$, which is contractible.

Now that we know the Möbius function of the intersections we can compute $\mu(A^{\sigma,\pi})$:

\[lem:muA\] $$\mu(A^{\sigma,\pi})=(-1)^{|\pi|-|\sigma|}\operatorname{\text{\rm NE}}(\sigma,\pi)+\sum_{S\in EZ^{\sigma,\pi}}(-1)^{|S|}.$$

We can split Equation into two parts: $$\label{eq:incex2}\mu(A^{\sigma,\pi})=\sum_{\eta\in \widehat{E}^{\sigma,\pi}}\mu(P(\eta)^o)+\sum_{\substack{S\subseteq \widehat{E}^{\sigma,\pi}\\|S|>1}}(-1)^{|S|-1}\mu(\bigcap_{\eta\in S}P(\eta)^o).$$ By Lemma \[lem:inter\] the second part of the right hand side of Equation equals $\displaystyle\sum_{S\in EZ^{\sigma,\pi}}(-1)^{|S|}$.

By the definition of $P(\eta)$, and the identity $\mu(A\times B)=\mu(A)\mu(B)$, we know $$\mu(P(\eta)^o)=\prod_{1\le i \le t} \mu(\hat{\eta}_i,\hat{\pi}_i).$$ We know that $[\hat{\eta}_i,\hat{\pi}_i]$ is always a chain, so by the definition of normality if $\eta$ is not normal there is some $i$ such that $|\hat{\eta}_i|\le|\hat{\pi}_i|-2$, so $\mu(\hat{\eta}_i,\hat{\pi}_i)=0$, which implies $\mu(P(\eta)^o)=0$. If $\eta$ is normal then $|\hat{\pi}_i|-|\hat{\eta}_i|=0$ or $1$, so $\mu(\hat{\eta}_i,\hat{\pi}_i)=1$ or $-1$, for all $i$. There are $|\pi|-|\sigma|$ parts $[\hat{\eta}_i,\hat{\pi}_i]$ with $\mu(\hat{\eta}_i,\hat{\pi}_i)=-1$, one for each zero in $\eta$, and the remaining have $\mu(\hat{\eta}_i,\hat{\pi}_i)=1$. Therefore, $\mu(P(\eta)^o)=(-1)^{|\pi|-|\sigma|}$ for each normal embedding, so the first term in the right hand side of Equation  equals $(-1)^{|\pi|-|\sigma|}\operatorname{\text{\rm NE}}(\sigma,\pi)$.

We now present our formula for the Möbius function that applies to any interval of permutations:

\[thm:main\] For any permutations $\sigma$ and $\pi$: $$\label{eq:main}\mu(\sigma,\pi)=(-1)^{|\pi|-|\sigma|}\operatorname{\text{\rm NE}}(\sigma,\pi)+\sum_{\lambda\in[\sigma,\pi)}\mu(\sigma,\lambda)\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}.$$

We take the poset $A^{\sigma,\pi}$ and for each $\lambda\in(\sigma,\pi)$ we retract $\widehat{E}^{\lambda,\pi}$ to a point we denote $\lambda$. This transforms $A^{\sigma,\pi}$ into the interval $(\sigma,\pi)$. We need to know what effect this has on the Möbius function of $A^{\sigma,\pi}$.

We work our way from the bottom to the top so we can assume that all elements below the elements of $\widehat{E}^{\lambda,\pi}$ have already been retracted and all elements above have not. Define the poset $W(\lambda):=\{\tau\in A^{\sigma,\pi}\,|\,\tau\le\eta\text{ or } \tau\ge\eta\text{ for some } \eta\in\widehat{E}^{\lambda,\pi}\}$. When we retract the elements of $\widehat{E}^{\lambda,\pi}$ to $\lambda$ we retract $W(\lambda)$ onto a contractible poset, since in that poset the element $\lambda$ is comparable to all other elements and thus represents a cone point in the corresponding order complex. This implies the change to the Möbius function is $-\mu(W(\lambda))$.

To compute $\mu(W(\lambda))$ we split $W(\lambda)$ into two disjoint parts $$\begin{aligned}
W(\lambda)^<&:=\{\tau\in W(\lambda)\,|\,\tau<\eta\text{ for some } \eta\in\widehat{E}^{\lambda,\pi}\},\\W(\lambda)^\ge&:=\{\tau\in W(\lambda)\,|\,\tau\ge\eta\text{ for some } \eta\in\widehat{E}^{\lambda,\pi}\}.\end{aligned}$$ The poset $W(\lambda)^<$ is isomorphic to $(\sigma,\lambda)$ because all points below $\lambda$ have already been retracted. The poset $W(\lambda)^\ge$ is equal to $\bigcup_{\eta\in\widehat{E}^{\lambda,\pi}}(P(\eta)\setminus\hat{\pi})$ which has Möbius function $-\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}$, by Lemma \[lem:inter\] and the inclusion-exclusion formula (this also follows from the Crosscut Theorem, see Proposition \[prop:crosscut\]).

Because every element of $\widehat{E}^{\lambda,\pi}$ lies above every element of $(\sigma,\lambda)$ this implies $W(\lambda)=W(\lambda)^<\star W(\lambda)^\ge$, where $\star$ denotes the topological join,so $\mu(W(\lambda))=-\mu(W(\lambda)^<)\star\mu( W(\lambda)^\ge)$ by [@Koz08 Theorem 10.23(2)]. Therefore, $$-\mu(W(\lambda))=\mu(\sigma,\lambda)\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}.$$ So we start with $\mu(A^{\sigma,\pi})$, given by Lemma \[lem:muA\], and then subtract $\mu(W(\lambda))$ for each $\lambda\in (\sigma,\pi)$, which gives the desired formula.

\[rem:tests\] Computer tests[^1] indicate that $~95\%$ of intervals $[\sigma,\pi]$, where $|\pi|<9$, satisfy $\mu(\sigma,\pi)=(-1)^{|\pi|-|\sigma|}\operatorname{\text{\rm NE}}(\sigma,\pi)$. Thus, for these intervals the latter term in Equation is zero.

The complexity of counting the number of normal embeddings is polynomial so in the cases where we can show that the latter term of Equation  equals zero we have a polynomial time formula for the Möbius function. This is a dramatic improvement over the original recursive formula that has exponential complexity. However, computing the latter term of Equation also has exponential complexity.

Tests show that using Equation is often much quicker than computing the Möbius function using the recursive formula. When computing the Möbius function of the rank $15$ interval $$[54123, 9\, 7\, 10\, 4\, 8\, 1\, 2\, 6\, 5\, 3\, 19 \,17\, 20\, 14 \,18\, 11\, 12 \,16\, 15\, 13],$$ the formula in Equation took 1.75 minutes and the recursive formula took 13.5 hours. Note that this interval has Möbius function $-3$ but no normal embeddings so the latter term of Equation is nonzero in this case. Furthermore, using Equation  we were able to compute the Möbius function of a rank 16 interval in 1 hour and a rank 17 interval in 6 hours. However, if $\sigma$ has a large number of occurrences in $\pi$ then using Equation can be quite slow. For example, if $\sigma=2413$ and $\pi= 2\, 4\, 6\, 8\, 10\, 1\, 3\, 5\, 7\, 9$ then there are 35 occurrences of $\sigma$ in $\pi$ and $\mu(\sigma,\pi)$ can be computed in 0.06 seconds using the recursive formula but takes 15.5 hours using Equation .

Poset Fibration {#sec:fibration}
---------------

In this subsection we present a generalisation of the argument used to prove Theorem \[thm:main\]. We can view the pair $((\sigma,\pi),\{\widehat{E}^{\lambda,\pi}\}_{\lambda\in(\sigma,\pi)})$ as a poset fibration which makes $f$ the projection map and $A^{\sigma,\pi}$ the total space. In [@Bjo05] various theorems are presented which relate two posets $P$ and $Q$ linked by a poset fibration $f$ satisfying a certain condition, see Theorem 2.5 of [@Bjo05] for the most general form of this condition. However, our poset fibration does not always satisfy this condition, for example the condition is not true on the interval $[1,456123]$. We present a result with a different condition on the poset fibration that generalises the argument in the proof of Theorem \[thm:main\], this result can be seen as an application of [@Wal81 Corollary 3.2]. We let $f^*$ and $f^{-1}$ denote the image and preimage of $f$, respectively.

\[prop:mob2.5\] Let $f:P\rightarrow Q$ be a surjective poset map such that $f^*(P_{<p})=Q_{<q}$, for any $q\in Q$ and $p\in f^{-1}(q)$. Then $$\mu(Q)=\mu(P)+\sum_{q\in Q}\mu(Q_{<q})\mu(f^{-1}(Q_{\ge q})).$$

We begin with $P$ and for each $q\in Q$ we retract $f^{-1}(q)$ to a single point and observe the effect this retraction has on the Möbius function of $P$. We do this inductively from the bottom to the top, so when considering $q\in Q$ we assume all points in $P_{<p}$, for all $p\in f^{-1}(q)$, have been retracted.

To calculate the effect the retraction has on the Möbius function of the poset we consider $$W(q):=\{p\in P\,|\, p<\lambda\text{ or }p\ge\lambda\text{ for some }\lambda\in f^{-1}(q)\}.$$ When we retract $f^{-1}(q)$ to a point we retract $W(q)$ to a contractible poset, which implies the change to the Möbius function is $-\mu(W(q))$. We can rewrite $W(q)$ in the following way: $$\begin{aligned}
W(q)&=\bigcup_{p\in f^{-1}(q)}P_{<p}\star P_{\ge p}=\bigcup_{p\in f^{-1}(q)}Q_{<q}\star P_{\ge p}\\&=Q_{<q}\star\bigcup_{p\in f^{-1}(q)} P_{\ge p}=Q_{<q}\star f^{-1}(Q_{\ge q}).\end{aligned}$$ We can replace $P_{<p}$ with $Q_{<q}$ because our induction assumption is that $P_{<p}$ has been retracted and our condition of the proposition is $f^*(P_{<p})=Q_{<q}$. Therefore, $-\mu(W(q))=\mu(Q_{<q})\mu(f^{-1}(Q_{\ge q}))$ and summing over all $q\in Q$ completes the proof.

An interesting question is whether Proposition \[prop:mob2.5\] can be generalised to show homotopy equivalence. Also, is there a more general condition that encompasses the conditions of both Proposition \[prop:mob2.5\] and Theorem 2.5 of [@Bjo05]?

Applications {#sec:app}
============

By Theorem \[thm:main\] we know the Möbius function is linked to the number of normal embeddings, which depend on the adjacencies.

\[lem:adj\] The average total number of letters in the tails of adjacencies in a permutation of length $n$ is $2(\frac{n-1}{n})$. In particular, when $n$ tends to infinity the average number of letters in the tails of adjacencies tends to 2.

Note first that $k=1$ cannot be in the tail of an increasing adjacency and $n$ cannot be in the tail of a decreasing adjacency. For $k>1$ the number of permutations of length $n$ in which $k$ is in the tail of an increasing adjacency is $(n-1)!$, because these are precisely all permutations of the letters $1,2,\ldots,n$ where $(k-1)k$ is regarded as a single letter. So the probability that a letter $k>1$ is in the tail of an increasing adjacency is $(n-1)!/n!=1/n$. Likewise, the probability that a letter $k<n$ is in the tail of a decreasing adjacency is $1/n$. Therefore, the probability that $k$ is in the tail of an adjacency is $$\label{eq:tail}\begin{cases}\frac{1}{n},&\mbox{ if } k=1 \mbox{ or }  n\\\frac{2}{n},&\mbox{ otherwise}\end{cases}.\nonumber$$ Summing over all letters $k=1,\ldots,n$ completes the proof.

An embedding in a permutation $\pi$ is likely to be normal if there is only a small proportion of letters in the tails of the adjacencies of $\pi$. Therefore, Lemma \[lem:adj\] indicates that the proportion of embeddings of $\lambda$ in a random permutation $\pi$ that are normal increases as the length of $\pi$ increases. If a permutation has no adjacencies of size $\ell>1$ then all embeddings will be normal, the proportion of such permutations tends to $1/e^2$ as the length of the permutations increase, see [@OEISA002464].

By Remark \[rem:tests\] we suspect that the second part of Equation vanishes for a significant proportion of intervals. A consequence of Proposition 3.3 in [@Smith14] is that if $\sigma$ and $\pi$ have the same number of descents then the second part of Equation vanishes. Note that although the definition of normal embeddings in [@Smith14] does not consider decreasing adjacencies, it is equivalent to Definition \[defn:normal\] when the number of descents is fixed. To see this note that if $\sigma$ and $\pi$ have the same number of descents then any letters in $\pi$ that form a decreasing adjacency, and thus a descent, must be nonzero in all embeddings otherwise that descent would not be in $\sigma$, contradicting the assumption that $\sigma$ and $\pi$ have the same number of descents.

One route to simplifying Equation is answering the following question:

\[que:sum\] Given an interval $[\sigma,\pi]$, for which $\lambda\in[\sigma,\pi)$ is the following sum nonzero?: $$\label{eq:sum}\displaystyle\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}.$$

One case where the sum in equals zero is when $EZ^{\lambda,\pi}$ is always empty, which leads us to the following definition and proposition:

We say an interval $[\sigma,\pi]$ has a *single block* if there exists some $i$ such that $\eta_i=0$ for any $\eta\in \widehat{E}^{\sigma,\pi}$. That is, there is a letter in $\pi$ that is not contained in any of the occurrences in $\widehat{E}^{\sigma,\pi}$.

We say an interval is *single* if for all $\lambda\in[\sigma,\pi)$ the interval $[\lambda,\pi]$ has a single block.

Our notation here follows from the idea of interval blocks in [@SteTen10]. Computer tests show that $78.6\%$ of intervals $[\sigma,\pi]$, where $|\pi|<9$, are single and we found that $39\%$ of $48300$ random rank 10 intervals, where $|\sigma|=5$ and $|\pi|=15$, are single. We suspect that the proportion of intervals that are single approaches zero as the rank tends to infinity, because the likelihood that there exists some $\lambda\in[\sigma,\pi]$ such that $[\lambda,\pi]$ does not have a single block increases as the rank of the interval increases.

\[prop:single\] If $[\sigma,\pi]$ is single then $\mu(\sigma,\pi)=(-1)^{|\pi|-|\sigma|}\operatorname{\text{\rm NE}}(\sigma,\pi)$.

If $[\lambda,\pi]$ has a single block then $EZ^{\lambda,\pi}$ must be empty which implies $\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}=~0$. Therefore, if $[\sigma,\pi]$ is single then $\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}=0$ for all $\lambda\in[\sigma,\pi)$, combining this with Equation  completes the proof.

Intervals that contain a disconnected subinterval of rank at least 3 are non-shellable, as shown by Björner in [@Bjo80], and thus not amenable to some of the elegant methods of topological combinatorics, see [@McSt13] for further background. In the rest of the paper we consider a particular type of interval that is known to be disconnected and show that the sum in is nonzero for these intervals. Whether there is a topological “reason" for being nonzero in these cases we don’t know.

We consider decomposable permutations and write them in the form $\pi_1\oplus\cdots\oplus\pi_n$ where each $\pi_i$, which we call a *component* of $\pi$, is indecomposable. Consider a permutation $\pi$, with a sequence of $\ell\ge2$ equal consecutive components, and $\lambda\le\pi$ obtained from $\pi$ by removing $k$ of the components from this sequence, where $\ell>k\ge1$. The interval $[\lambda,\pi]$ is disconnected, which follows from results in [@McSt13], specifically Lemma 4.2 and Theorem 5.6. These intervals are the cause of the extra conditions in the formulas for the Möbius function that appear in [@BJJS11] and [@McSt13].

The simplest permutations with equal consecutive components are the following:

Given an indecomposable permutation $\lambda$ let $$\lambda^n:=\underbrace{\lambda\oplus\cdots\oplus\lambda}_{\times n}.$$

Before we continue let us introduce a very useful result for computing the Möbius function of lattices known as the Crosscut Theorem. We denote the join of $A\subseteq X$ as $\vee A:=\min\{x\in X\,|\,x\ge a\text{ for all } a\in A\}$:

\[prop:crosscut\](Crosscut Theorem, see [@Sta97 Corollary 3.9.4]) Let $L$ be a finite lattice with top element $\hat{1}$ and bottom element $\hat{0}$. Let $X$ be a subset of $L$ such that $\hat{0}\not\in X$ and for all $s\in L$, $s\not=\hat{0}$, there is some $t\in X$ such that $s\ge t$. Then $$\mu(\hat{0},\hat{1})=\sum_{\substack{A\subseteq X\\\vee A=\hat{1}}}(-1)^{|A|}.$$

The Crosscut theorem is traditionally used to compute the Möbius function of a lattice, but we can use it in reverse if we can represent our problem as a lattice for which we already know the Möbius function.

Consider the interval $[\lambda^m,\lambda^n]$, for some indecomposable permutation $\lambda$, the embeddings of $\lambda^m$ in $\lambda^n$ can be considered as subsets of $[n]:=\{1,\ldots,n\}$ of size $m$. So we can regard our problem as that of computing the Möbius function of a sublattice of the Boolean lattice:

The *Boolean lattice* $B_n$ is the poset of subsets of $[n]$ with the partial order given by inclusion.

Define the *truncated Boolean lattice* $B_{n}^{\ge k}$ as the subposet of $B_n$ where all elements $a\in B_n$ such that $|a|< k$ are retracted to a single point $\hat{0}$. Similarly, define $B_{n}^{\le k}$ as the subposet of $B_n$ where all elements $a\in B_n$ such that $|a|> k$ are retracted to a single point $\hat{1}$.

(0,0) – (-3,1) – (-2,2) – (0,3); (0,0) – (-1.75,1) – (-2,2) – (0,3); (0,0) – (0.5,1) – (-0.5,2) – (0,3); (0,0) – (-0.5,1) – (-2,2) – (0,3); (0,0) – (1.75,1) – (2,2) – (0,3); (0,0) – (3,1) – (0.5,2) – (0,3); (3,1) – (2,2); (1.75,1) – (-0.5,2); (-0.5,1) – (2,2); (0.5,1) – (0.5,2); (-1.75,1) – (0.5,2); (-3,1) – (-0.5,2); (0,3) node\[above\] [$1234$]{}; (0,3) node\[fill,circle,scale=0.5pt\]; (-2,2.1) node\[left\] [$123$]{}; (-2,2) node\[fill,circle,scale=0.5pt\]; (-0.5,2.1) node\[left\] [$124$]{}; (-0.5,2) node\[fill,circle,scale=0.5pt\]; (0.5,2.1) node\[right\] [$134$]{}; (0.5,2) node\[fill,circle,scale=0.5pt\]; (2,2.1) node\[right\] [$234$]{}; (2,2) node\[fill,circle,scale=0.5pt\]; (-3,.95) node\[left\] [$12$]{}; (-3,1) node\[fill,circle,scale=0.5pt\]; (-1.75,.95) node\[left\] [$13$]{}; (-1.75,1) node\[fill,circle,scale=0.5pt\]; (-0.5,.95) node\[left\] [$23$]{}; (-0.5,1) node\[fill,circle,scale=0.5pt\]; (0.5,.95) node\[right\] [$14$]{}; (0.5,1) node\[fill,circle,scale=0.5pt\]; (1.75,.95) node\[right\] [$24$]{}; (1.75,1) node\[fill,circle,scale=0.5pt\]; (3,.95) node\[right\] [$34$]{}; (3,1) node\[fill,circle,scale=0.5pt\]; (0,0) node\[below\] [$\hat{0}$]{}; (0,0) node\[fill,circle,scale=0.5pt\]; (6,0) – (4.5,1) – (6,2); (6,0) – (5.5,1) – (6,2); (6,0) – (6.5,1) – (6,2); (6,0) – (7.5,1) – (6,2); (6,2) node\[above\] [$\hat{1}$]{}; (6,2) node\[fill,circle,scale=0.5pt\]; (4.5,1) node\[left\] [$1$]{}; (4.5,1) node\[fill,circle,scale=0.5pt\]; (5.5,1) node\[left\] [$2$]{}; (5.5,1) node\[fill,circle,scale=0.5pt\]; (6.5,1) node\[right\] [$3$]{}; (6.5,1) node\[fill,circle,scale=0.5pt\]; (7.5,1) node\[right\] [$4$]{}; (7.5,1) node\[fill,circle,scale=0.5pt\]; (6,0) node\[below\] [$\emptyset$]{}; (6,0) node\[fill,circle,scale=0.5pt\];

We take the notation for a truncated Boolean lattice from [@Wac07 Section 3.2.1]. See Figure \[fig:partialboolean\] for examples of truncated Boolean lattices. The embeddings of $\lambda^m$ in $\lambda^n$ can be viewed as the atoms of the truncated Boolean lattice $B_n^{\ge m}$, so using the Crosscut theorem we can compute the sum in for $[\lambda^m,\lambda^n]$ by computing $\mu(B_n^{\ge m})$. The Möbius function of a Boolean lattice is given by $\mu(B_n)=(-1)^n$, see [@Rota64 Section 3]. We can use this to compute the Möbius function of the truncated Boolean lattice.

\[lem:parBool\] The Möbius function of a truncated Boolean lattice is given by: $$\mu(B_{n}^{\le k})=(-1)^{k-1}\dbinom{n-1}{k} \hskip30pt \text{ and }\hskip30pt\mu(B_n^{\ge k})=(-1)^{n-k-1}\dbinom{n-1}{k-1}.$$

First consider $B_{n}^{\le k}$. For each element $\lambda\in B_{n}^{\le k}$, with $|\lambda|=\ell$, the interval $[\emptyset,\lambda]$ is isomorphic to the boolean lattice $B_\ell$, therefore $\mu(\emptyset,\lambda)=(-1)^\ell$. There are $\binom{n}{\ell}$ elements in $B_{n}^{\le k}$ with size $\ell$, for $0\le\ell\le k$. To compute $\mu(B_{n}^{\le k})$ we need to sum all elements and negate, we do this by summing over $\ell$. We can then apply an identity on the alternating sum of binomial coefficients, a proof of which can be found in Section 0 of [@Kle63], this gives: $$\mu(B_{n}^{\le k})=-\sum_{\ell=0}^{k}(-1)^{\ell}\binom{n}{\ell}=(-1)^{k}\binom{n-1}{k}.$$ Note that the lattice $B_n^{\ge k}$ is isomorphic to $(B_{n}^{\le n-k})^*$, the dual of $B_{n}^{\le n-k}$, that is, the lattice with the partial order reversed. Therefore, $\mu(B_n^{\ge k})=\mu((B_{n}^{\le n-k})^*)=\mu(B_{n}^{\le n-k})$ which completes the proof.

We can now present our result for the interval $[\lambda^m,\lambda^n]$:

\[prop:countEmb\] Let $\lambda$ be an indecomposable permutation, of length $\ell>1$, and consider the interval $[\lambda^m,\lambda^n]$. Then: $$\sum_{S\in EZ^{\lambda^m,\lambda^n}}(-1)^{|S|}=(-1)^{n-m-1}\dbinom{n-1}{m-1}.$$

We can consider each embedding of $\lambda^m$ in $\lambda^n$ as a subset $a\subseteq\{1,\ldots,n\}$ with $|a|=m$. Therefore, the embeddings correspond to the atoms of the lattice $B_n^{\ge m}$. So we can apply the Crosscut theorem and Lemma \[lem:parBool\] to complete the proof.

We can generalise this result by adding in other components to the permutations to get the following proposition:

\[prop:conSeq\] Consider a decomposable permutation $\pi=\pi_1\oplus\cdots\oplus\pi_n$ with a sequence of consecutive components $\pi_{i+1}=\cdots=\pi_{i+\alpha}$, with $\alpha>1$. Let $\lambda=\lambda_1\oplus\cdots\oplus\lambda_m$ be the subpermutation of $\pi$ obtained by reducing the sequence of equal components to length $\ell$, where $0\le \ell\le \alpha$. Then: $$\label{eq:conSeq}\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}=(-1)^{\alpha-\ell-1}\dbinom{\alpha-1}{\ell-1}.$$

Consider $W(\lambda,\pi):=\bigcup_{\eta\in\widehat{E}^{\lambda,\pi}}(P(\eta)\setminus\hat{\pi})$. The proof of Theorem \[thm:main\] shows that $\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}=\mu(W(\lambda,\pi))$. We show that $W(\lambda,\pi)$ is homotopy equivalent to $W(\pi_{i+1}^\ell,\pi_{i+1}^\alpha)$, which along with Proposition \[prop:countEmb\] implies the result.

To show that $W(\lambda,\pi)$ and $W(\pi_{i+1}^\ell,\pi_{i+1}^\alpha)$ are homotopy equivalent we use the Quillen Fiber Lemma, see [@Koz08 Theorem 15.28]. To do this we use the map $g:W(\lambda,\pi)\rightarrow W(\pi_{i+1}^\ell,\pi_{i+1}^\alpha)$, defined in the following way. Consider $\hat{\eta}\in W(\lambda,\pi)$, then $\hat{\eta}$ is a decomposition of an embedding $\eta$ of a permutation of the form $\tau=\pi_1\oplus\cdots\pi_i\oplus\tilde{\tau}\oplus\pi_{i+\alpha+1}\oplus\cdots\oplus\pi_n$ and let $g(\hat{\eta})$ be the decomposition of the embedding of $\tilde{\tau}$ in $\pi_{i+1}\oplus\cdots\oplus\pi_{i+\alpha}$.

To apply the Quillen Fiber Lemma we need to show that $D(x):=\Delta(g^{-1}(W(\pi_{i+1}^\ell,\pi_{i+1}^\alpha)_{\ge x}))$ is contractible for all $x\in W(\pi_{i+1}^\ell,\pi_{i+1}^\alpha)$. Let $\hat{\phi}^1,\ldots,\hat{\phi}^k$ be the minimal elements of $D(x)$. The posets $W(\lambda,\pi)_{\ge\hat{\phi}^i}$ are contractible, for all $i=1,\ldots,k$, because each has a unique minimal element $\hat{\phi}^i$. So if we can show that their intersection is also contractible that implies $D(x)$ is contractible.

All the minimal elements $\hat{\phi}^i$ have $g(\hat{\phi}^i)=x$, so there is a set $\{j_1,\ldots,j_r\}\subset\{i+1,\ldots,i+\alpha\}$ such that $\hat{\phi}^i_{j_p}=\hat{\pi}_{j_p}$, for all $1\le i\le k$ and $1\le p\le r$. If $j_1=i+1$ and $j_r=i+\alpha$, then there is exactly one minimal element in $D(x)$, so it is contractible. So assume $j_1\not=i+1$, then $\hat{\phi}^i_{j_1-1}\not=\hat{\pi}_{j_1-1}$, for all $1\le~i\le~k$, because $\hat{\phi}^i_{j_1-1}$ cannot be larger than $\hat{\pi}_{i}$ if $\hat{\pi}_i<\hat{\pi}_{i+1}$ or $\emptyset$ if $\hat{\pi}_i>\hat{\pi}_{i+1}$. An analogous argument implies $\hat{\phi}^i_{j_r+1}\not=\hat{\pi}_{j_1-1}$ if $j_r\not=i+\alpha$. Therefore, the join $\bigvee_{j=1,\ldots,k}\hat{\phi}^j$ is strictly less than $\hat{\pi}$. So the intersection $\bigcap_{j=1,\ldots,k}W(\lambda,\pi)_{\ge\hat{\phi}^j}$ has a unique minimal element and so is contractible, which implies $D(x)$ is contractible for all $x\in W(\pi_{i+1}^\ell,\pi_{i+1}^\alpha)$. Therefore, by the Quillen Fiber Lemma, $W(\lambda,\pi)$ and $W(\pi_{i+1}^\ell,\pi_{i+1}^\alpha)$ are homotopy equivalent.

\[ex:conSeq\] Consider the interval $[\lambda,\pi]$, where:

  ------------- ----------------------------------------------------------------------- -------------------------------------------
  $\lambda$     $=2\,\,1\,\,5\,\,3\,\,4\,\,8\,\,6\,\,7\,\,10\,\,9 $                     $=21\oplus312\oplus312\oplus21,$
  $\pi$         $=2\,\,1\,\,5\,\,3\,\,4\,\,8\,\,6\,\,7\,\,11\,\,9\,\,10\,\,13\,\,12 $   $=21\oplus312\oplus312\oplus312\oplus21,$
  $\hat{\pi}$   $=(21,1,12,1,12,1,12,21).$                                              
  ------------- ----------------------------------------------------------------------- -------------------------------------------

So we have a sequence of equal components $\pi_2=\pi_3=\pi_4=312$ of length $\alpha=3$ and $\ell=2$.

Given an element $\hat{\eta}\in W(\lambda,\pi)$, which is the decomposition of an embedding $\eta$ of a permutation $\tau$ in $\pi$, we apply the the map $g$ from the proof of Proposition \[prop:conSeq\] in the following way: $$\begin{aligned}
\hat{\eta}&=(0,1,1,1,12,1,12,21)\\
\eta&=0\,\,0\,\,5\,\,0\,\,4\,\,8\,\,6\,\,7\,\,11\,\,9\,\,10\,\,13\,\,12\\
\tau&=\sigma\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\tilde{\tau}=312\oplus312\end{aligned}$$ The letters of $\tilde{\tau}$ in $\eta$ are those embedded in $8\,6\,7\,11\,9\,10$ so we get the embedding $0\,0\,0\,8\,6\,7\,11\,9\,10$, which gives $g(\hat{\eta})=(0,0,1,12,1,12)$.

Applying Proposition \[prop:conSeq\] to $[\lambda,\pi]$ gives: $$\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}=(-1)^{3-2-1}\dbinom{3-1}{2-1}=2.$$

We conjecture that we can generalise this further by removing elements from more than one sequence of equal components:

\[conj:genRepeat\] Consider a decomposable permutation $\pi=\pi_1\oplus\cdots\oplus\pi_n$ which has $t$ sequences of equal components $\pi_{s_i+1}=\ldots=\pi_{s_i+\alpha_i}\not=1$ of respective lengths $\alpha_i$, for $1\le i\le t$. Let $\lambda=\lambda_1\oplus\cdots\oplus\lambda_m$ be the permutation obtained from $\pi$ by, for each $i$, reducing the $i$-th sequence to length $\ell_i$, with $0\le \ell_i\le \alpha_i$. Then: $$\sum_{S\in EZ^{\lambda,\pi}}(-1)^{|S|}=(-1)^{\alpha-\ell-1}\prod_{i=1}^t\dbinom{\alpha_i-1}{\ell_i-1},$$ where $\alpha=\alpha_1+\cdots+\alpha_t$ and $\ell=\ell_1+\cdots+\ell_t$.

Consider the permutation $\pi=2\,1\,4\,3\,7\,5\,6\,10\,8\,9\,13\,11\,12$ which has the decomposition $21\oplus21\oplus312\oplus312\oplus312$ so has 2 sequences of equal components $21,\,21$ and $312,\,312,\,312$ of lengths $\alpha_1=2$ and $\alpha_2=3$. If $\lambda=21\oplus312\oplus312=21534867$, so $\ell_1=1$ and $\ell_2=2$, the sum in equals $-2$, this agrees with the formula in Conjecture \[conj:genRepeat\]: $$(-1)^{5-3-1}\dbinom{2-1}{1-1}\dbinom{3-1}{2-1}=-2.$$

Acknowledgements {#acknowledgements .unnumbered}
================

I would like to thank the anonymous referee for their extremely useful comments which greatly improved the paper.

Bibliography {#bibliography .unnumbered}
============

[18]{} natexlab\#1[\#1]{}url \#1[`#1`]{}urlprefix

Bj[ö]{}rner, A., 1980. Shellable and [C]{}ohen-[M]{}acaulay partially ordered sets. Transactions of the American Mathematical Society 260 (1), 159–183.

Bj[ö]{}rner, A., 1990. The [M]{}[ö]{}bius function of subword order. Institute for Mathematics and its Applications 19, 118.

Bj[ö]{}rner, A., 1993. The [M]{}[ö]{}bius function of factor order. Theoretical Computer Science 117 (1), 91–98.

Bj[ö]{}rner, A., Wachs, M., Welker, V., 2005. Poset fiber theorems. Transactions of the American Mathematical Society 357 (5), 1877–1899.

Burstein, A., Jel[í]{}nek, V., Jel[í]{}nkov[á]{}, E., Steingr[í]{}msson, E., 2011. The [M]{}öbius function of separable and decomposable permutations. Journal of Combinatorial Theory. Series A 118 (8), 2346–2364.

Klee, V., 1963. The [E]{}uler characteristic in combinatorial geometry. American Mathematical Monthly, 119–127.

Kozlov, D., 2008. Combinatorial Algebraic Topology. Algorithms and Computation in Mathematics. Springer.

McNamara, P. R. W., Steingr[í]{}msson, E., 2015. On the topology of the permutation pattern poset. Journal of Combinatorial Theory, Series A 134, 1–35.

Narushima, H., 1974. Principle of inclusion-exclusion on semilattices. Journal of Combinatorial Theory, Series A 17 (2), 196–203.

Rota, G.-C., 1964. On the foundations of combinatorial theory [I]{}. [T]{}heory of [M]{}[ö]{}bius functions. Probability Theory and Related Fields 2 (4), 340–368.

Sagan, B. E., Vatter, V., 2006. The [M]{}öbius function of a composition poset. Journal of Algebraic Combinatorics 24 (2), 117–136.

Sloane, N. J. A., 1991. The [O]{}n-[L]{}ine [E]{}ncyclopedia of [I]{}nteger [S]{}equences. Published electronically at <http://oeis.org>, sequence [A002464](http://oeis.org/A002464).

Smith, J. P., 2014. On the [M]{}öbius function of permutations with one descent. The Electronic Journal of Combinatorics 21, 2.11.

Smith, J. P., 2016. Intervals of permutations with a fixed number of descents are shellable. Discrete Mathematics 339 (1), 118 – 126.

Stanley, R. P., 2012. Enumerative Combinatorics. [V]{}ol. 1, 2nd Edition. Cambridge Studies in Advanced Mathematics. Cambridge University Press.

Steingr[í]{}msson, E., Tenner, B. E., 2010. The [M]{}öbius function of the permutation pattern poset. Journal of Combinatorics 1 (1), 39–52.

Wachs, M. L., 2007. Poset topology: [T]{}ools and applications. In: Geometric Combinatorics. Vol. 13 of IAS/Park City Math. Ser. Amer. Math. Soc., pp. 497–615.

Walker, J. W., 1981. Homotopy type and euler characteristic of partially ordered sets. European Journal of Combinatorics 2 (4), 373–384.

[^1]: The programs used are available at <https://github.com/JasonPSmith/perm> and the data can be provided upon request by emailing the author at jason.p.smith@strath.ac.uk.
