A122843 -id:A122843 - 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

A229001 Total sum A(n,k) of the k-th powers of lengths of ascending runs in all permutations of [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 3, 0, 1, 4, 12, 0, 1, 6, 18, 60, 0, 1, 10, 32, 96, 360, 0, 1, 18, 66, 186, 600, 2520, 0, 1, 34, 152, 426, 1222, 4320, 20160, 0, 1, 66, 378, 1110, 2964, 9086, 35280, 181440, 0, 1, 130, 992, 3186, 8254, 22818, 75882, 322560, 1814400

Offset: 0

Alois P. Heinz, Sep 10 2013

			A(3,2) = 32 = 9+5+5+5+5+3 = 3^2+4*(2^2+1^2)+3*1^2: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).
Square array A(n,k) begins:
:    0,    0,    0,     0,     0,      0,      0, ...
:    1,    1,    1,     1,     1,      1,      1, ...
:    3,    4,    6,    10,    18,     34,     66, ...
:   12,   18,   32,    66,   152,    378,    992, ...
:   60,   96,  186,   426,  1110,   3186,   9846, ...
:  360,  600, 1222,  2964,  8254,  25620,  86782, ...
: 2520, 4320, 9086, 22818, 66050, 214410, 765506, ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A001710(n+1) for n>0, A001563, A228959, A229003, A228994, A228995, A228996, A228997, A228998, A228999, A229000.
Rows n=0-2 give: A000004, A000012, A052548.
Main diagonal gives: A229002.

A:= (n, k)-> add(`if`(n=t, 1, n!/(t+1)!*(t*(n-t+1)+1
             -((t+1)*(n-t)+1)/(t+2)))*t^k, t=1..n):
seq(seq(A(n, d-n), n=0..d), d=0..12);

A[n_, k_] := Sum[If[n == t, 1, n!/(t + 1)!*(t*(n - t + 1) + 1 - ((t + 1)*(n - t) + 1)/(t + 2))]* t^k, {t, 1, n}]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

A(n,k) = Sum_{t=1..n} t^k * A122843(n,t).

For fixed k, A(n,k) ~ n! * n * sum(t>=1, t^k*(t^2+t-1)/(t+2)!) = n! * n * ((Bell(k) - Bell(k+1) + sum(j=0..k, (-1)^j*(2^j*((2*k-j+1)/(j+1))-1) *Bell(k-j)*C(k,j)))*exp(1) - (-1)^k*(2^k-1)), where Bell(k) are Bell numbers A000110. - Vaclav Kotesovec, Sep 12 2013

A230251 Number of permutations of [2n+1] in which the longest increasing run has length n+1.

Original entry on oeis.org

1, 4, 41, 602, 11304, 257400, 6881160, 211170960, 7315701120, 282398538240, 12019910112000, 559278036979200, 28242651241728000, 1538394175334016000, 89912239244860032000, 5612575361948755200000, 372687441873534627840000, 26231028469670851706880000

Offset: 0

Alois P. Heinz, Oct 13 2013

nonn

Also the number of ascending runs of length n+1 in the permutations of [2n+1].

Alois P. Heinz, Table of n, a(n) for n = 0..300

Diagonal of A008304, A122843.

a:= proc(n) option remember; `if`(n<2, 1+3*n,
      2*n*(2*n+1)*(n^3+4*n^2+6*n+5)*a(n-1)/((n+3)*(n^3+n^2+n+2)))
    end:
seq(a(n), n=0..25);

Flatten[{1,Table[(5+6*n+4*n^2+n^3)*(2*n+1)!/(n+3)!,{n,1,20}]}] (* Vaclav Kotesovec, Oct 15 2013 *)

a(n) = A008304(2*n+1,n+1) = A122843(2*n+1,n+1).

For n>0, a(n) = (5+6*n+4*n^2+n^3)*(2*n+1)!/(n+3)!. - Vaclav Kotesovec, Oct 15 2013

A230342 Number of permutations of [2n+2] in which the longest increasing run has length n+2.

Original entry on oeis.org

1, 6, 67, 1024, 19710, 456720, 12372360, 383685120, 13406178240, 521194867200, 22318001798400, 1043827513344000, 52949040240096000, 2895555891900672000, 169823181579891840000, 10633812541718446080000, 708077586604965857280000, 49962245750984840232960000

Offset: 0

Alois P. Heinz, Oct 16 2013

nonn

Also the number of ascending runs of length n+2 in the permutations of [2n+2].

Alois P. Heinz, Table of n, a(n) for n = 0..300

A diagonal of A008304, A122843.

a:= proc(n) option remember; `if`(n<2, 1+5*n, 2*(n+1)*(2*n+1)*
      (n^3+6*n^2+12*n+11)*a(n-1)/((n+4)*(n^3+3*n^2+3*n+4)))
    end:
seq(a(n), n=0..25);

a(n) = (n^3+6*n^2+12*n+11)*(2*n+2)!/(n+4)! for n>0, a(0) = 1.

a(n) = A008304(2*n+2,n+2) = A122843(2*n+2,n+2).

A230343 Number of permutations of [2n+3] in which the longest increasing run has length n+3.

Original entry on oeis.org

1, 8, 99, 1602, 32010, 761904, 21064680, 663848640, 23500653120, 923616691200, 39914540709120, 1881558401184000, 96096062174112000, 5286518167746816000, 311689569962010240000, 19608741674518284288000, 1311187373310480906240000, 92868537238628772741120000

Offset: 0

Alois P. Heinz, Oct 16 2013

nonn

Also the number of ascending runs of length n+3 in the permutations of [2n+3].

Alois P. Heinz, Table of n, a(n) for n = 0..300

A diagonal of A008304, A122843.

a:= proc(n) option remember; `if`(n<2, 1+7*n, 2*(2*n+3)*(n+1)*
      (n^3+8*n^2+20*n+19)*a(n-1)/((n+5)*(n^3+5*n^2+7*n+6)))
    end:
seq(a(n), n=0..25);

a(n) = (n^3+8*n^2+20*n+19)*(2*n+3)!/(n+5)! for n>0, a(0) = 1.

a(n) = A008304(2*n+3,n+3) = A122843(2*n+3,n+3).

A230344 Number of permutations of [2n+4] in which the longest increasing run has length n+4.

Original entry on oeis.org

1, 10, 137, 2360, 49236, 1209936, 34288800, 1102187520, 39656131200, 1579837754880, 69064610186880, 3288126441600000, 169388400557376000, 9389435419203840000, 557323393281887232000, 35272416767753797632000, 2371290445442664345600000

Offset: 0

Alois P. Heinz, Oct 16 2013

nonn

Also the number of ascending runs of length n+4 in the permutations of [2n+4].

Alois P. Heinz, Table of n, a(n) for n = 0..300

A diagonal of A008304, A122843.

a:= proc(n) option remember; `if`(n<2, 1+9*n, 2*(2*n+3)*(n+2)*
      (n^3+10*n^2+30*n+29)*a(n-1)/((n+6)*(n^3+7*n^2+13*n+8)))
    end:
seq(a(n), n=0..25);

a(n) = (n^3+10*n^2+30*n+29)*(2*n+4)!/(n+6)! for n>0, a(0) = 1.

a(n) = A008304(2*n+4,n+4) = A122843(2*n+4,n+4).

A230345 Number of permutations of [2n+5] in which the longest increasing run has length n+5.

Original entry on oeis.org

1, 12, 181, 3322, 72540, 1845480, 53749920, 1766525760, 64739122560, 2619453513600, 116043825744000, 5588681114016000, 290812286052288000, 16263827918642304000, 973009916329651200000, 62017234027123415040000, 4195886889891954216960000

Offset: 0

Alois P. Heinz, Oct 16 2013

nonn

Also the number of ascending runs of length n+5 in the permutations of [2n+5].

Alois P. Heinz, Table of n, a(n) for n = 0..300

A diagonal of A008304, A122843.

a:= proc(n) option remember; `if`(n<2, 1+11*n, 2*(2*n+5)*(n+2)*
      (n^3+12*n^2+42*n+41)*a(n-1)/((n+7)*(n^3+9*n^2+21*n+10)))
    end:
seq(a(n), n=0..25);

a(n) = (n^3+12*n^2+42*n+41)*(2*n+5)!/(n+7)! for n>0, a(0) = 1.

a(n) = A008304(2*n+5,n+5) = A122843(2*n+5,n+5).

A230346 Number of permutations of [2n+6] in which the longest increasing run has length n+6.

Original entry on oeis.org

1, 14, 231, 4512, 103194, 2721600, 81591840, 2746068480, 102661518960, 4224849995520, 189917647920000, 9263565222912000, 487461283781472000, 27533206366009344000, 1661865400404937728000, 106768864984887705600000, 7275718977990226283520000

Offset: 0

Alois P. Heinz, Oct 16 2013

nonn

Also the number of ascending runs of length n+6 in the permutations of [2n+6].

Alois P. Heinz, Table of n, a(n) for n = 0..300

A diagonal of A008304, A122843.

a:= proc(n) option remember; `if`(n<2, 1+13*n, 2*(2*n+5)*(n+5)*
      (n+3)*(n^2+9*n+11)*a(n-1)/((n+4)*(n+8)*(n^2+7*n+3)))
    end:
seq(a(n), n=0..25);

a(n) = (n+5)*(n^2+9*n+11)*(2*n+6)!/(n+8)! for n>0, a(0) = 1.

a(n) = A008304(2*n+6,n+6) = A122843(2*n+6,n+6).

A230347 Number of permutations of [2n+7] in which the longest increasing run has length n+7.

Original entry on oeis.org

1, 16, 287, 5954, 142590, 3900480, 120466080, 4156079760, 158664456720, 6647965632000, 303540020784000, 15009431909472000, 799414492260384000, 45641465547245568000, 2781538377619921920000, 180263592116387619840000, 12381113998069012804608000

Offset: 0

Alois P. Heinz, Oct 16 2013

nonn

Also the number of ascending runs of length n+7 in the permutations of [2n+7].

Alois P. Heinz, Table of n, a(n) for n = 0..300

A diagonal of A008304, A122843.

a:= proc(n) option remember; `if`(n<2, 1+15*n, 2*(n+3)*(2*n+7)*
      (n^3+16*n^2+72*n+71)*a(n-1)/((n+9)*(n^3+13*n^2+43*n+14)))
    end:
seq(a(n), n=0..25);

a(n) = (n^3+16*n^2+72*n+71)*(2*n+7)!/(n+9)! for n>0, a(0) = 1.

a(n) = A008304(2*n+7,n+7) = A122843(2*n+7,n+7).

A230348 Number of permutations of [2n+8] in which the longest increasing run has length n+8.

Original entry on oeis.org

1, 18, 349, 7672, 192240, 5454144, 173606040, 6143195520, 239656253760, 10231052832000, 474832908950400, 23819880180096000, 1284985968634368000, 74207855717259264000, 4569213387521502720000, 298885288012537901875200, 20702796608070625112064000

Offset: 0

Alois P. Heinz, Oct 16 2013

nonn

Also the number of ascending runs of length n+8 in the permutations of [2n+8].

Alois P. Heinz, Table of n, a(n) for n = 0..300

A diagonal of A008304, A122843.

a:= proc(n) option remember; `if`(n<2, 1+17*n, 2*(n+4)*(2*n+7)*
      (n^3+18*n^2+90*n+89)*a(n-1)/((n+10)*(n^3+15*n^2+57*n+16)))
    end:
seq(a(n), n=0..25);

a(n) = (n^3+18*n^2+90*n+89)*(2*n+8)!/(n+10)! for n>0, a(0) = 1.

a(n) = A008304(2*n+8,n+8) = A122843(2*n+8,n+8).

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

A229001 Total sum A(n,k) of the k-th powers of lengths of ascending runs in all permutations of [n]; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A230251 Number of permutations of [2n+1] in which the longest increasing run has length n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A230342 Number of permutations of [2n+2] in which the longest increasing run has length n+2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A230343 Number of permutations of [2n+3] in which the longest increasing run has length n+3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A230344 Number of permutations of [2n+4] in which the longest increasing run has length n+4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A230345 Number of permutations of [2n+5] in which the longest increasing run has length n+5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A230346 Number of permutations of [2n+6] in which the longest increasing run has length n+6.

Views

Author