login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137546 Number of permutations in S_n avoiding 5234{bar 1} (i.e., every occurrence of 5234 is contained in an occurrence of a 52341). 13
1, 2, 6, 23, 104, 535, 3082, 19763, 140885, 1117101, 9853890, 96543043, 1046549545, 12480046880, 162595262990 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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)

LINKS

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.

EXAMPLE

a(5) = 104: There are 16 permutations that have a 5234 *pattern* that is not followed by a 1. This is different from looking for the string 5234 followed by 1.

A 5234 pattern is a string of 4 numbers abcd where b<c<d<a (i.e. the string has the same relative order as the numbers 5234.)

The 16 permutations that have a 5234 pattern not followed by an even smaller number are:

{[1, 5, 2, 3, 4], [2, 5, 1, 3, 4], [3, 5, 1, 2, 4], [4, 1, 2, 3, 5], [4, 1, 2, 5, 3], [4, 1, 5, 2, 3], [4, 5, 1, 2, 3], [5, 1, 2, 3, 4], [5, 1, 2, 4, 3], [5, 1, 3, 2, 4], [5, 1, 3, 4, 2], [5, 1, 4, 2, 3], [5, 2, 1, 3, 4], [5, 2, 3, 1, 4], [5, 3, 1, 2, 4], [5, 4, 1, 2, 3]}

For example, in 25134, 5134 forms a 5234 pattern that is not followed by something even smaller.

CROSSREFS

Cf. A137536-A137548, A117107.

Sequence in context: A137543 A137544 A137545 * A137547 A137548 A080108

Adjacent sequences:  A137543 A137544 A137545 * A137547 A137548 A137549

KEYWORD

nonn,more

AUTHOR

Lara Pudwell, Apr 25 2008

EXTENSIONS

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 14 16:48 EDT 2019. Contains 328022 sequences. (Running on oeis4.)