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](http://www-math.mit.edu/~rstan/papers/multfree.pdf).



Counting block-equivalent permutations
We can prove this with a slight generalisation (and uglification) of Stanley's
argument.


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}$$


