A177478 Permutations avoiding the consecutive patterns 4312 and 4213.

1, 1, 2, 6, 22, 100, 540, 3388, 24248, 195048, 1742860, 17127880, 183617280, 2132433940, 26669752928, 357375269160, 5108084756320, 77574769941760, 1247401873186560, 21172559509803520, 378282904982091200, 7096584257305845120, 139471475802695196160

Offset: 0

Author

Signy Olafsdottir (signy06(AT)ru.is), May 09 2010

Keywords

• nonn

Comments

a(n) gives the number of permutations of [n] which avoid both the pattern 4312 and 4213 consecutively. Also the number avoiding the pairs {2134, 3124}, {1243, 1342}, or {3421, 2431} (by symmetry).

This can also be considered avoiding a partially ordered pattern: Suppose p

The Baxter-Nakamura-Zeilberger paper has an associated Maple package. See Links.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..120 (terms n = 1..40 from Ray Chandler)
• A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
• S. Kitaev, Introduction to partially ordered patterns, Discrete Applied Mathematics 155 (2007), 929-944.

Crossrefs

Cf. A117226, A117156.

Programs

Maple

b:= proc(u, o, s, t) option remember; `if`(u+o=0, 1,
       add(b(u-j, o+j-1, t, j), j=1..u)+
       add(b(u+j-1, o-j, 0, 0), j=`if`(s>0, s+t-1, 1)..o))
    end:
a:= n-> b(0, n, 0, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Oct 25 2013

Mathematica

b[u_, o_, s_, t_] := b[u, o, s, t] = If[u+o == 0, 1, Sum[b[u-j, o+j-1, t, j], {j, 1, u}] + Sum[b[u+j-1, o-j, 0, 0], {j, If[s > 0, s+t-1, 1], o}]];
a[n_] := b[0, n, 0, 0];
a /@ Range[0, 25] (* Jean-François Alcover, Nov 03 2020, after Alois P. Heinz *)

Formula

a(n) ~ c * d^n * n!, where d = 0.89333294588184091624317413051..., c = 1.4839698712287023868073431417... . - Vaclav Kotesovec, Aug 24 2014

Extensions

More terms, succinct title, additional comments, new references from Andrew Baxter, Jan 21 2011

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.