A008304 -id:A008304 - cp's OEIS frontend

A122843 Triangle read by rows: T(n,k) = the number of ascending runs of length k in the permutations of [n] for k <= n.

1, 2, 1, 7, 4, 1, 32, 21, 6, 1, 180, 130, 41, 8, 1, 1200, 930, 312, 67, 10, 1, 9240, 7560, 2646, 602, 99, 12, 1, 80640, 68880, 24864, 5880, 1024, 137, 14, 1, 786240, 695520, 257040, 62496, 11304, 1602, 181, 16, 1, 8467200, 7711200, 2903040, 720720, 133920, 19710, 2360, 231, 18, 1

Offset: 1

David Scambler, Sep 13 2006

Also T(n,k) = number of rising sequences of length k among all permutations. E.g., T(4,3)=6 because in the 24 permutations of n=4, there are 6 rising sequences of length 3: {1,2,3} in {1,2,4,3}, {1,2,3} in {1,4,2,3}, {2,3,4} in {2,1,3,4}, {2,3,4} in {2,3,1,4}, {2,3,4} in {2,3,4,1}, {1,2,3} in {4,1,2,3}. - Harlan J. Brothers, Jul 23 2008
Further comments and formulas from Harlan J. Brothers, Jul 23 2008: (Start)
The n-th row sums to (n+1)!/2, consistent with total count implied by the n-th row in the table of Eulerians, A008292.
Generating this triangle through use of the diagonal polynomials allows one to produce an arbitrary number of "imaginary" columns corresponding to runs of length 0, -1, -2, etc. These columns match A001286, A001048 and the factorial function respectively.
As n->inf, there is a limiting value for the count of each length expressed as a fraction of all rising sequences in the permutations of n. The numerators of the set of limit fractions are given by A028387 and the denominators by A001710.
As a table of diagonals d[i]:
d[1][n] = 1
d[2][n] = 2n
d[3][n] = 3n^2 + 5n - 1
d[4][n] = 4n^3 + 18n^2 + 16n - 6
d[5][n] = 5n^4 + 42n^3 + 106n^2 + 63n - 36
d[6][n] = 6n^5 + 80n^4 + 374n^3 + 688n^2 + 292n - 240
T[n,k] = n!(n(k^2 + k - 1) - k(k^2 - 4) + 1)/(k+2)! + floor(k/n)(1/(k(k+3)+2)), 0 < k <= n.  (End)

			T(3,2) = 4: There are 4 ascending runs of length 2 in the permutations of [3], namely 13 in 132 and in 213, 23 in 231, 12 in 312.
Triangle begins:
    1;
    2,   1;
    7,   4,   1;
   32,  21,   6,   1;
  180, 130,  41,   8,   1;
  ...

C. M. Grinstead and J. L. Snell, Introduction to Probability, American Mathematical Society, 1997, pp.120-131.
Donald E. Knuth. The Art of Computer Programming. Vol. 2. Addison-Wesley, Reading, MA, 1998. Seminumerical algorithms, Third edition, Section 3.3.2, p.67.

Alois P. Heinz, Rows n = 1..141, flattened
Persi Diaconis, Mathematical developments from the analysis of riffle shuffling, p.4.
Francis Edward Su, Rising Sequences in Card Shuffling

Cf. A008292, A097900, A001286, A001048, A000142, A028387, A001710.
Cf. A122844, A001710, A006157, A005460.
T(2n+j,n+j) for j = 0..10 gives A230382, A230251, A230342, A230343, A230344, A230345, A230346, A230347, A230348, A230349, A230350.

T:= (n, k)-> `if`(n=k, 1, n!/(k+1)!*(k*(n-k+1)+1
             -((k+1)*(n-k)+1)/(k+2))):
seq(seq(T(n,k), k=1..n), n=1..10);  # Alois P. Heinz, Sep 11 2013

Table[n!((n(k(k+1)-1)-k(k-2)(k+2)+1))/(k+2)!+Floor[k/n]1/(k(k+3)+2),{n,1,10},{k,1,n}]//TableForm (* Harlan J. Brothers, Jul 23 2008 *)

T(n,k) = n!(n(k(k+1)-1) - k(k-2)(k+2) + 1)/(k+2)! for 0 < k < n; T(n,n) = 1; T(n,k) = A122844(n,k) - A122844(n,k+1).

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

A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements.

Original entry on oeis.org

1, 3, 12, 58, 335, 2261, 17465, 152020, 1473057, 15730705, 183571817, 2324298010, 31737207034, 464904410985, 7272666016725, 121007866402968, 2133917906948645, 39756493513248129, 780313261631908137, 16093326774432620874, 347958942706716524974

Offset: 1

N. J. A. Sloane and Richard Stanley

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..80
R. M. Baer and P. Brock, Natural sorting over permutation spaces, Math. Comp. 22 1968 385-410.
R. P. Stanley, Letter to N. J. A. Sloane, c. 1991
A. M. Vershik and S. V. Kerov, Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux, Doklady Akademii Nauk SSSR, 1977, Volume 233, Number 6, Pages 1024-1027. In Russian.
Wikipedia, Longest increasing subsequence

Cf. A008304 (which is concerned with runs of adjacent elements).
Row sums of A214152.
Cf. A047874, A321273, A321274.

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-> add(k* (g(n-k, k, [k])), k=1..n):
seq(a(n), n=1..22);  # Alois P. Heinz, Jul 05 2012

h[l_List] := Module[{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_] := If[n == 0 || i == 1, h[Join[l, Array[1&, n]]]^2, If[i<1, 0, Sum[g[n-i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; a[n_] := Sum[k*g[n-k, k, {k}], {k, 1, n}]; Table[a[n], {n, 1, 22}] (* Jean-François Alcover, Feb 11 2014, after Alois P. Heinz *)

From Alois P. Heinz, Nov 04 2018: (Start)
a(n) = Sum_{k=1..n} k * A047874(n,k).
A321274(n) < a(n) < A321273(n) for n > 1. (End)
A theorem of Vershik and Kerov (1977) implies that a(n) ~ 2 * sqrt(n) * n!. - Ludovic Schwob, Apr 04 2024

Corrected a(13) and extended beyond a(16) by Alois P. Heinz, Jul 05 2012

A064315 Triangle of number of permutations by length of shortest ascending run.

Original entry on oeis.org

1, 1, 1, 5, 0, 1, 18, 5, 0, 1, 101, 18, 0, 0, 1, 611, 89, 19, 0, 0, 1, 4452, 519, 68, 0, 0, 0, 1, 36287, 3853, 110, 69, 0, 0, 0, 1, 333395, 27555, 1679, 250, 0, 0, 0, 0, 1, 3382758, 233431, 11941, 418, 251, 0, 0, 0, 0, 1, 37688597, 2167152, 59470, 658, 922, 0, 0, 0, 0, 0, 1

Offset: 1

David W. Wilson, Sep 07 2001

			Sequence (1, 3, 2, 5, 4) has ascending runs (1, 3), (2, 5), (4), the shortest is length 1. Of all permutations of (1, 2, 3, 4, 5), T(5,1) = 101 have shortest ascending run of length 1.
Triangle T(n,k) begins:
      1;
      1,    1;
      5,    0,   1;
     18,    5,   0,  1;
    101,   18,   0,  0,  1;
    611,   89,  19,  0,  0, 1;
   4452,  519,  68,  0,  0, 0, 1,
  36287, 3853, 110, 69,  0, 0, 0, 1;
  ...

Alois P. Heinz, Rows n = 1..100, flattened
D. W. Wilson, Extended tables for A008304 and A064315

Row sums give: A000142.
Columns k=1-10 give: A228614, A185652, A228670, A228671, A228672, A228673, A228674, A228675, A228676, A228677.
Cf. A030662, A064316.

A:= proc(n, k) option remember; local b; b:=
      proc(u, o, t) option remember; `if`(t+o<=k, (u+o)!,
        add(b(u+i-1, o-i, min(k, t)+1), i=1..o)+
        `if`(t<=k, u*(u+o-1)!, add(b(u-i, o+i-1, 1), i=1..u)))
      end: forget(b):
      add(b(j-1, n-j, 1), j=1..n)
    end:
T:= (n, k)-> A(n, k) -A(n, k-1):
seq(seq(T(n, k), k=1..n), n=1..12); # Alois P. Heinz, Aug 29 2013

A[n_, k_] := A[n, k] = Module[{b}, b[u_, o_, t_] := b[u, o, t] = If[t+o <= k, (u+o)!, Sum[b[u+i-1, o-i, Min[k, t]+1], {i, 1, o}] + If[t <= k, u*(u+o-1)!, Sum[ b[u-i, o+i-1, 1], {i, 1, u}]]]; Sum[b[j-1, n-j, 1], {j, 1, n}]]; T[n_, k_] := A[n, k] - A[n, k-1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)

T(2*n,n) = binomial(2*n,n)-1 = A030662(n).

Sum_{k=1..n} k * T(n,k) = A064316(n).

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

Original entry on oeis.org

0, 1, 4, 16, 69, 348, 2016, 13357, 99376, 822040, 7477161, 74207208, 797771520, 9236662345, 114579019468, 1516103040832, 21314681315997, 317288088082404, 4985505271920096, 82459612672301845, 1432064398910663704, 26054771465540507272

Offset: 1

N. J. A. Sloane

nonn

			a(3)=4 because we have (13)2, 2(13), (23)1, 3(12), where the parentheses surround increasing 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.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..464 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded runs length, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012

Column 2 of A008304. Other columns: A000402, A000434, A000456, A000467, A230055.
Cf. A001250, A001251, A001252, A001253, A010026, A211318.
Equals 1 less than A049774. - Greg Dresden, Feb 22 2020

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];
a[n_] := T[n, 2];
Array[a, 30] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

Better description from Emeric Deutsch, May 08 2004

Edited and extended by Max Alekseyev, May 20 2012

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

Original entry on oeis.org

0, 0, 1, 6, 41, 293, 2309, 19975, 189524, 1960041, 21993884, 266361634, 3465832370, 48245601976, 715756932697, 11277786883720, 188135296651083, 3313338641692957, 61444453534759589, 1196988740015236617, 24442368179977776766, 522124104504306695929

Offset: 1

N. J. A. Sloane

nonn

			a(4)=6 because we have (124)3, (134)2, (234)1, 4(123), 3(124) and 2(134), where the parentheses surround increasing runs of length 3.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261, Table 7.4.1. (Values for n>=16 are incorrect.)
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..452 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded runs length, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012

Column 3 of A008304. Other columns: A000303, A000434, A000456, A000467.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

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];
a[n_] := T[n, 3];
Array[a, 30] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

Better description from Emeric Deutsch, May 08 2004

Terms a(16), a(17) are corrected and further terms added by Max Alekseyev, May 20 2012

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

Original entry on oeis.org

0, 0, 0, 1, 8, 67, 602, 5811, 60875, 690729, 8457285, 111323149, 1569068565, 23592426102, 377105857043, 6387313185576, 114303481217657, 2155348564847332, 42719058006864690, 887953677898186108, 19316200230609433690, 438920223893512987430

Offset: 1

N. J. A. Sloane

nonn

			a(5)=8 because we have (1235)4, (1245)3, (1345)2, (2345)1, 5(1234), 4(1235), 3(1245) and 2(1345), where the parentheses surround increasing runs of length 4.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261. (Values for n>=16 are incorrect.)
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded runs length, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013. - From _N. J. A. Sloane_, Oct 23 2012

Column 4 of A008304. Other columns: A000303, A000402, A000456, A000467.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

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];
a[n_] := T[n, 4];
Array[a, 30] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

Better description from Emeric Deutsch, May 08 2004

Terms a(16)-a(18) corrected and further terms added by Max Alekseyev, May 20 2012

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

Original entry on oeis.org

0, 0, 0, 0, 1, 10, 99, 1024, 11304, 133669, 1695429, 23023811, 333840443, 5153118154, 84426592621, 1463941342191, 26793750988542, 516319125748337, 10451197169218523, 221738082618710329, 4921234092461339819, 114041894068935641488

Offset: 1

N. J. A. Sloane

nonn

			a(6)=10 because we have (12346)5, (12356)4, (12456)3, (13456)2, (23456)1, 6(12345), 5(12346), 4(12356), 3(12456) and 2(13456), where the parentheses surround increasing runs of length 5.

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581 [math.CO], 2012-2013.

Column 5 of A008304. Other columns: A000303, A000402, A000434, A000467.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

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]; a[n_] := T[n, 5]; Array[a, 25] (* Jean-François Alcover, Feb 08 2016, after Alois P. Heinz in A008304 *)

Better description from Emeric Deutsch, May 08 2004

Edited and extended by Max Alekseyev, May 20 2012

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

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 12, 137, 1602, 19710, 257400, 3574957, 52785901, 827242933, 13730434111, 240806565782, 4452251786946, 86585391630673, 1767406549387381, 37790452850585180, 844817788372455779, 19711244788916894489, 479203883157602851294

Offset: 1

N. J. A. Sloane

nonn

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 261.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..450 (first 100 terms from Max Alekseyev)
Max A. Alekseyev, On the number of permutations with bounded run lengths, arXiv preprint arXiv:1205.4581 [math.CO], 2012.

Column 6 of A008304. Other columns: A000303, A000402, A000434, A000456.

Cf. A001250, A001251, A001252, A001253, A010026, A211318.

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]; a[n_] := T[n, 6]; Array[a, 23] (* Jean-François Alcover, Feb 08 2016, after Alois P. Heinz in A008304 *)

Edited and extended by Max Alekseyev, May 20 2012

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

Original entry on oeis.org

1, 14, 181, 2360, 32010, 456720, 6881160, 109546009, 1841298059, 32629877967, 608572228291, 11923667699474, 244964063143590, 5267496652725480, 118348438201424761, 2773714509551524351, 67705791536824698266, 1718769199589362743761, 45314525515737783596251

Offset: 7

Alois P. Heinz, Oct 07 2013

nonn

			a(7) = 1: 1234567.
a(8) = 14: 12345687, 12345786, 12346785, 12356784, 12456783, 13456782, 21345678, 23456781, 31245678, 41235678, 51234678, 61234578, 71234568, 81234567.

Alois P. Heinz, Table of n, a(n) for n = 7..200

Column k=7 of A008304.

b:= proc(u, o, t, k) option remember; `if`(u+o=0, 1,
      `if`(t b(n, 0, 0, 7)-b(n, 0, 0, 6):
seq(a(n), n=7..30);

b[u_, o_, t_, k_] := b[u, o, t, k] = If[u + o == 0, 1, If[t < k - 1, Sum[b[u + j - 1, o - j, t + 1, k], {j, 1, o}], 0] + Sum[b[u - j, o + j - 1, 0, k], {j, 1, u}]];
a[n_] := b[n, 0, 0, 7] - b[n, 0, 0, 6];
Table[a[n], {n, 7, 30}] (* Jean-François Alcover, Jul 19 2018, after Alois P. Heinz *)

a(n) = A230051(n) - A177553(n).

E.g.f.: 1/Sum_{n>=0} (8*n+1-x)*x^(8*n)/(8*n+1)! - 1/Sum_{n>=0} (7*n+1-x)*x^(7*n)/(7*n+1)!.

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

cp's OEIS Frontend

A122843 Triangle read by rows: T(n,k) = the number of ascending runs of length k in the permutations of [n] for k <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A003316 Sum of lengths of longest increasing subsequences of all permutations of n elements.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A064315 Triangle of number of permutations by length of shortest ascending run.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

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

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica