login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A137533 Number of permutations in S_n avoiding {bar 1}432 (i.e., every occurrence of 432 is contained in an occurrence of a 1432). 1
1, 2, 5, 15, 55, 248, 1357, 8809, 66323, 568238, 5456689, 58023731, 676566591, 8581174564, 117594655061, 1731202603885, 27245237545195, 456412842304058, 8108103076572185, 152241172196748919, 3012385194815011031 (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

Lara Pudwell, Table of n, a(n) for n = 1..30

David Callan, A Combinatorial Interpretation of the Eigensequence for Composition, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.4. (Erratum: The rising and falling factorials in the second displayed line on page 12 should be interchanged.)

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.

MATHEMATICA

FallingFactorial[n_, k_] := Product[n - i, {i, 0, k - 1}];

RisingFactorial[n_, k_] := Product[n + i, {i, 0, k - 1}];

Table[(n - 1)! + Sum[FallingFactorial[k, i] RisingFactorial[n - 2 - k, j], {k, 0, n - 2}, {i, 0, k}, {j, 0, k - i}], {n, 15}] (* David Callan, Nov 21 2011 *)

CROSSREFS

Sequence in context: A109319 A059219 A242275 * A121392 A216388 A005976

Adjacent sequences:  A137530 A137531 A137532 * A137534 A137535 A137536

KEYWORD

nonn,easy

AUTHOR

Lara Pudwell, Apr 25 2008

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 May 6 00:41 EDT 2021. Contains 343579 sequences. (Running on oeis4.)