A382570 a(n) is the number of shallow permutations of length n that avoid 231.

1, 1, 2, 5, 14, 41, 121, 355, 1037, 3025, 8824, 25746, 75130, 219246, 639805, 1867066, 5448412, 15899370, 46397015, 135394275, 395103258, 1152977744, 3364582879, 9818418346, 28651794889, 83610752932, 243990229487, 712004497223, 2077748790043, 6063220178075

Offset

0,3

Comments

A shallow permutation is a permutation that satisfies the lower bound of the Diaconis-Graham inequality (i.e., so that the total displacement is equal to the sum of the length and reflection length).

Links

Michael De Vlieger, Table of n, a(n) for n = 0..2151

Kassie Archer, Aaron Geary, and Robert P. Laudone, Pattern-avoiding shallow permutations, arXiV:2412.11999 [math.CO], 2024

Index entries for linear recurrences with constant coefficients, signature (4,-4,2,1,1).

Formula

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

Mathematica

CoefficientList[Series[(1 - 3*x + 2*x^2 - x^3 - x^4 - x^5)/(1 - 4*x + 4*x^2 - 2*x^3 -x^4 - x^5), {x, 0, 29}], x] (* Michael De Vlieger, Apr 01 2025 *)

Crossrefs

Cf. A062869, A301897.

Sequence in context: A244885 A116845 A307466 * A116849 A371427 A123183

Adjacent sequences: A382567 A382568 A382569 * A382571 A382572 A382573

Keyword

nonn,easy

Author

Kassie Archer, Mar 31 2025

Status

approved