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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137550 Number of permutations in S_n avoiding 31{bar 5}{bar 4}2 (i.e., every occurrence of 312 is contained in an occurrence of a 31542). 0
1, 1, 2, 5, 14, 43, 144, 522, 2030, 8398, 36714, 168793, 813112, 4091735, 21451972, 116891160, 660554822, 3863775322, 23353384298, 145634065581, 935743895590, 6187151514364, 42050180222692, 293448121230999, 2100678197412864 (list; graph; refs; listen; history; text; internal format)
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)
From David Callan, Oct 14 2012: (Start)
a(n) appears to be the number of integer sequences u = (u(0),u(1),...,u(n-1)) satisfying (i) 0<=u(i)<=i for all i, (ii) either u(i)<u(i+1) or u(i+1)=0 for all i, (iii) whenever nonzero entries a,b (in that order) are separated in u by precisely k>=1 0's, b-k does not lie in the interval [1,a].
To illustrate, 020 violates condition (i), 011 violates condition (ii), and 0102 violates condition (iii).
When n=3 the 5 "u" sequences are 000, 001, 002, 010, 012, and when n=4 the 14 "u" sequences are 0000, 0001, 0002, 0003, 0010, 0012, 0013, 0020, 0023, 0100, 0101, 0103, 0120, 0123.
The sequences satisfying the first two conditions are counted by the Bell numbers A000110. (End)
LINKS
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
Cf. A000110.
Sequence in context: A137549 A014327 A173437 * A047970 A160701 A137551
KEYWORD
nonn
AUTHOR
Lara Pudwell, Apr 25 2008
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Jul 10 2023
STATUS
approved

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 March 28 13:42 EDT 2024. Contains 371254 sequences. (Running on oeis4.)