A337495 Maximum number of preimages that a permutation of length n can have under the consecutive-123-avoiding stack-sorting map.

1, 1, 1, 2, 3, 4, 7, 11, 16, 26, 42

Offset

0,4

Links

Table of n, a(n) for n=0..10.

Colin Defant and Kai Zheng, Stack-sorting with consecutive-pattern-avoiding stacks, arXiv:2008.12297 [math.CO], 2020.

Example

The consecutive-123-avoiding stack-sorting map acts on permutations of length 3 by reversing every permutation except 321, which gets sent to 213. The permutation 213 has 2 preimages under this map (namely, 312 and 321), and every other permutation of length 3 has at most one preimage. Hence, a(3)=2.

Crossrefs

Sequence in context: A222022 A025048 A017987 * A222023 A221997 A221998

Adjacent sequences: A337492 A337493 A337494 * A337496 A337497 A337498

Keyword

nonn,more

Author

Colin Defant, Aug 29 2020

Status

approved