|
%I #24 Jul 11 2023 02:58:01
%S 1,2,5,14,43,146,561,2518,13563,88354,686137,6191526,63330147,
%T 720314930,8985750097,121722964822,1777038601387,27792425428418,
%U 463361639828329,8200984957695750,153532638260056115,3030783297332577234
%N 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).
%C From _Lara Pudwell_, Oct 23 2008: (Start)
%C 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.
%C 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.
%C 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.
%C 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)
%H Vaclav Kotesovec, <a href="/A137553/b137553.txt">Table of n, a(n) for n = 1..300</a>
%H Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/papers/pudwell_thesis.pdf">Enumeration Schemes for Pattern-Avoiding Words and Permutations</a>, Ph. D. Dissertation, Math. Dept., Rutgers University, May 2008.
%H Lara Pudwell, <a href="https://doi.org/10.37236/301">Enumeration schemes for permutations avoiding barred patterns</a>, El. J. Combinat. 17 (1) (2010) R29.
%F 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
%F a(n) ~ (n-2)!. - _Vaclav Kotesovec_, Mar 15 2014
%F 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
%t CoefficientList[Assuming[Element[x, Reals], Series[1/(1 - x - ExpIntegralEi[1/x]/E^(1/x)), {x, 0, 20}]], x] (* _Vaclav Kotesovec_, Mar 15 2014 *)
%t 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_ *)
%o (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
%K nonn
%O 1,2
%A _Lara Pudwell_, Apr 25 2008
|
