A137551 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).

1, 1, 2, 5, 14, 43, 144, 525, 2084, 9005, 42288, 215111, 1179738, 6937765, 43504598, 289356385, 2031636826, 14995775647, 115943399636, 936138957225, 7872233481696, 68788474572625, 623323010473012, 5846701373312019, 56677763478164422, 567011396405398185

Offset: 0

Author

Lara Pudwell, Apr 25 2008

Keywords

• nonn

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)

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..570
• David Callan, The number of bar{2}413bar{5}-avoiding permutations, arXiv:1110.6884 [math.CO], 2011.
• 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.

Crossrefs

Row sums of A205574.

Antidiagonal sums of A292870.

Programs

Maple

read("bVATTER14") ; # http://faculty.valpo.edu/lpudwell/maple/bVATTER14
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
# Another Maple program:
with(combinat):
invtr:= proc(p) local b; b:= proc(n) option remember;
           `if`(n<1, 1, add(b(n-i) *p(i-1), i=1..n+1)) end
        end:
a:= n-> invtr(n-> bell(n))(n-1):
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 28 2012

Mathematica

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

Formula

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

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

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

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

Extensions

a(0)=1 prepended by Alois P. Heinz, Jul 10 2023