cp's OEIS Frontend

A008304 Triangle read by rows: T(n,k) (n>=1; 1<=k<=n) is the number of permutations of [n] in which the longest increasing run has length k.

%I A008304 #71 Nov 28 2023 13:05:03
%S A008304 1,1,1,1,4,1,1,16,6,1,1,69,41,8,1,1,348,293,67,10,1,1,2016,2309,602,
%T A008304 99,12,1,1,13357,19975,5811,1024,137,14,1,1,99376,189524,60875,11304,
%U A008304 1602,181,16,1,1,822040,1960041,690729,133669,19710,2360,231,18,1,1,7477161
%N A008304 Triangle read by rows: T(n,k) (n>=1; 1<=k<=n) is the number of permutations of [n] in which the longest increasing run has length k.
%C A008304 Row n has n terms.
%D A008304 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1.
%H A008304 Alois P. Heinz, <a href="/A008304/b008304.txt">Rows n = 1..141, flattened</a>
%H A008304 Max A. Alekseyev, <a href="http://arxiv.org/abs/1205.4581">On the number of permutations with bounded run lengths</a>, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012
%H A008304 D. W. Wilson, <a href="/A008304/a008304.txt">Extended tables for A008304 and A064315</a>
%F A008304 E.g.f. of column k: 1/Sum_{n>=0} ((k+1)*n+1-x)*x^((k+1)*n)/((k+1)*n+1)! - 1/Sum_{n>=0} (k*n+1-x)*x^(k*n)/(k*n+1)!. - _Alois P. Heinz_, Oct 13 2013
%F A008304 T(n,k) = A122843(n,k) for k > n/2. - _Alois P. Heinz_, Oct 17 2013
%e A008304 Triangle T(n,k) begins:
%e A008304   1;
%e A008304   1,   1;
%e A008304   1,   4,   1;
%e A008304   1,  16,   6,  1;
%e A008304   1,  69,  41,  8,  1;
%e A008304   1, 348, 293, 67, 10,  1;
%e A008304   ...
%e A008304 T(3,2) = 4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround runs of length 2.
%p A008304 b:= proc(u, o, t, k) option remember; `if`(t=k, (u+o)!,
%p A008304       `if`(max(t, u)+o<k, 0, add(b(u+j-1, o-j, t+1, k), j=1..o)+
%p A008304       add(b(u-j, o+j-1, 1, k), j=1..u)))
%p A008304     end:
%p A008304 T:= (n, k)-> b(0, n, 0, k) -b(0, n, 0, k+1):
%p A008304 seq(seq(T(n,k), k=1..n), n=1..15);  # _Alois P. Heinz_, Oct 16 2013
%t A008304 b[u_, o_, t_, k_] := b[u, o, t, k] = If[t == k, (u + o)!, If[Max[t, u]+o < k, 0, Sum[b[u+j-1, o-j, t+1, k], {j, 1, o}] + Sum[b[u-j, o+j-1, 1, k], {j, 1, u}]]]; T[n_, k_] := b[0, n, 0, k] - b[0, n, 0, k+1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 15}] // Flatten (* _Jean-François Alcover_, Jan 10 2014, translated from _Alois P. Heinz_'s Maple code *)
%t A008304 (*additional code*)
%t A008304 nn=12;a[r_]:=Apply[Plus,Table[Normal[Series[y x^(r+1)/(1-Sum[y x^i,{i,1,r}]),{x,0,nn}]][[n]]/(n+r)!,{n,1,nn-r}]]/.y->-1;Map[Select[#,#>0&]&,Transpose[Prepend[Table[Drop[Range[0,nn]! CoefficientList[Series[1/(1-x-a[n+1])-1/(1-x-a[n]),{x,0,nn}],x],1],{n,1,8}],Table[1,{nn}]]]]//Grid (* _Geoffrey Critzer_, Feb 25 2014 *)
%Y A008304 Row sums give A000142. Sum_{k=1..n} k*T(n,k) = A064314(n). Cf. A064315.
%Y A008304 Columns k=1-10 give: A000012, A000303, A000402, A000434, A000456, A000467, A230055, A230234, A230235, A230236.
%Y A008304 T(2n+j,n+j) for j=0-10 gives: A230341, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.
%K A008304 nonn,tabl
%O A008304 1,5
%A A008304 _N. J. A. Sloane_
%E A008304 More terms from _David W. Wilson_, Sep 07 2001
%E A008304 Better description from _Emeric Deutsch_, May 08 2004