cp's OEIS Frontend

A113229 Number of permutations avoiding the consecutive pattern 3412.

%I A113229 #45 Jul 27 2019 17:17:39
%S A113229 1,1,2,6,23,110,631,4223,32301,277962,2657797,27954521,320752991,
%T A113229 3987045780,53372351265,765499019221,11711207065229,190365226548070,
%U A113229 3276401870322033,59523410471007913,1138295039078030599,22856576346825690128,480807130959249565541
%N A113229 Number of permutations avoiding the consecutive pattern 3412.
%C A113229 a(n) is the number of permutations on [n] that avoid the consecutive pattern 3412 (also number that avoid 2143).
%H A113229 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 A113229 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 A113229 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 A113229 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 A113229 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 A113229 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 A113229 Steven Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/csolve/av.pdf">Pattern-Avoiding Permutations</a> [Broken link?]
%H A113229 Steven Finch, <a href="/A240885/a240885.pdf">Pattern-Avoiding Permutations</a> [Cached copy, with permission]
%F A113229 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 A113229 a(n) ~ c * d^n * n!, where d = 0.9561742431150784273897350385923872770208469..., c = 1.1465405299007850875068632404058971045769... . - _Vaclav Kotesovec_, Aug 23 2014
%e A113229 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 A113229 b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p A113229       add(b(u-j, o+j-1, `if`(t>0 and j>t, t-j, 0)), j=1..u)+
%p A113229       add(b(u+j-1, o-j, j), j=`if`(t<0,1-t,1)..o))
%p A113229     end:
%p A113229 a:= n-> b(n, 0$2):
%p A113229 seq(a(n), n=0..25);  # _Alois P. Heinz_, Nov 07 2013
%t A113229 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 A113229 Cf. A113228, A117156, A117158, A117226, A201692, A201693.
%Y A113229 Column k=0 of A264319.
%K A113229 nonn
%O A113229 0,3
%A A113229 _David Callan_, Oct 19 2005