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

Author

Kassie Archer, Mar 31 2025

Keywords

• nonn
• easy

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

Crossrefs

Cf. A062869, A301897.

Programs

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 *)

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