cp's OEIS Frontend

A258690 Total number of longest increasing runs in all permutations of [n].

%I A258690 #13 Apr 15 2022 10:32:28
%S A258690 1,1,3,8,32,167,1096,8117,67859,627649,6394781,71201812,861677250,
%T A258690 11270215084,158564826122,2389093936957,38396351412220,
%U A258690 655832914215010,11865953978478454,226724258401651143,4562163514498852598,96430112680094188086,2136024671422363671272
%N A258690 Total number of longest increasing runs in all permutations of [n].
%C A258690 a(0) = 1 by convention.
%C A258690 a(n) >= n! = A000142(n).
%H A258690 Alois P. Heinz, <a href="/A258690/b258690.txt">Table of n, a(n) for n = 0..100</a>
%e A258690 a(1) = 1: (1).
%e A258690 a(2) = 3: (12), (2)(1).
%e A258690 a(3) = 8: (123), (13)2, 2(13), (23)1, 3(12), (3)(2)(1).
%p A258690 b:= proc(u, o, l, m, c) option remember;  `if`(u+o=0, `if`(l>m, 1,
%p A258690       `if`(l<m, c, c+1)), add(b(u-j, o+j-1, 1, max(l,m),
%p A258690       `if`(l>m, 1, `if`(l<m, c, c+1))), j=1..u)+
%p A258690           add(b(u+j-1, o-j, l+1, m, c), j=1..o))
%p A258690     end:
%p A258690 a:= n-> b(n, 0$4):
%p A258690 seq(a(n), n=0..25);
%t A258690 b[u_, o_, l_, m_, c_] := b[u, o, l, m, c] = If[u + o == 0, If[l > m, 1,
%t A258690      If[l < m, c, c + 1]], Sum[b[u - j, o + j - 1, 1, Max[l, m],
%t A258690      If[l > m, 1, If[l < m, c, c + 1]]], {j, 1, u}] +
%t A258690            Sum[b[u+j-1, o-j, l+1, m, c], {j, 1, o}]];
%t A258690 a[n_] :=  b[n, 0, 0, 0, 0];
%t A258690 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Apr 15 2022, after _Alois P. Heinz_ *)
%Y A258690 Cf. A000142, A008304, A167999.
%K A258690 nonn
%O A258690 0,3
%A A258690 _Alois P. Heinz_, Jun 07 2015