A117226 Number of permutations of [n] avoiding the consecutive pattern 1243.

1, 1, 2, 6, 23, 110, 630, 4204, 32054, 274914, 2619692, 27459344, 313990182, 3889585408, 51888955808, 741668212080, 11307669002720, 183174676857608, 3141820432768752, 56882461258572976, 1084056190235653304, 21692744773505849952, 454758269790599361968

Offset

0,3

Comments

a(n) is the number of permutations on [n] that avoid the consecutive pattern 1243. It is the same as the number of permutations which avoid 3421, 4312 or 2134.

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, 2011.

Sergi Elizalde and Marc Noy, Consecutive patterns in permutations, Adv. Appl. Math. 30 (2003), 110-125; see p. 120.

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. Appl. Math. 36 (2006), 138-155.

Steven Finch, Pattern-Avoiding Permutations. [Archived copy]

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

Eric Weisstein's World of Mathematics, Pochhammer Symbol.

Wikipedia, Falling and rising factorials.

Formula

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

From Petros Hadjicostas, Nov 01 2019:

E.g.f.: 1/W(z), where W(z) := 1 + Sum_{n >= 0} (-1)^(n+1)* z^(3*n+1)/(b(n)*(3*n+1)) with b(n) = A176730(n) = (3*n)!/(3^n*(1/3)_n). (Here (x)_n = x*(x + 1)*...*(x + n - 1) is the Pochhammer symbol, or rising factorial, which is denoted by (x)^n in some papers and books.) The function W(z) satisfies the o.d.e. W'''(z) + z*W'(z) = 0 with W(0) = 1, W'(0) = -1, and W''(0) = 0. [See Theorem 4.3 (Case 1243 with u = 0) in Elizalde and Noy (2003).]

a(n) = Sum_{m = 0..floor((n-1)/3)} (-3)^m * (1/3)_m * binomial(n, 3*m+1) * a(n-3*m-1) for n >= 1 with a(0) = 1. (End)

Maple

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

Mathematica

A[x_]:=Integrate[AiryAi[ -t], {t, 0, x}]; B[x_]:=Integrate[AiryBi[ -t], {t, 0, x}];
c=-3^(2/3)*Gamma[2/3]/2; d=-3^(1/6)*Gamma[2/3]/2;
a[n_]:=SeriesCoefficient[1/(c*A[x]+d*B[x]+1), {x, 0, n}]*n!; Table[a[n], {n, 0, 10}] (* fixed by Vaclav Kotesovec, Aug 23 2014 *)
(* constant d: *) 1/x/.FindRoot[3^(2/3)*Gamma[2/3]/2 * Integrate[AiryAi[-t], {t, 0, x}] + 3^(1/6)*Gamma[2/3]/2 * Integrate[AiryBi[-t], {t, 0, x}]==1, {x, 1}, WorkingPrecision->50] (* Vaclav Kotesovec, Aug 23 2014 *)

Crossrefs

Cf. A113228, A113229, A117156, A117158, A176730, A201692, A201693, A231166.

Row m = 1 of A327722.

Sequence in context: A224786 A320566 A205802 * A117156 A201692 A113229

Adjacent sequences: A117223 A117224 A117225 * A117227 A117228 A117229

Keyword

nonn

Author

Steven Finch, Apr 26 2006

Status

approved