A317166 Number of permutations of [n] with distinct lengths of increasing runs.

1, 1, 1, 5, 7, 27, 241, 505, 1975, 10241, 188743, 460545, 2323679, 10836141, 85023209, 2734858573, 8010483015, 45714797671, 243112435345, 1632532938001, 15831051353773, 892173483721887, 2978105991739613, 19855526019022967, 113487352591708591

Offset

0,4

Links

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

Formula

a(A000217(n)) = A317165(n).

Maple

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, 0$2, {}):
seq(a(n), n=0..24);

Mathematica

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, 0, 0, {}];
Table[a[n], {n, 0, 24}] (* Jean-François Alcover, Sep 01 2021, after Alois P. Heinz *)

Crossrefs

Cf. A000217, A007838, A317165.

Sequence in context: A029668 A144392 A268701 * A126888 A358582 A185302

Adjacent sequences: A317163 A317164 A317165 * A317167 A317168 A317169

Keyword

nonn

Author

Alois P. Heinz, Jul 23 2018

Status

approved