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.
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