A113229 Number of permutations avoiding the consecutive pattern 3412.

1, 1, 2, 6, 23, 110, 631, 4223, 32301, 277962, 2657797, 27954521, 320752991, 3987045780, 53372351265, 765499019221, 11711207065229, 190365226548070, 3276401870322033, 59523410471007913, 1138295039078030599, 22856576346825690128, 480807130959249565541

Offset

0,3

Comments

a(n) is the number of permutations on [n] that avoid the consecutive pattern 3412 (also number that avoid 2143).

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

V. Dotsenko and A. Khoroshkin, Shuffle algebras, homology, and consecutive pattern avoidance, arXiv preprint arXiv:1109.2690 [math.CO], 2011.

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

The Dotsenko et al. reference gives a g.f. There is an associated triangle of numbers c_{n,l} that should be added to the OEIS if it is not already present.

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

Example

The 5! - a(5) = 10 permutations on [5] not counted by a(5) are 14523, 24513, 34125, 34512, 35124, 43512, 45123, 45132, 45231, 53412.

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, t-j, 0)), j=1..u)+
      add(b(u+j-1, o-j, j), j=`if`(t<0, 1-t, 1)..o))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Nov 07 2013

Mathematica

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, t-j, 0]], {j, 1, u}] + Sum[b[u+j-1, o-j, j], {j, Range[If[t<0, 1-t, 1], o]}]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 13 2015, after Alois P. Heinz *)

Crossrefs

Cf. A113228, A117156, A117158, A117226, A201692, A201693.

Column k=0 of A264319.

Sequence in context: A117226 A117156 A201692 * A113228 A201693 A063255

Adjacent sequences: A113226 A113227 A113228 * A113230 A113231 A113232

Keyword

nonn

Author

David Callan, Oct 19 2005

Status

approved