A335793 Number of hare pop-stack sortable Cayley permutations.

1, 1, 3, 11, 41, 151, 553, 2023, 7401, 27079, 99081, 362535, 1326505, 4853639, 17759305, 64980711, 237762281, 869964359, 3183170953, 11647117735, 42616420393, 155932079367, 570550345417, 2087624932455, 7638550907241, 27949206323143, 102265225902089

Offset

0,3

Comments

Also, the set of Cayley permutations avoiding 231, 312, and 2121.

Links

Abigail Ollson, Table of n, a(n) for n = 0..99

Christian Bean, Paul C. Bell, and Abigail Ollson, The insertion encoding of Cayley permutations, arXiv:2505.08480 [math.CO], 2025.

Giulio Cerbai, Sorting Cayley permutations with pattern-avoiding machines, arXiv:2003.02536 [math.CO], 2020. See p. 16.

Index entries for linear recurrences with constant coefficients, signature (5,-6,4).

Formula

Conjectures from Colin Barker, Jun 24 2020: (Start)

G.f.: (1 - 4*x + 4*x^2 - 2*x^3) / (1 - 5*x + 6*x^2 - 4*x^3).

a(n) = 5*a(n-1) - 6*a(n-2) + 4*a(n-3) for n>3. (End)

The above conjectures are correct. - Abigail Ollson, Feb 12 2026

Crossrefs

Cf. A000670, A226316.

Sequence in context: A086972 A218348 A320827 * A077831 A032952 A079935

Adjacent sequences: A335790 A335791 A335792 * A335794 A335795 A335796

Keyword

nonn,easy

Author

Michael De Vlieger, Jun 23 2020

Extensions

a(7)-a(8) from Giulio Cerbai via Michael De Vlieger, Jun 24 2020

More terms from Abigail Ollson, Feb 12 2026

Status

approved