It is classical that 321-avoiding permutations are enumerated by the Catalan numbers.

A permutation is *parity-alternating* if it sends even integers to even integers, and odd integers to odd. I am interested in the number of 321-avoiding parity-alternating permutations. (123-avoidance is also of interest).
The four other patterns of length 3 are easy to enumerate.

**Example:**
The sequence for 321-avoiding permutations of size $n=1,2,3,...$ is
$$
1, 1, 1, 2, 3, 6, 11, 22, 44, 89, 185, 382, 808, 1702, 3635, 7779, \dotsc
$$
and this is ~~not in the OEIS at the moment~~ A354208.
For example, $[1, 2, 3, 4]$, and $[3, 4, 1, 2]$ are the two parity-alternating permutations of size 4 which also avoids 321.

These numbers are generated by first computing all 321-avoiding permutations (via a Catalan recursion) and then selecting the parity-alternating ones. We do not have an efficient formula for generating the numbers above.

**Question:** *Can one find some more efficient way of generating the above sequence?*
A generating function, or a recursion?

Note: For odd $n$, there is a bijection between 123 and 321-avoiding, parity-alternating permutations, by taking the reverse

16more comments