# A question on permutations

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?

• 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. – Richard Stanley Jul 26 '15 at 15:53
• @RichardStanley I corrected question. Hope it is clearer now. – Brout Jul 26 '15 at 16:05

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$.
• 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). – Brout Jul 27 '15 at 1:21