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 