A137542 Number of permutations in S_n avoiding {bar 1}3425 (i.e., every occurrence of 3425 is contained in an occurrence of a 13425).

1, 1, 2, 6, 23, 104, 533, 3038, 19128, 133112, 1028287, 8859284, 85298231, 915617310, 10887682031, 142169785210

Offset: 0

Author

Lara Pudwell, Apr 25 2008

Keywords

• nonn
• more

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)

Examples

			See example in A137546.
		

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. A137546.

Extensions

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

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