login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A117158 Number of permutations avoiding the consecutive pattern 1234. 20
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 [Broken link?]

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

I. 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

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

FORMULA

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));

f:=(4*k)!/(2*k)!; b:=(4*k+1)!/(2*k+1)!; c:=(4*k+2)!/(2*k+1)!; d:=(4*k+3)!/(2*k+2)!. - Sergei N. Gladkovskii, Nov 30 2011

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.

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 03:08 EST 2019. Contains 319370 sequences. (Running on oeis4.)