login
A159175
Number of permutations of 1..n containing the relative rank sequence { 1234567 } at any spacing.
3
1, 50, 1578, 40884, 958809, 21353634, 463945294, 9996042284, 215831724525, 4702905606350, 103912444955422, 2336099774748540, 53567906041439136, 1255172323669315848, 30095426182382305848, 739238316780966277616, 18619024923770934306358, 481234428294016650524172
OFFSET
7,2
COMMENTS
Same series (among rank sequences with inversion = reversal) for 3214765 2134576.
LINKS
Eric Weisstein's World of Mathematics, Permutation Pattern
FORMULA
a(n) = A214152(n,7) = A000142(n)-A052399(n) = A000142(n)-A214015(n,6). - Alois P. Heinz, Jul 05 2012
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, 6, []):
seq(a(n), n=7..25); # Alois P. Heinz, Jul 05 2012
# second Maple program
a:= proc(n) option remember; `if`(n<7, 0, `if`(n=7, 1, ((-93464*n+1072*n^4
+72128-125284*n^2+84*n^6+994*n^5-30491*n^3+n^7) *a(n-1)
-4*(14*n^5+399*n^4+1124*n^3-7354*n^2-23983*n-5042)*(n-1)^2 *a(n-2)
+4*(-7359-2629*n+1596*n^2+196*n^3)*(n-1)^2*(n-2)^2 *a(n-3)
-1152*(1+2*n)*(n-1)^2*(n-2)^2*(n-3)^2 *a(n-4))/
((n-7)*(n+9)*(n+8)^2*(n+5)^2)))
end:
seq(a(n), n=7..30); # Alois P. Heinz, Sep 27 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, 6, {}];
Table[a[n], {n, 7, 25}] (* Jean-François Alcover, Jun 19 2018, from first Maple program *)
KEYWORD
nonn
AUTHOR
R. H. Hardin Apr 05 2009
EXTENSIONS
Extended beyond a(16) by Alois P. Heinz, Jul 05 2012
STATUS
approved