A230341 -id:A230341 - 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.

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

N. J. A. Sloane

Row n has n terms.

			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.

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

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

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.

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

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 *)

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

More terms from David W. Wilson, Sep 07 2001

Better description from Emeric Deutsch, May 08 2004

A267433 Number of permutations of [2n] with longest increasing subsequence of length n.

Original entry on oeis.org

1, 1, 13, 381, 17557, 1100902, 87116283, 8312317976, 927716186325, 118504614869214, 17044414451764396, 2725298085020712539, 479491040778079234419, 92050364310704637832186, 19146538134094625864605786, 4289203871330156652985437480

Offset: 0

Alois P. Heinz, Jan 15 2016

nonn

			a(2) = 13: 1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312.

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..74 (terms 0..55 from Alois P. Heinz)
Mathematics StackExchange, Reference or proof for number of permutations of [2n] with longest increasing subsequence of length n, answered by David Moews, Sep 22 2023.

Cf. A047874, A126065, A230341, A267436.

h:= proc(l) local n; n:= nops(l); add(i, i=l)! /mul(mul(1+l[i]-j+
    add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n) end:
g:= (n, i, l)-> `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
                add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i))):
a:= n-> g(n$2, [n]):
seq(a(n), n=0..20);

h[l_] := With[{n = Length[l]}, Total[l]! / Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] >= j, 1, 0], { k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]];
g[n_, i_, l_] := g[n, i, l] = If[n==0 || i==1, h[Join[l, Table[1, {n}]]]^2, If[i<1, 0, Sum[g[n-i*j, i-1, Join[l, Table[i, {j}]]], {j, 0, n/i}]]];
a[n_] := g[n, n, {n}];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 29 2017, translated from Maple *)

a(n) = A047874(2n,n) = A126065(2n,n).

a(n) ~ 16^n * (n-1)! / (Pi * exp(2)). - Vaclav Kotesovec, Mar 27 2016

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions