login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A117158 Number of permutations avoiding the consecutive pattern 1234. 23
1, 1, 2, 6, 23, 111, 642, 4326, 33333, 288901, 2782082, 29471046, 340568843, 4263603891, 57482264322, 830335952166, 12793889924553, 209449977967081, 3630626729775362, 66429958806679686, 1279448352687538463, 25874432578888440471, 548178875969847203202 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 4 16:41 EDT 2022. Contains 357239 sequences. (Running on oeis4.)