9
$\begingroup$

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

Improve this question
$\endgroup$
21
  • 2
    $\begingroup$ @PerAlexandersson Here are the values through n=29 (more or less the limit of my patience at this point) using a simple DFS (there are ways to refine it which would dig out more terms but I'm not sure it's worth it). Incidentally, it appears the exponential growth rate is about 2 which would make sense from the heuristic that each element has a 1/2 chance of being the right parity, so we expect about 4^n/2^n. 1, 1, 1, 1, 2, 3, 6, 11, 22, 44, 89, 185, 382, 808, 1702, 3635, 7779, 16736, 36229, 78466, 171238, 373203, 819186, 1795611, 3958662, 8721086, 19294525, 42691298, 94733886, 210379132 $\endgroup$
    – Michael Albert
    Jun 5, 2022 at 23:07
  • 2
    $\begingroup$ Simple DFS in Python $\endgroup$
    – Peter Taylor
    Jun 5, 2022 at 23:31
  • 3
    $\begingroup$ I reworked to use bitmasks instead of lists for efficiency, and can extend @MichaelAlbert's list by six values: 468084856, 1042703207, 2325575076, 5193931583, 11609749877, 25986720374. The ratio between successive terms appears to be growing without bound, but if you consider the sequence r(n) = (nth Catalan number)/(nth term of the sequence of interest), the term ratio r(n+1)/r(n) appears to be converging on a value slightly above 1.71. (Another two terms would help to clarify, but I estimate a calculation time of about 24 hours). $\endgroup$
    – Peter Taylor
    Jun 6, 2022 at 19:53
  • 1
    $\begingroup$ @MichaelAlbert Ah, right, it is for ODD n there is that bijection, but for EVEN n, the numbers are not the same. $\endgroup$
    – Per Alexandersson
    Jun 7, 2022 at 5:41
  • 1
    $\begingroup$ @PerAlexandersson So I was right - I was missing something terribly obvious - a typo :) $\endgroup$
    – Michael Albert
    Jun 7, 2022 at 5:55

0

Reset to default

You must log in to answer this question.