OFFSET
0,3
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.
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)
MAPLE
b:= proc(u, o, t) option remember; `if`(u+o=0, 1,
add(b(u+j-1, o-j, `if`(u+j-1<j, 0, j)), j=1..o)+
`if`(t=-2, 0, add(b(u-j, o+j-1, `if`(j<t, 0,
`if`(t>0, -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[j<t, 0, If[t>0, -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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Ray Chandler, Dec 14 2011
STATUS
approved