Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #45 Jul 27 2019 17:17:39
%S 1,1,2,6,23,110,631,4223,32301,277962,2657797,27954521,320752991,
%T 3987045780,53372351265,765499019221,11711207065229,190365226548070,
%U 3276401870322033,59523410471007913,1138295039078030599,22856576346825690128,480807130959249565541
%N Number of permutations avoiding the consecutive pattern 3412.
%C a(n) is the number of permutations on [n] that avoid the consecutive pattern 3412 (also number that avoid 2143).
%H Alois P. Heinz, <a href="/A113229/b113229.txt">Table of n, a(n) for n = 0..200</a> (terms n = 0..60 from Ray Chandler)
%H A. Baxter, B. Nakamura, and D. Zeilberger. <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html">Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes</a>
%H V. Dotsenko and A. Khoroshkin, <a href="http://arxiv.org/abs/1109.2690">Shuffle algebras, homology, and consecutive pattern avoidance</a>, arXiv preprint arXiv:1109.2690 [math.CO], 2011.
%H Sergi Elizalde, <a href="https://arxiv.org/abs/math/0505254">Asymptotic enumeration of permutations avoiding generalized patterns</a>, arXiv:math/0505254 [math.CO], 2005.
%H Sergi Elizalde, <a href="https://doi.org/10.1016/j.aam.2005.05.006">Asymptotic enumeration of permutations avoiding generalized patterns</a>, Adv. in Appl. Math. 36 (2006), no. 2, 138-155.
%H S. Elizalde and M. Noy, <a href="http://dx.doi.org/10.1016/S0196-8858(02)00527-4">Consecutive patterns in permutations</a>, Adv. Appl. Math. 30 (2003), 110-125.
%H Steven Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/csolve/av.pdf">Pattern-Avoiding Permutations</a> [Broken link?]
%H Steven Finch, <a href="/A240885/a240885.pdf">Pattern-Avoiding Permutations</a> [Cached copy, with permission]
%F 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.
%F a(n) ~ c * d^n * n!, where d = 0.9561742431150784273897350385923872770208469..., c = 1.1465405299007850875068632404058971045769... . - _Vaclav Kotesovec_, Aug 23 2014
%e The 5! - a(5) = 10 permutations on [5] not counted by a(5) are 14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.
%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p add(b(u-j, o+j-1, `if`(t>0 and j>t, t-j, 0)), j=1..u)+
%p add(b(u+j-1, o-j, j), j=`if`(t<0,1-t,1)..o))
%p end:
%p a:= n-> b(n, 0$2):
%p seq(a(n), n=0..25); # _Alois P. Heinz_, Nov 07 2013
%t 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_ *)
%Y Cf. A113228, A117156, A117158, A117226, A201692, A201693.
%Y Column k=0 of A264319.
%K nonn
%O 0,3
%A _David Callan_, Oct 19 2005