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.

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, 99, 12, 1, 1, 13357, 19975, 5811, 1024, 137, 14, 1, 1, 99376, 189524, 60875, 11304, 1602, 181, 16, 1, 1, 822040, 1960041, 690729, 133669, 19710, 2360, 231, 18, 1, 1, 7477161

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• tabl

Comments

Row n has n terms.

Examples

			Triangle T(n,k) begins:
  1;
  1,   1;
  1,   4,   1;
  1,  16,   6,  1;
  1,  69,  41,  8,  1;
  1, 348, 293, 67, 10,  1;
  ...
T(3,2) = 4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround runs of length 2.
		

References

• F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1.

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012
• D. W. Wilson, Extended tables for A008304 and A064315

Crossrefs

Row sums give A000142. Sum_{k=1..n} k*T(n,k) = A064314(n). Cf. A064315.

Columns k=1-10 give: A000012, A000303, A000402, A000434, A000456, A000467, A230055, A230234, A230235, A230236.

T(2n+j,n+j) for j=0-10 gives: A230341, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.

Programs

Maple

b:= proc(u, o, t, k) option remember; `if`(t=k, (u+o)!,
      `if`(max(t, u)+o b(0, n, 0, k) -b(0, n, 0, k+1):
seq(seq(T(n,k), k=1..n), n=1..15);  # Alois P. Heinz, Oct 16 2013

Mathematica

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 *)
(*additional code*)
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 *)

Formula

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

T(n,k) = A122843(n,k) for k > n/2. - Alois P. Heinz, Oct 17 2013

Extensions

More terms from David W. Wilson, Sep 07 2001

Better description from Emeric Deutsch, May 08 2004