|
|
A202213
|
|
Number of permutations of [n] avoiding the consecutive pattern 45321.
|
|
27
|
|
|
1, 1, 2, 6, 24, 119, 708, 4914, 38976, 347765, 3447712, 37598286, 447294144, 5764747515, 80011430240, 1189835682714, 18873422539776, 318085061976105, 5676223254661760, 106919460527212950, 2119973556022047744, 44136046410218669055, 962630898723772565760
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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):
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|