login
A158432
Number of permutations of 1..n containing the relative rank sequence { 45312 } at any spacing.
3
1, 26, 458, 6996, 101072, 1438112, 20598112, 300892896, 4521034917, 70286670034, 1135485759114, 19121776482564, 336412530327804, 6191800556586104, 119301546930406184, 2406376964044265344, 50786085223779295344, 1120447461653440780128, 25810064637612342838624
OFFSET
5,2
COMMENTS
Same series for 54321 12345 45321 21345 12354 54312 34521 32145 12543 54123 23451 43215 15432 51234 21354 34512 32154 21543 45123.
LINKS
Eric Weisstein's World of Mathematics, Permutation Pattern
FORMULA
a(n) = A214152(n,5) = A000142(n)-A047889(n) = A000142(n)-A214015(n,4).
MAPLE
h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
+add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
a:= n-> n! -g(n, 4, []):
seq(a(n), n=5..25); # Alois P. Heinz, Jul 05 2012
# second Maple program
a:= proc(n) option remember; `if`(n<5, 0, `if`(n=5, 1,
((132-142*n-301*n^2-35*n^3+25*n^4+n^5)*a(n-1)
-2*(10*n^3+33*n^2-181*n-2)*(n-1)^2*a(n-2)
+64*(n-2)^2*(n-1)^3*a(n-3))/ ((n+4)*(n-5)*(n+3)^2)))
end:
seq(a(n), n=5..30); # Alois P. Heinz, Sep 26 2012
MATHEMATICA
h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]!/Product[Product[1+l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := If[n == 0 || i === 1, h[Join[l, Array[1 &, n]]]^2, If[i < 1, 0, Sum[g[n - i*j, i - 1, Join[l, Array[i &, j]]], {j, 0, n/i}]]];
a[n_] := n! - g[n, 4, {}];
Table[a[n], {n, 5, 25}] (* Jean-François Alcover, Jun 19 2018, after Alois P. Heinz's first program *)
CROSSREFS
KEYWORD
nonn
AUTHOR
R. H. Hardin, Mar 18 2009
EXTENSIONS
Extended beyond a(16) by Alois P. Heinz, Jul 05 2012
STATUS
approved