4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 2, 2017 at 23:37
  • $\begingroup$ 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! $\endgroup$ Jun 3, 2017 at 3:57
  • $\begingroup$ I guess the definition should say that you can to make more than one of such operations? Otherwise the relation isn't transitive. $\endgroup$ Jun 9, 2017 at 18:21

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.