OFFSET
0,3
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<s, r<s, o<p and o<r. To avoid spor means not to have four consecutive letters such that the first letter is larger than the second and the last one, the third letter is less than the second and the last one.
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.
FORMULA
a(n) ~ c * d^n * n!, where d = 0.89333294588184091624317413051..., c = 1.4839698712287023868073431417... . - Vaclav Kotesovec, Aug 24 2014
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Signy Olafsdottir (signy06(AT)ru.is), May 09 2010
EXTENSIONS
More terms, succinct title, additional comments, new references from Andrew Baxter, Jan 21 2011
STATUS
approved