The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137555 Number of permutations in S_n avoiding {bar 4}{bar 5}123 (i.e., every occurrence of 123 is contained in an occurrence of a 45123). 0
1, 2, 5, 14, 43, 147, 578, 2702, 15252, 103150, 817928, 7428844, 75807522, 856512850, 10596715538 (list; graph; refs; listen; history; text; internal format)



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)


Table of n, a(n) for n=1..15.

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

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


Sequence in context: A148334 A149882 A137554 * A137556 A137557 A306799

Adjacent sequences:  A137552 A137553 A137554 * A137556 A137557 A137558




Lara Pudwell, Apr 25 2008


a(8)-(15) from Lars Blomberg, Jun 06 2018



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 22 09:50 EDT 2022. Contains 353949 sequences. (Running on oeis4.)