A137551 - OEIS

%I #61 Jul 10 2023 10:30:35

%S 1,1,2,5,14,43,144,525,2084,9005,42288,215111,1179738,6937765,

%T 43504598,289356385,2031636826,14995775647,115943399636,936138957225,

%U 7872233481696,68788474572625,623323010473012,5846701373312019,56677763478164422,567011396405398185

%N Number of permutations in S_n avoiding {bar 2}413{bar 5} (i.e., every occurrence of 413 is contained in an occurrence of a 24135).

%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)

%C Equals the INVERT transform of the Bell sequence (A000110 with offset 0) [Callan preprint]. - _R. J. Mathar_, Nov 29 2011

%H Alois P. Heinz, <a href="/A137551/b137551.txt">Table of n, a(n) for n = 0..570</a>

%H David Callan, <a href="http://arxiv.org/abs/1110.6884">The number of bar{2}413bar{5}-avoiding permutations</a>, arXiv:1110.6884 [math.CO], 2011.

%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.: ((x^2-4)/(U(0)*(x+1)-x^3+4*x)-1)/(1+x) where U(k)= k*(2*k+3)*x^2 + x - 2 - (2 - x + 2*k*x)*(2 + 3*x + 2*k*x)*(k+1)*x^2/U(k+1); (continued fraction, 1-step). - _Sergei N. Gladkovskii_, Sep 28 2012

%F G.f.: 1/(G(0) - x ) where G(k) =  1 - x/(1 - x*(2*k+1)/(1 - x/(1 - x*(2*k+2)/G(k+1) ))); (continued fraction). - _Sergei N. Gladkovskii_, Dec 14 2012

%F G.f.: 1/( G(0) - x ) where G(k) = 1 - x/(1 - x*(k+1)/G(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Feb 02 2013

%F G.f.: 1/( Q(0) -x ) where Q(k)= 1 - (k+1)*x - (k+1)*x^2/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 03 2013

%p read("bVATTER14") ; # http://faculty.valpo.edu/lpudwell/maple/bVATTER14

%p for n from 1 do f([[2,1],[4,0],[1,0],[3,0],[5,1]], {op(permute(n))} ) ; nops(%) ; print(%) ; od: # _R. J. Mathar_, May 29 2009

%p # Another Maple program:

%p with(combinat):

%p invtr:= proc(p) local b; b:= proc(n) option remember;

%p            `if`(n<1, 1, add(b(n-i) *p(i-1), i=1..n+1)) end

%p         end:

%p a:= n-> invtr(n-> bell(n))(n-1):

%p seq(a(n), n=0..30);  # _Alois P. Heinz_, Jun 28 2012

%t invtr[p_] := Module[{b}, b[n_] := b[n] = If[n<1, 1, Sum[b[n-i]*p[i-1], {i, 1, n+1}]]; b]; a[n_] := invtr[BellB][n-1]; Table[a[n], {n, 1, 30}] (* _Jean-François Alcover_, Jan 31 2016, after _Alois P. Heinz_ *)

%Y Row sums of A205574.

%Y Antidiagonal sums of A292870.

%K nonn

%O 0,3

%A _Lara Pudwell_, Apr 25 2008

%E a(0)=1 prepended by _Alois P. Heinz_, Jul 10 2023