A158432 Number of permutations of 1..n containing the relative rank sequence { 45312 } at any spacing.

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

Alois P. Heinz, Table of n, a(n) for n = 5..200

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

Cf. A000142, A047889, A056986, A158005, A214015, A214152.

Sequence in context: A025954 A158436 A158431 * A021974 A158433 A158423

Adjacent sequences: A158429 A158430 A158431 * A158433 A158434 A158435

Keyword

nonn

Author

R. H. Hardin, Mar 18 2009

Extensions

Extended beyond a(16) by Alois P. Heinz, Jul 05 2012

Status

approved