A317273 -id:A317273 - cp's OEIS frontend

A317327 Number T(n,k) of permutations of [n] with exactly k distinct lengths of increasing runs; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

1, 0, 1, 0, 2, 0, 2, 4, 0, 7, 17, 0, 2, 118, 0, 82, 436, 202, 0, 2, 3294, 1744, 0, 1456, 18164, 20700, 0, 1515, 140659, 220706, 0, 50774, 1096994, 2317340, 163692, 0, 2, 10116767, 27136103, 2663928, 0, 3052874, 94670868, 328323746, 52954112, 0, 2, 1021089326, 4317753402, 888178070

Offset: 0

Alois P. Heinz, Jul 25 2018

			T(4,1) = 7: 1234, 1324, 1423, 2314, 2413, 3412, 4321.
Triangle T(n,k) begins:
  1;
  0,       1;
  0,       2;
  0,       2,        4;
  0,       7,       17;
  0,       2,      118;
  0,      82,      436,       202;
  0,       2,     3294,      1744;
  0,    1456,    18164,     20700;
  0,    1515,   140659,    220706;
  0,   50774,  1096994,   2317340,   163692;
  0,       2, 10116767,  27136103,  2663928;
  0, 3052874, 94670868, 328323746, 52954112;
  ...

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

Columns k=0-1 give: A000007, A317329.
Row sums give A000142.
Cf. A000217, A003056, A097591, A097592, A123125, A218868, A317273.

b:= proc(u, o, t, s) option remember;
      `if`(u+o=0, x^(nops(s union {t})-1),
       add(b(u-j, o+j-1, 1, s union {t}), j=1..u)+
       add(b(u+j-1, o-j, t+1, s), j=1..o))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2, {})):
seq(T(n), n=0..16);

b[u_, o_, t_, s_] := b[u, o, t, s] = If[u + o == 0, x^(Length[s ~Union~  {t}] - 1), Sum[b[u - j, o + j - 1, 1, s ~Union~ {t}], {j, 1, u}] + Sum[b[u + j - 1, o - j, t + 1, s], {j, 1, o}]];
T[n_] := With[{p = b[n, 0, 0, {}]}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]];
T /@ Range[0, 16] // Flatten (* Jean-François Alcover, Jan 27 2021, after Alois P. Heinz *)

T(n*(n+1)/2,n) = A317273(n).

Sum_{k=0..floor((sqrt(1+8*n)-1)/2)} k * T(n,k) = A317328(n).

A317165 Number of permutations of [n*(n+1)/2] with distinct lengths of increasing runs.

Original entry on oeis.org

1, 1, 5, 241, 188743, 2734858573, 892173483721887, 7469920269852025033699, 1841449549508718383891930251607, 14973026148724796464136435753195418043885, 4467880642339303169146446437381463615730321314015457, 53810913396105573079543194840166969124601447333276658546225661505

Offset: 0

Alois P. Heinz, Jul 23 2018

nonn

Cf. A000217, A246292, A317130, A317166, A317273.

g:= (n, s)-> `if`(n in s, 0, 1):
b:= proc(u, o, t, s) option remember; `if`(u+o=0, g(t, s),
      `if`(g(t, s)=1, add(b(u-j, o+j-1, 1, s union {t})
       , j=1..u), 0)+ add(b(u+j-1, o-j, t+1, s), j=1..o))
    end:
a:= n-> b(n*(n+1)/2, 0$2, {}):
seq(a(n), n=0..8);

g[n_, s_] := If[MemberQ[s, n], 0, 1];
b[u_, o_, t_, s_] := b[u, o, t, s] = If[u + o == 0, g[t, s],
     If[g[t, s] == 1, Sum[b[u - j, o + j - 1, 1, s ~Union~ {t}],
     {j, u}], 0] + Sum[b[u + j - 1, o - j, t + 1, s], {j, o}]];
a[n_] := b[n(n+1)/2, 0, 0, {}];
Table[a[n], {n, 0, 8}] (* Jean-François Alcover, Sep 01 2021, after Alois P. Heinz *)

a(n) = A317166(A000217(n)).

a(n) >= A317273(n).

cp's OEIS Frontend

A317327 Number T(n,k) of permutations of [n] with exactly k distinct lengths of increasing runs; triangle T(n,k), n>=0, 0<=k<=A003056(n), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula