A382574 a(n) is the number of shallow permutations of length n that avoid 123.

1, 1, 2, 5, 13, 35, 90, 225, 525, 1181, 2526, 5289, 10729, 21583, 42566, 83909, 163225, 318713, 616122, 1198029, 2309829, 4483643, 8635314, 16750761, 32247973, 62538517, 120378518, 233428337, 449294497, 871206887, 1676835486, 3251439501, 6258092337, 12134600945

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..3494

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

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

Formula

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

Mathematica

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

Crossrefs

Cf. A062869, A301897.

Sequence in context: A331755 A137674 A048781 * A291242 A097919 A160438

Adjacent sequences: A382571 A382572 A382573 * A382575 A382576 A382577

Keyword

nonn,easy

Author

Kassie Archer, Mar 31 2025

Status

approved