|
| |
|
|
A137554
|
|
Number of permutations in S_n avoiding {bar 5}{bar 4}132 (i.e., every occurrence of 132 is contained in an occurrence of a 54132).
|
|
0
|
|
|
|
1, 2, 5, 14, 43, 147, 575, 2648, 14617, 96696, 754585, 6794015, 69116493, 781266266, 9688636317, 130551322618, 1897079161639, 29549030800315, 490880073850267, 8660360684895644, 161671375033644161, 3183279386216962364
(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..22.
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.
|
|
|
CROSSREFS
|
Sequence in context: A149881 A148334 A149882 * A137555 A137556 A137557
Adjacent sequences: A137551 A137552 A137553 * A137555 A137556 A137557
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Lara Pudwell, Apr 25 2008
|
|
|
STATUS
|
approved
|
| |
|
|
