A289603 a(n) is the number of permutations of length n that avoid the pattern 321 and the mesh pattern (12, 273).

1, 1, 1, 1, 6, 22, 91, 349, 1277, 4570, 16235, 57698, 205883, 738704, 2666127, 9678317, 35324733, 129579058, 477507403, 1767000790, 6563595843, 24465218120, 91480466127, 343055418946, 1289895758275, 4861929623752, 18367319517191, 69533483806564, 263747817532007

Offset

0,5

Links

Table of n, a(n) for n=0..28.

Christian Sievers, RFE Dec 2025: Mesh patterns avoiding 321, SeqFan thread.

Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

Formula

From Thomas Scheuerle, Dec 18 2025: (Start)

G.f.: -(-4*x^9 + 14*x^8 - 26*x^7 + 18*x^6 - 6*x^5 - 4*x^4 + 9*x^3 - 9*x^2 + sqrt(1 - 4*x)*(2*x^4 - 7*x^3 + 9*x^2 - 5*x + 1) + 5*x - 1)/(2*(x - 1)^3*x*(2*x - 1)).

a(n) = C(n) - 2^(n-1) - (n-3)^2, for n > 4, where C(n) is the Catalan number A000108.

a(n) = 2*A289604(n) - A289605(n), for n > 4. (End)

Prog

(PARI) listA(max_n) = my(x='x+O(x^max_n)); Vec(-(-4*x^9+14*x^8-26*x^7+18*x^6-6*x^5-4*x^4+9*x^3-9*x^2+sqrt(1-4*x)*(2*x^4-7*x^3+9*x^2-5*x+1)+5*x-1)/(2*(x-1)^3*x*(2*x-1))) \\ Thomas Scheuerle, Dec 18 2025

Crossrefs

Cf. A000108.

Related to mesh patterns: A280891, A289446-A289453, A289587-A289616, A289652-A289654.

Sequence in context: A046365 A266184 A255465 * A349834 A379436 A240049

Adjacent sequences: A289600 A289601 A289602 * A289604 A289605 A289606

Keyword

nonn

Author

N. J. A. Sloane, Jul 08 2017

Extensions

More terms, name and offset changed by Thomas Scheuerle, Dec 18 2025

Status

approved