A202213 Number of permutations of [n] avoiding the consecutive pattern 45321.

1, 1, 2, 6, 24, 119, 708, 4914, 38976, 347765, 3447712, 37598286, 447294144, 5764747515, 80011430240, 1189835682714, 18873422539776, 318085061976105, 5676223254661760, 106919460527212950, 2119973556022047744, 44136046410218669055, 962630898723772565760

Offset: 0

Author

Ray Chandler, Dec 14 2011

Keywords

• nonn

Comments

a(n) is the number of permutations on [n] that avoid the consecutive pattern 45321. It is the same as the number of permutations which avoid 12354, 21345 or 54312.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..200 (terms n = 1..40 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 Theorem 3.2 (p. 116) with m = a = 3 and u = 0.
• Eric Weisstein's World of Mathematics, Pochhammer Symbol.
• Wikipedia, Falling and rising factorials.

Crossrefs

Cf. A177523, A202214-A202236, A329070.

Column k = 0 of A264781 and row m = 2 of A327722.

Programs

Maple

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

Mathematica

b[u_, o_, t_] := b[u, o, t] = If[u+o == 0, 1, Sum[b[u+j-1, o-j, If[u+j-1 < j, 0, j]], {j, 1, o}] + If[t == -2, 0, Sum[b[u-j, o+j-1, If[j0, -1, If[t == -1, -2, 0]]]], {j, 1, u}]]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 12 2015, after Alois P. Heinz *)

Formula

From Petros Hadjicostas, Nov 02 2019: (Start)

E.g.f.: 1/W(z), where W(z) = 1 + Sum_{n >= 0} (-1)^(n+1)* z^(4*n+1)/(b(n)*(4*n+1)) with b(n) = A329070(n,4) = (4*n)!/(4^n*(1/4)_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^(4)(z) + z*W'(z) = 0 with W(0) = 1, W'(0) = -1, and W^(k)(0) = 0 for k = 2..3. [See Theorem 3.2 (with m = a = 3 and u = 0) in Elizalde and Noy (2003).]

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