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!)
A113228 a(n) is the number of permutations of [1..n] that avoid the consecutive pattern 1324 (equally, the permutations that avoid 4231). 9
1, 1, 2, 6, 23, 110, 632, 4229, 32337, 278204, 2659223, 27959880, 320706444, 3985116699, 53328433923, 764610089967, 11693644958690, 190015358010114, 3269272324528547, 59373764638615449, 1135048629795612125, 22783668363316052016, 479111084084119883217 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..200 (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, arXiv:math/0505254 [math.CO], 2005.

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

S. Elizalde and M. 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]

FORMULA

In the recurrence coded in Mathematica below, w[n, a] = #1324-avoiding permutations on [n] with first entry a; u[n, a, b] is the number that start with an ascent a<b and v[n, a] is the number that start with a descent from a (n>=2). The main sum for u[n, a, b] counts by length k of the longest initial increasing subsequence. The cases k=2, k=3, k>=4 are considered separately.

a(n) ~ c * d^n * n!, where d = 0.9558503134742499886507376383060906722796..., c = 1.15104449887019137479444895134035262624... . - Vaclav Kotesovec, Aug 23 2014

EXAMPLE

In 24135, the entries 2435 are in relative order 1324 but they do not occur consecutively and 24135 avoids the consecutive 1324 pattern.

MAPLE

b:= proc(u, o, t) option remember; `if`(u+o=0, 1,

       add(b(u-j, o+j-1, `if`(t>0 and j<t, -j, 0)), j=1..u)+

       add(b(u+j-1, o-j, j), j=1..`if`(t<0, min(-t-1, o), o)))

    end:

a:= n-> b(n, 0, 0):

seq(a(n), n=0..25);  # Alois P. Heinz, Nov 07 2013

MATHEMATICA

Clear[u, v, w]; w[0]=1; w[1]=1; w[2]=2; w[n_]/; n>=3 := w[n] = Sum[w[n, a], {a, n}]; w[1, 1] = w[2, 1] = w[2, 2] = 1; w[n_, a_]/; n>=3 && 1<=a<=n := Sum[u[n, a, b], {b, a+1, n}] + v[n, a]; v[1, 1]=1; v[n_, a_]/; n>=2 && a==1 := 0; v[n_, a_]/; n>=2 && 2<=a<=n := wCumulative[n-1, a-1]; wCumulative[n_, k_]/; Not[1<=k<=n] := 0; wCumulative[n_, k_]/; 1<=k<=n := wCumulative[n, k] = Sum[w[n, a], {a, k}]; u[n_, a_, b_]/; Not[1<=a<b<=n] := 0; u[2, 1, 2]=u[3, 1, 2]=u[3, 1, 3]=u[3, 2, 3]=1; u[n_, a_, b_]/; n>=4 && 1<=a<b<=n := u[n, a, b] = wCumulative[n-2, a-1] + Sum[ Sum[u[n-2, c, d], {d, c+1, b-2}] + v[n-2, c], {c, a, b-2}] + (n-b)wCumulative[n-3, b-2] + Sum[ Sum[ (Sum[u[n-3, d, e], {e, d+1, c-3}] + v[n-3, d]), {d, b-1, c-3}], {c, b+1, n}] + Sum[(n-c)bi[c-b-1, i]wCumulative[n-4-i, c-i-3], {i, 0, n-2-b}, {c, b+i+1, n-1}] + Sum[ bi[c-b-1, i]*Sum[(Sum[u[n-4-i, e, f], {f, e+1, d-i-4}] + v[n-4-i, e]), {d, c+1, n}, {e, c-i-2, d-i-4}], {i, 0, n-3-b}, {c, b+i+1, n-1}] + If[{a, b}=={1, 2}, 1, 0]; Table[w[n], {n, 0, 12}]

(* Second program: *)

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, -j, 0]], {j, 1, u}] + Sum[b[u+j-1, o-j, j], {j, 1, If[t<0, Min[-t-1, o], o]}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* Jean-Fran├žois Alcover, Jan 19 2017, after Alois P. Heinz *)

CROSSREFS

Cf. A113229, A117156, A117158, A117226, A201692, A201693, A231166.

Column k=0 of A264173.

Sequence in context: A117156 A201692 A113229 * A201693 A063255 A117158

Adjacent sequences:  A113225 A113226 A113227 * A113229 A113230 A113231

KEYWORD

nonn

AUTHOR

David Callan, Oct 19 2005

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:09 EDT 2022. Contains 357239 sequences. (Running on oeis4.)