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$
  • $\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$ – Richard Stanley Jul 26 '15 at 15:53
  • $\begingroup$ @RichardStanley I corrected question. Hope it is clearer now. $\endgroup$ – Brout Jul 26 '15 at 16:05
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$
  • $\begingroup$ Is there a formal proof? $\endgroup$ – Brout Jul 27 '15 at 0:46
  • $\begingroup$ I see ir works, but I do not understand how. $\endgroup$ – Brout Jul 27 '15 at 1:04
  • $\begingroup$ @Turbo I have added some more details to my argument. $\endgroup$ – Richard Stanley Jul 27 '15 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$ – Brout Jul 27 '15 at 1:21

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.