A113228 a(n) is the number of permutations of [1..n] that avoid the consecutive pattern 1324 (equally, the permutations that avoid 4231).

1, 1, 2, 6, 23, 110, 632, 4229, 32337, 278204, 2659223, 27959880, 320706444, 3985116699, 53328433923, 764610089967, 11693644958690, 190015358010114, 3269272324528547, 59373764638615449, 1135048629795612125, 22783668363316052016, 479111084084119883217

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 0..60 from Ray Chandler)

Andrew Baxter, Brian Nakamura, and Doron Zeilberger, Automatic generation of theorems and proofs on enumerating consecutive Wilf-classes

Colin Defant, Noah Kravitz, and Nathan Williams, The Ungar Games, arXiv:2302.06552 [math.CO], 2023.

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.

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]

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