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 