A137553 Number of permutations in S_n avoiding {bar 5}{bar 4}231 (i.e., every occurrence of 231 is contained in an occurrence of a 54231).

1, 2, 5, 14, 43, 146, 561, 2518, 13563, 88354, 686137, 6191526, 63330147, 720314930, 8985750097, 121722964822, 1777038601387, 27792425428418, 463361639828329, 8200984957695750, 153532638260056115, 3030783297332577234

Offset

1,2

Comments

From Lara Pudwell, Oct 23 2008: (Start)

A permutation p avoids a pattern q if it has no subsequence that is order-isomorphic to q. For example, p avoids the pattern 132 if it has no subsequence abc with a < c < b.

Barred pattern avoidance considers permutations that avoid a pattern except in a special case. Given a barred pattern q, we may form two patterns, q1 = the sequence of unbarred letters of q and q2 = the sequence of all letters of q.

A permutation p avoids barred pattern q if every instance of q1 in p is embedded in a copy of q2 in p. In other words, p avoids q1, except in the special case that a copy of q1 is a subsequence of a copy of q2.

For example, if q = 5{bar 1}32{bar 4}, then q1 = 532 and q2 = 51324. p avoids q if every for decreasing subsequence acd of length 3 in p, one can find letters b and e so that the subsequence abcde of p has b < d < c < e < a. (End)

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..300

Lara Pudwell, Enumeration Schemes for Pattern-Avoiding Words and Permutations, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.

Lara Pudwell, Enumeration schemes for permutations avoiding barred patterns, El. J. Combinat. 17 (1) (2010) R29.

Formula

G.f. A(x) (for offset 0) satisfies: A(x) = (1-x)^2*A(x)^2 - x^2*A'(x). - Paul D. Hanna, Aug 02 2008

a(n) ~ (n-2)!. - Vaclav Kotesovec, Mar 15 2014

G.f.: (1 + x/((1-x)*S(0) -x))/(1-x), where S(k)= 1 - (k+1)*x/(1 - (k+1)*x/S(k+1)); (continued fraction). - Sergei N. Gladkovskii, Feb 05 2015

Mathematica

CoefficientList[Assuming[Element[x, Reals], Series[1/(1 - x - ExpIntegralEi[1/x]/E^(1/x)), {x, 0, 20}]], x] (* Vaclav Kotesovec, Mar 15 2014 *)
max = 20; Clear[g]; g[max + 2] = 1; g[k_] := g[k] = 1 - (k+1)*x/(1 - (k+1)*x/g[k+1]); gf = (1 + x/((1-x)*g[0] -x))/(1-x); CoefficientList[Series[gf, {x, 0, max}], x] (* Vaclav Kotesovec, Feb 06 2015, after Sergei N. Gladkovskii *)

Prog

(PARI) {a(n)=local(A=1+x+x*O(x^n)); for(i=1, n, A=(1+x^2*deriv(A)/A)/(1-x)^2); polcoeff(A, n)} \\ Paul D. Hanna, Aug 02 2008

Crossrefs

Sequence in context: A201497 A122993 A137552 * A149881 A148334 A149882

Adjacent sequences: A137550 A137551 A137552 * A137554 A137555 A137556

Keyword

nonn

Author

Lara Pudwell, Apr 25 2008

Status

approved