|
%I #71 Nov 28 2023 13:05:03
%S 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 99,12,1,1,13357,19975,5811,1024,137,14,1,1,99376,189524,60875,11304,
%U 1602,181,16,1,1,822040,1960041,690729,133669,19710,2360,231,18,1,1,7477161
%N 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 Row n has n terms.
%D F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1.
%H Alois P. Heinz, <a href="/A008304/b008304.txt">Rows n = 1..141, flattened</a>
%H 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 D. W. Wilson, <a href="/A008304/a008304.txt">Extended tables for A008304 and A064315</a>
%F 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 T(n,k) = A122843(n,k) for k > n/2. - _Alois P. Heinz_, Oct 17 2013
%e Triangle T(n,k) begins:
%e 1;
%e 1, 1;
%e 1, 4, 1;
%e 1, 16, 6, 1;
%e 1, 69, 41, 8, 1;
%e 1, 348, 293, 67, 10, 1;
%e ...
%e T(3,2) = 4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround runs of length 2.
%p b:= proc(u, o, t, k) option remember; `if`(t=k, (u+o)!,
%p `if`(max(t, u)+o<k, 0, add(b(u+j-1, o-j, t+1, k), j=1..o)+
%p add(b(u-j, o+j-1, 1, k), j=1..u)))
%p end:
%p T:= (n, k)-> b(0, n, 0, k) -b(0, n, 0, k+1):
%p seq(seq(T(n,k), k=1..n), n=1..15); # _Alois P. Heinz_, Oct 16 2013
%t 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 (*additional code*)
%t 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 Row sums give A000142. Sum_{k=1..n} k*T(n,k) = A064314(n). Cf. A064315.
%Y Columns k=1-10 give: A000012, A000303, A000402, A000434, A000456, A000467, A230055, A230234, A230235, A230236.
%Y T(2n+j,n+j) for j=0-10 gives: A230341, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.
%K nonn,tabl
%O 1,5
%A _N. J. A. Sloane_
%E More terms from _David W. Wilson_, Sep 07 2001
%E Better description from _Emeric Deutsch_, May 08 2004
|
