A354208 Number of parity-alternating permutations of [n] avoiding the pattern 321.

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, 468084856, 1042703207, 2325575076, 5193931583, 11609749877, 25986720374, 58203955771

Offset: 0

Author

Per W. Alexandersson, Jun 06 2022

Keywords

• nonn

Comments

A permutation is parity-alternating if it sends odd integers to odd integers, and even integers to even integers. It avoids 321 if there is no subsequence a..b..c with a > b > c. The values are computed by Michael Albert, see MathOverflow link.

Examples

			For n=4, the two permutations are 1234, 3412.
For n=5, we have 12345, 34125, 14523.
For n=6, we have 123456, 341256, 145236, 125634, 561234, 345612.
		

Links

• Peter J. Taylor, Table of n, a(n) for n = 0..50
• Per Alexandersson, Samuel Asefa Fufa, Frether Getachew and Dun Qiu, Pattern-avoidance and Fuss-Catalan numbers, arXiv:2201.08168 [math.CO], 2022. See also J. Int. Seq. (2023) Vol. 26, Art. 23.4.2.
• MathOverflow, 321-avoiding and parity-alternating permutations, Jun 06 2022.
• Nathan Williams, Oberwolfach Problem Session: Enumerative Combinatorics 2022, Univ. Texas Dallas (2023). See example 3.4, where this sequence is misidentified by typographical error.

Crossrefs

Cf. A000108 (321-avoiding permutations), A010551 (parity-alternating permutations).

Extensions

Offset corrected and terms a(30) and beyond from Peter J. Taylor, Jun 10 2022