A289613 - OEIS

A289613

a(n) is the number of permutations of length n that avoid the pattern 321 and the mesh pattern (12, 307) or the same sequence for the mesh pattern (12, 409).

1, 1, 1, 1, 8, 31, 116, 407, 1401, 4825, 16750, 58730, 207945, 742821, 2674348, 9694739, 35357549, 129644653, 477638546, 1767263018, 6564120229, 24466266809, 91482563408, 343059613396, 1289904147047, 4861946401151, 18367353071826, 69533550915652, 263747951749981

(list; graph; refs; listen; history; text; internal format)

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 19 2025: (Start)

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

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

a(n) = A289616(n) - (n-2)*(n-1)/2.

a(n) = A289451(n) - 1, for n > 4. (End)

PROG

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

CROSSREFS

Cf. A000108.

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

Sequence in context: A213764 A335606 A320416 * A055845 A034556 A121097

Adjacent sequences: A289610 A289611 A289612 * A289614 A289615 A289616

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Jul 09 2017

EXTENSIONS

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

STATUS

approved