cp's OEIS Frontend

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

%I A158432 #22 Feb 16 2025 08:33:09
%S A158432 1,26,458,6996,101072,1438112,20598112,300892896,4521034917,
%T A158432 70286670034,1135485759114,19121776482564,336412530327804,
%U A158432 6191800556586104,119301546930406184,2406376964044265344,50786085223779295344,1120447461653440780128,25810064637612342838624
%N A158432 Number of permutations of 1..n containing the relative rank sequence { 45312 } at any spacing.
%C A158432 Same series for 54321 12345 45321 21345 12354 54312 34521 32145 12543 54123 23451 43215 15432 51234 21354 34512 32154 21543 45123.
%H A158432 Alois P. Heinz, <a href="/A158432/b158432.txt">Table of n, a(n) for n = 5..200</a>
%H A158432 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PermutationPattern.html">Permutation Pattern</a>
%F A158432 a(n) = A214152(n,5) = A000142(n)-A047889(n) = A000142(n)-A214015(n,4).
%p A158432 h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
%p A158432       +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
%p A158432     end:
%p A158432 g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
%p A158432                  add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
%p A158432 a:= n-> n! -g(n, 4, []):
%p A158432 seq(a(n), n=5..25);  # _Alois P. Heinz_, Jul 05 2012
%p A158432 # second Maple program
%p A158432 a:= proc(n) option remember; `if`(n<5, 0, `if`(n=5, 1,
%p A158432      ((132-142*n-301*n^2-35*n^3+25*n^4+n^5)*a(n-1)
%p A158432      -2*(10*n^3+33*n^2-181*n-2)*(n-1)^2*a(n-2)
%p A158432      +64*(n-2)^2*(n-1)^3*a(n-3))/ ((n+4)*(n-5)*(n+3)^2)))
%p A158432     end:
%p A158432 seq(a(n), n=5..30);  # _Alois P. Heinz_, Sep 26 2012
%t A158432 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}]];
%t A158432 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}]]];
%t A158432 a[n_] := n! - g[n, 4, {}];
%t A158432 Table[a[n], {n, 5, 25}] (* _Jean-François Alcover_, Jun 19 2018, after _Alois P. Heinz_'s first program *)
%Y A158432 Cf. A000142, A047889, A056986, A158005, A214015, A214152.
%K A158432 nonn
%O A158432 5,2
%A A158432 _R. H. Hardin_, Mar 18 2009
%E A158432 Extended beyond a(16) by _Alois P. Heinz_, Jul 05 2012