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,5

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.

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.

Example

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.

Crossrefs

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

Sequence in context: A027214 A192652 A132831 * A007477 A274936 A244521

Adjacent sequences: A354205 A354206 A354207 * A354209 A354210 A354211

Keyword

nonn

Author

Per W. Alexandersson, Jun 06 2022

Extensions

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

Status

approved