A381859 a(n) is the number of permutations that avoid 312 and 4321 and whose square avoids 321.

1, 1, 2, 5, 11, 23, 50, 109, 236, 511, 1108, 2402, 5206, 11284, 24459, 53016, 114914, 249081, 539894, 1170243, 2536551, 5498082, 11917326, 25831309, 55990457, 121361689, 263056605, 570186341, 1235903062, 2678872272, 5806569196, 12585984849, 27280655629

Offset: 0

Author

Kassie Archer, Mar 10 2025

Keywords

• nonn
• easy

Examples

			The 11 permutations of length 4 are: 1234, 1243, 1324, 1342, 1432, 2134, 2143, 2314, 2341, 3214, 3421.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..2977
• Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See p. 8.
• Index entries for linear recurrences with constant coefficients, signature (2,0,1,0,-1).

Crossrefs

Cf. A001590 (with square avoiding 312), A001590 (with square avoiding 132).

Programs

Mathematica

CoefficientList[Series[(1 - x)/(1 - 2*x - x^3 + x^5), {x, 0, 32}], x] (* Michael De Vlieger, May 13 2025 *)

Formula

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

a(n) = a(n-3) + a(n-4) + Sum_{j=0..n-1} a(j).