0
$\begingroup$

Given integers $1$ through $n$, let $S$ be set of ordering of integers that respect even alternating or reverse alternating permutations (https://en.wikipedia.org/wiki/Alternating_permutation) up to length $2n$ ($2,4\dots,n$ if $n$ is even, $2,4\dots,n-1$ if $n$ is odd), $\overline{S}$ be set of orderings that violate alternating and reverse alternating permutations up to length $2n$ .

$$3<4>2<5>1<6>3$$ $$4>2<5>1<6>3<4$$ $$2<3>1<4>2$$ $$4<5>3<6>3$$ are examples of alternating and reverse alternating permutations respectively of length up to $6$ and are in $S$.

$$3>2>1<6>5>4>3$$ $$4>2>1<5<6>3<4$$ $$4>2>1<3<4$$ $$6>4>3<5<6$$ are not alternating or reverse alternating permutations and are in $\overline{S}$.

$|S\cup\overline{S}|=n!$.

How many permutation maps $\sigma_1$ through $\sigma_K$ does one need so that for every $s\in S$ there is a $\sigma_i$ where $i\in\{1,\dots,K\}$ such that $\sigma_i(s)\in\overline{S}$?

Is $K>1$?

If $n=6$, $123456\rightarrow432165$, $123456\rightarrow456123$ both individually seem to convert every $s\in S$ to some element in $\overline S$.

Update after Stanley's answer Answer provided below suggests $2$ permutations needed for every alternating and reverse alternating permutations cycle of given even length.

However in example with $n=6$ above, every even length alternating and reverse alternating permutations cycle of length at most $6$ cycles is covered ($4$ also is covered) with just $1$ permutation.

Stanley's answer provides a solution that needs at least $3$ permutations when $n=6$ ($\sigma_1$ is common for every even length cycle) or $n/2$ permutations asymptotically.

Do we need $K>1$ for this question or at least can $K\ll(\log n)^{1/a}$ with some fixed $a>1$ hold?

$\endgroup$
2
  • $\begingroup$ If I understand your question correctly, then we can take $K=1$ for $n>1$ . Let $\sigma_1$ be any permutation satisfying $\sigma_1(1)=n$. This works since in an alternating permutation as defined by your link, 1 occurs in an odd position and $n$ in an even position. $\endgroup$ Jul 26, 2015 at 15:53
  • $\begingroup$ @RichardStanley I corrected question. Hope it is clearer now. $\endgroup$
    – Turbo
    Jul 26, 2015 at 16:05

1 Answer 1

3
$\begingroup$

We can take $K=2$ for $n\geq 3$. Let $\sigma_1$ satisfy $\sigma_1(1)=1$ and $\sigma_1(2)=n$. Now any permutation in $S$ either has the form $21\cdots$ or $\cdots 12$, or else $1$ and $2$ are in positions with the same parity. But for any permutation in $S$, $1$ and $n$ are in positions with different parity. It follows that $\sigma_1(s)\in \bar{S}$ for all $s\in S$ except for permutations in $S$ of the form $21\cdots$ or $\cdots 12$. Let $\sigma_2(1)=2$ and $\sigma_2(2)=1$. Then for any permutation $s\in S$ of the form $21\cdots$ or $\cdots 12$ we have $\sigma_2(s)\in\bar{S}$, since a permutation in $S$ (for $n\geq 3$) cannot have the form $12\cdots$ or $\cdots 21$.

$\endgroup$
4
  • $\begingroup$ Is there a formal proof? $\endgroup$
    – Turbo
    Jul 27, 2015 at 0:46
  • $\begingroup$ I see ir works, but I do not understand how. $\endgroup$
    – Turbo
    Jul 27, 2015 at 1:04
  • $\begingroup$ @Turbo I have added some more details to my argument. $\endgroup$ Jul 27, 2015 at 1:21
  • $\begingroup$ Thank you for update. I think an even more efficient solution exists that covers every even alternating and reverse alternating permutation upto length $n$ (perhaps with $K=1$ even for my stronger question). Please look at my stronger question that asks to cover every even alternating and reverse alternating permutations. My example at $n=6$ also covers such $4$-cycles (not just $6$ cycles). $\endgroup$
    – Turbo
    Jul 27, 2015 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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