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