|
%I #68 Mar 11 2021 17:29:35
%S 1,1,2,6,23,111,642,4326,33333,288901,2782082,29471046,340568843,
%T 4263603891,57482264322,830335952166,12793889924553,209449977967081,
%U 3630626729775362,66429958806679686,1279448352687538463,25874432578888440471,548178875969847203202
%N Number of permutations avoiding the consecutive pattern 1234.
%C a(n) is the number of permutations on [n] that avoid the consecutive pattern 1234. It is the same as the number of permutations which avoid 4321.
%D F. N. David and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962, pages 156-157.
%H Alois P. Heinz, <a href="/A117158/b117158.txt">Table of n, a(n) for n = 0..450</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 Sergi Elizalde, <a href="http://dx.doi.org/10.1016/j.aam.2005.05.006">Asymptotic enumeration of permutations avoiding generalized patterns</a>, Adv. Appl. Math. 36 (2006), 138-155.
%H Sergi Elizalde and Marc 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="https://web.archive.org/web/20150405060634/http://www.people.fas.harvard.edu/~sfinch/csolve/av.pdf">Pattern-Avoiding Permutations</a>. [Archived version]
%H Steven Finch, <a href="/A240885/a240885.pdf">Pattern-Avoiding Permutations</a>. [Cached copy, with permission]
%H Ira M. Gessel, <a href="http://dx.doi.org/10.1016/0097-3165(90)90060-A">Symmetric functions and P-recursiveness</a>, J. Combin. Theory A 53 (1990), 257-285.
%H Ira M. Gessel, Yan Zhuang, <a href="https://arxiv.org/abs/1408.1886">Counting permutations by alternating descents</a>, arXiv:1408.1886 [math.CO], 2014. See displayed equation before Eq. (3) and set m=4. - _N. J. A. Sloane_, Aug 11 2014
%H Kaarel Hänni, <a href="https://arxiv.org/abs/2011.14360">Asymptotics of descent functions</a>, arXiv:2011.14360 [math.CO], Nov 29 2020, p. 14.
%H Mingjia Yang, Doron Zeilberger, <a href="https://arxiv.org/abs/1805.06077">Increasing Consecutive Patterns in Words</a>, arXiv:1805.06077 [math.CO], 2018.
%H Mingjia Yang, <a href="https://doi.org/10.7282/t3-d9z1-aw94">An experimental walk in patterns, partitions, and words</a>, Ph. D. Dissertation, Rutgers University (2020).
%F From _Sergei N. Gladkovskii_, Nov 30 2011: (Start)
%F E.g.f.: 2/(exp(-x) + cos(x) - sin(x)) = 1/W(0) with continued fraction
%F W(k) = 1 + (x^(2*k))/(f + f*x/(4*k + 1 - x - (4*k + 1)*b/R)), where R := x^(2*k) + b -(x^(4*k+1))/(c + (x^(2*k+1)) + x*c/T); T := 4*k + 3 - x - (4*k + 3)*d/(d +(x^(2*k+1))/W(k+1)), and
%F f := (4*k)!/(2*k)!; b := (4*k + 1)!/(2*k + 1)!; c := (4*k + 2)!/(2*k + 1)!; and d :=(4*k + 3)!/(2*k + 2)!. (End)
%F a(n) ~ n! / (sin(r)*r^(n+1)), where r = 1.0384156372665563... is the root of the equation exp(-r) + cos(r) = sin(r). - _Vaclav Kotesovec_, Dec 11 2013
%p b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
%p `if`(t<2, add(b(u+j-1, o-j, t+1), j=1..o), 0)+
%p add(b(u-j, o+j-1, 0), j=1..u))
%p end:
%p a:= n-> b(n, 0, 0):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Oct 07 2013
%t a[n_]:=Coefficient[Series[2/(Cos[x]-Sin[x]+Exp[ -x]),{x,0,30}],x^n]*n!
%t (* second program: *)
%t b[u_, o_, t_] := b[u, o, t] = If[u+o==0, 1, If[t<2, Sum[b[u+j-1, o-j, t+1], {j, 1, o}], 0] + Sum[b[u-j, o+j-1, 0], {j, 1, u}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Nov 23 2015, after _Alois P. Heinz_ *)
%Y Cf. A022558, A049774, A111004, A113228, A113229, A117156, A117226, A177523, A177533, A201692, A201693, A230051, A324132.
%Y Column k=0 of A220183.
%Y Column k=7 of A242784.
%K nonn
%O 0,3
%A _Steven Finch_, Apr 26 2006
|
