OFFSET
0,3
COMMENTS
a(n) is the number of permutations on [n] that avoid the consecutive pattern 3412 (also number that avoid 2143).
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 0..60 from Ray Chandler)
A. Baxter, B. Nakamura, and D. Zeilberger. Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes
V. Dotsenko and A. Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, arXiv preprint arXiv:1109.2690 [math.CO], 2011.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, arXiv:math/0505254 [math.CO], 2005.
Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
S. Elizalde and M. Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.
Steven Finch, Pattern-Avoiding Permutations [Broken link?]
Steven Finch, Pattern-Avoiding Permutations [Cached copy, with permission]
FORMULA
The Dotsenko et al. reference gives a g.f. There is an associated triangle of numbers c_{n,l} that should be added to the OEIS if it is not already present.
a(n) ~ c * d^n * n!, where d = 0.9561742431150784273897350385923872770208469..., c = 1.1465405299007850875068632404058971045769... . - Vaclav Kotesovec, Aug 23 2014
EXAMPLE
The 5! - a(5) = 10 permutations on [5] not counted by a(5) are 14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.
MAPLE
b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
add(b(u-j, o+j-1, `if`(t>0 and j>t, t-j, 0)), j=1..u)+
add(b(u+j-1, o-j, j), j=`if`(t<0, 1-t, 1)..o))
end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..25); # Alois P. Heinz, Nov 07 2013
MATHEMATICA
b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[b[u-j, o+j-1, If[t>0 && j>t, t-j, 0]], {j, 1, u}] + Sum[b[u+j-1, o-j, j], {j, Range[If[t<0, 1-t, 1], o]}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 13 2015, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
David Callan, Oct 19 2005
STATUS
approved