Computing cardinalities of subsets on Sn with k adjacencies

Abstract

Given a permutation $\pi =({\pi }_1,{\pi }_2,{\pi }_3,\dots ,{\pi }_n)$ over the alphabet $\mathrm{\Sigma }=\{0,1,\dots ,n-1\}$, ${\pi }_i$ and ${\pi }_{i+1}$ are said to form an adjacency if ${\pi }_{i+1}={\pi }_i+1$ where $1\le i\le n-1$. The set of permutations over $\mathrm{\Sigma }$ is a symmetric group denoted by $S_n$. $S_n(k)$ denotes the subset of permutations with exactly $k$ adjacencies. We study four adjacency types and efficiently compute the cardinalities of $S_n(k)$. That is, we compute for all $k$ $|S_n(k)|$ for each type of adjacency in $O(n^2)$ time. We define reduction and show that $S_n(n-k)$ is a multiset consisting exclusively of $\mu \in {\mathbb{Z}}^{+}$ copies of $S_n(0)$ where $\mu$ depends on $n$, $k$ and the type of adjacency. We derive an expression for $\mu$ for all types of adjacency.