We say two permutations $\pi_1$ and $\pi_2$ in the symmetric group $\mathfrak{S}_n$ are $k$-equivalent, denoted $\pi_1 \sim_k \pi_2$, if one can be determined from the other after a finite number of switching of neighborly terms that differ by exactly $k$.

The above concept is motivated by this paper of R. P. Stanley who studied the case $k=1$. The question below attempts at an extension on enumeration of classes:

QUESTION 1. Let $f_2(n)$ be the number of equivalent classes with respect to $\sim_2$ on $\mathfrak{S}_n$. Then, does the following hold true? $$ f_2(n)=\sum_{j=0}^{\lfloor\frac{n}2\rfloor}(-1)^j(n-j)!\sum_{\ell=0}^{\lfloor\frac{j}2\rfloor}\binom{n-j-2\ell-1}{j-2\ell}.$$

The first few values of $f_2(n)$, for $n\geq0$, are: $$1, 1, 2, 4, 14, 60, 336, 2232, 17304, 152280, 1498320, \dots$$ but not yet available on OEIS.

  • 1
    $\begingroup$ Does the "finite" in "finite number of switching[s]" affect anything? After all, there are only finitely many permutations, so any infinite sequence of switchings would have to stutter at some point. $\endgroup$ – LSpice Mar 7 '19 at 16:20
  • $\begingroup$ You're right, it doesn't affect. $\endgroup$ – T. Amdeberhan Mar 7 '19 at 16:38

This answer will come in two parts, first we will transform the problem into a form that is ammenable to the methods of section 2 of Stanley's paper, then we will show that the above summation is equivalent to that answer.

If we renumber the elements of the permutation so that $1,3,5,\dots$ become $1,2,3,\dots$, and $2,4,6,\dots$ become $\lceil \frac{n}{2} \rceil + 1,\lceil \frac{n}{2} \rceil + 2,\lceil \frac{n}{2} \rceil + 3,\ldots$, then the definiton of $\sim_2$ becomes -- two permutations are equivalent if they can be obtained from each other by interchanging adjacent terms that differ by one except we cannot interchange $\lceil \frac{n}{2} \rceil$ and $\lceil \frac{n}{2} \rceil + 1$.

Parallelling the paper we can define a permutation $\omega=a_1a_2\cdots a_n\in \mathfrak{S}_n$ to be salient if we never have $a_i=a_{i+1}+1$ $(1\le i \le n-1$ unless $a_{i+1}=\lceil\frac{n}{2}\rceil$ and we never have $a_i=a_{i+1}+2=a_{i+2}+1$ $(i\le i \le n-2)$ unless $a_{i+1}$ or $a_{i+2}$ equals $\lceil\frac{n}{2}\rceil$.

Each equivalence class of permutations contains exactly one salient permutation. The proof of this exactly parallels the proof of Lemma 2.1 in Stanley's paper. The lexicographically smallest permutation in each equivalence class is salient, and each salient permutation is lexicographically smallest in its equivalence class.

The arguments of Theorem 2.2 hold as well, the only difference is that none of the factors can cross the $\lceil\frac{n}{2}\rceil$ -- $\lceil\frac{n}{2}\rceil+1$ boundary, and we find that

$$f_2(n)=\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}{(-1)}^j(n-j)!\ p(n,j)$$

where $p(n,j)$ is the number of ways of placing $j$ non overlapping $2\times 1$ dominos and $n-2j$ $1\times 1$ squares on a strip of length $n$ so that no domino covers both $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$.

Since we know that there are $\binom{n-k}{k}$ ways of placing $k$ dominos on a strip of length $n$, we can place the dominos in the left and right halves independently giving

$$f_2(n)=\sum_{i=0}^{\lfloor\frac{n+1}{4}\rfloor}{(-1)}^i\binom{\lceil\frac{n}{2}\rceil-i}{i} \sum_{k=0}^{\lfloor\frac{n}{4}\rfloor}{(-1)}^k(n-i-k)!\binom{\lfloor\frac{n}{2}\rfloor-k}{k}$$

Slight modification of the above argument gives a plausible way of computing the number of equivalence classes for $\sim_k$ for small $k$.

Now to show that

$$f_2(n)=\sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}{(-1)}^j(n-j)! \sum_{\ell=0}^{\lfloor \frac{j}{2}\rfloor} \binom{n-j-2\ell-1}{j-2\ell}.$$

we show that

$$p(n,j)=\sum_{\ell=0}^{\lfloor \frac{j}{2}\rfloor} \binom{n-j-2\ell-1}{j-2\ell}.$$

Simple counting shows that the formula holds for $j$ equals zero and one.

Now we show that $$p(n,j) = \binom{n-j-1}{j} + p(n-4,j-2)$$ for $j\ge 2$ which will give us the desired result by induction.

There are $\binom{n-j-1}{j}$ ways of placing $j$ dominos on a strip of length $n$ so that at least one of $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$ is not covered by a domino. We can place $j$ non overlapping dominos on a strip of length $n-1$ in $\binom{n-j-1}{j}$ ways, and for each of these if a domino covers both $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$ we insert a single tile at $\lceil\frac{n}{2}\rceil$, otherwise we insert a tile at $\lceil\frac{n}{2}\rceil + 1$.

Conversely, if we have a placement of dominos on a strip of length $n$ such that $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$ are not both covered by dominos. If $\lceil\frac{n}{2}\rceil+1$ is not covered by a domino we shift everything greater than $\lceil\frac{n}{2}\rceil+1$ left one place. Otherwise $\lceil\frac{n}{2}\rceil$ is not covered by a domino and we shift everything greater than $\lceil\frac{n}{2}\rceil$ left one place.

Now there are $p(n-4,j-2)$ ways of placing $j$ non overlapping dominos on a strip of length $n$ such that $\lceil\frac{n}{2}\rceil$ and $\lceil\frac{n}{2}\rceil+1$ are each covered by a domino. This gives us the recurrence

$$p(n,j) = \binom{n-j-1}{j}+p(n-4,j-2)$$

for $j\ge2$ which combined with the base cases shows that

$$p(n,j)=\sum_{\ell=0}^{\lfloor \frac{k}{2}\rfloor} \binom{n-j-2\ell-1}{j-2\ell}.$$

I'd prefer to avoid the induction and give a direct argument, but cannot figure out how.


The generalization of the argument in the first half to count equivalence classes of $\sim_k$ gives us

$$f_k(n) = \sum_{j=0}^{\lfloor\frac{n}{2}\rfloor}{(-1)}^n(n-j)!\sum_{\substack{a_1+a_2+\cdots+a_k=j\\0\le a_i\le\lfloor\frac{n+i-1}{2k}\rfloor\text{ for all $1\le i\le k$}}} \prod_{i=1}^k\binom{\lfloor\frac{n+i-1}{k}\rfloor-a_i}{a_i}.$$

This is much less elegant than the final result for $n=2$, but it is amenable to dynamic programming and can efficiently compute $f_k(n)$ easily for any plausible values of $n$ and $k$.

| cite | improve this answer | |
  • $\begingroup$ Nice. Up-voted. $\endgroup$ – T. Amdeberhan Dec 18 '16 at 4:49
  • $\begingroup$ Thanks, I'm curious as to how you came up with the formula. $\endgroup$ – Deinst Dec 18 '16 at 5:13
  • $\begingroup$ I studied the proof for $k=1$ and experimented a bit, but was lazy on the details of generalizing the proof. BTW, just as you suspected, I also extended the notion to $k$-salient permutations which I believe exist uniquely in the classes, for any $k$. $\endgroup$ – T. Amdeberhan Dec 18 '16 at 5:24

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.