# Counting block-equivalent permutations

Consider the group $\mathfrak{S}_n$ of permutations on the letters $\{1,2,\dots,n\}$.

We say two permutations are b-equivalent, $\pi_1\,\pmb{\sim^b}\,\pi_2$, if one can be determined from the other by reversing a block of $b$ consecutive integers. For example, $617\pmb{5432}\,\pmb{\sim^4}\,617\pmb{2345}$.

Question. Is this true? The number $h_b(n)$ of $(b+1)$-equivalent classes is given by $$h_b(n)=\sum_{j=0}^{\lfloor\frac{n}{b+1}\rfloor}(-1)^j(n-bj)!\binom{n-bj}j.$$

The special case $b=1$ recovers Theorem 2.2 of this paper.

• Could this be a particular case of Theorem 2.18 in William Kuszmaul, New Results on Doubly Adjacent Pattern-Replacement Equivalences, arXiv:1402.3881v2? This is not a rhetorical question -- I haven't read that paper -- but it sounds at least seriously relevant to the question. Jun 2, 2017 at 23:37
• This is rather interesting, thanks. The formula in my question is the case $k=1$ of the theorem you mentioned. However, the constructions are very different. One needs to see (find) some bijective link! Jun 3, 2017 at 3:57
• I guess the definition should say that you can to make more than one of such operations? Otherwise the relation isn't transitive. Jun 9, 2017 at 18:21

Let a permutation be $b$-salient if we never have either $a_i=a_{i+1}+1=\cdots =a_{i+b}+b$ or $a_i=a_{i+1}+b+1=a_{i+2}+b=\cdots =a_{i+b+1}+1$. The proof of Stanley's lemma 2.1 holds with minor modification to show that the lexicographically first element in each $b$-equivalence class is $b$-salient, and is the only $b$-salient permutation in its equivalence class.
So we need to count the number of $b$-salient permutations. We will do this by inclusion exclusion, much like Stanley's Theorem 2.2. Let $A_i$, $1\le i\le n-b$ be the set of permutations $v\in\mathfrak{S}_n$ that contain the factor $i+b,i_b-1,\dots,i$. Let $B_i$, $1\le i\le n-b-1$ be the set of permutations that contain the factor $i+b+1, i, i+1,\dots, i+b$. Let $C_i$ be some indexing of the $A_i$'s and $B_i$'s. By inclusion-exclusion we have $$h_b(n)=\sum_{S\in [2n-2b-1]}{(-1)}^{\#S} \#\bigcap_{i\in S}C_i,$$ where the empty intersection is all of $\mathfrak{S}_n$. We see that any intersection of the $C_i$'s consist of disjoint factors of the forms $j,j-1,\dots,i+1,i$ and $j,j-1,\dots,i+b+1,i,i+1,\dots,i+b$. Permutations containing the factors $j,j-1,\dots,i+1,i$ are those in $A_{k_1=j-b}\cap A_{k_2}\cap\dots\cap A_{k_l=i}$ where the $k_i$ are a decreasing sequence of numbers such that $0<k_i-k_{i+1}<b$. Similarly, permuations containing the factors $j,j-1,\dots,i+b+1,i,i+1,\dots,i+b$ are those in $a_{k_1=j-b}\cap a_{k_2}\cap\cdots\cap a_{k_l=i+b+1}\cap B_i$ where $0<k_i<b$. If we convert the first occurence of $B_i$ in our intersection with $A_i\cap A_{i+1}$, the size of the sets of permutations are the same, but the cardinality of the intersecting sets have opposite cardinality, so the two sets cancel in our summation.
Now call a subset of [n-b] good if whenever it contains both $i$ and $i+1$ then it also contains some element between $i-b$ and $i-1$ or $i+2$ and $i+b$. After the above pairing operation we have reduced our sum to $$h_b(n)=\sum_{\substack{S\in [n-b]\\S \text{ is good}}}{(-1)}^{\#S} \#\bigcap_{i\in S}A_i$$ Now if we look at the nonoverlapping factors, the factor $i+b+1, i+b,\dots,i$ corresponding to $A_{i}\cap A_{i+1}$ does not occur because the isolated $i,i+1$ is not good, so these factors contribute nothing to the sum. The nonoverlapping factor $i+b+2, i+b+1,\dots,i$ corresponds to $A_{i+2}\cap A_{i+1}\cap A_{i}$ or $A_{i+2}\cap A_{i}$ both of which are good but have opposite parity so contribute nothing to the sum. Similarly for nonoverlapping factors of the form $i+b+k, i+b+k-1,\dots,i$ for $2\le k \le b$ corresponds to $2^{k-1}$ intersections containing $A_{i+k}$ and $A_{i}$ and any combination of $A_j$ for $i<j<i+k$. For $k>b$ the corresponding intersection must contain $A_{i+k}$ and some $A_{i+j}$ for $k-b<j<k$ where if we remove $A_{i+k}$ from our intersection we get a previously considered factor which contributed nothing to the sum. As adding $A_{i+k}$ just changes the parity of the intersection these factors also contribute nothing to the sum.
So we are left with nonoverlapping factors of size exactly $b+1$, and the problem reduces to tiling a strip of length $n$ with tiles of length $b+1$ and 1. There are $\binom{n-bj}{j}$ ways of doing this with $j$ tiles of length $b+1$, and there are $(n-bj)!$ permutations corresponding to the above factors giving us $$h_b(n)=\sum_{j=0}^{\lfloor \frac{n}{b+1} \rfloor}{(-1)}^{j}(n-bj)!\binom{n-bj}{j}$$