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,3

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.

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

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

Crossrefs

Row sums of A205574.

Antidiagonal sums of A292870.

Sequence in context: A137550 A047970 A160701 * A148333 A271270 A201497

Adjacent sequences: A137548 A137549 A137550 * A137552 A137553 A137554

Keyword

nonn

Author

Lara Pudwell, Apr 25 2008

Extensions

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

Status

approved