A117158 Number of permutations avoiding the consecutive pattern 1234.

1, 1, 2, 6, 23, 111, 642, 4326, 33333, 288901, 2782082, 29471046, 340568843, 4263603891, 57482264322, 830335952166, 12793889924553, 209449977967081, 3630626729775362, 66429958806679686, 1279448352687538463, 25874432578888440471, 548178875969847203202

Offset

0,3

Comments

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.

References

F. N. David and D. E. Barton, Combinatorial Chance, Hafner, New York, 1962, pages 156-157.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..450 (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.

Sergi Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. Appl. Math. 36 (2006), 138-155.

Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125.

Steven Finch, Pattern-Avoiding Permutations. [Archived version]

Steven Finch, Pattern-Avoiding Permutations. [Cached copy, with permission]

Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53 (1990), 257-285.

Ira M. Gessel, Yan Zhuang, Counting permutations by alternating descents, arXiv:1408.1886 [math.CO], 2014. See displayed equation before Eq. (3) and set m=4. - N. J. A. Sloane, Aug 11 2014

Kaarel Hänni, Asymptotics of descent functions, arXiv:2011.14360 [math.CO], Nov 29 2020, p. 14.

Mingjia Yang, Doron Zeilberger, Increasing Consecutive Patterns in Words, arXiv:1805.06077 [math.CO], 2018.

Mingjia Yang, An experimental walk in patterns, partitions, and words, Ph. D. Dissertation, Rutgers University (2020).

Formula

From Sergei N. Gladkovskii, Nov 30 2011: (Start)

E.g.f.: 2/(exp(-x) + cos(x) - sin(x)) = 1/W(0) with continued fraction

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 := (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)

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

Maple

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
      `if`(t<2, add(b(u+j-1, o-j, t+1), j=1..o), 0)+
      add(b(u-j, o+j-1, 0), j=1..u))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 07 2013

Mathematica

a[n_]:=Coefficient[Series[2/(Cos[x]-Sin[x]+Exp[ -x]), {x, 0, 30}], x^n]*n!
(* second program: *)
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 *)

Crossrefs

Cf. A022558, A049774, A111004, A113228, A113229, A117156, A117226, A177523, A177533, A201692, A201693, A230051, A324132.

Column k=0 of A220183.

Column k=7 of A242784.

Sequence in context: A113228 A201693 A063255 * A317128 A185334 A290280

Adjacent sequences: A117155 A117156 A117157 * A117159 A117160 A117161

Keyword

nonn

Author

Steven Finch, Apr 26 2006

Status

approved