A317444 Number of permutations of [n] whose lengths of increasing runs are distinct Fibonacci numbers.

1, 1, 1, 5, 6, 19, 212, 40, 757, 2170, 13546, 379084, 8978, 73195, 2702092, 772852, 38833826, 213557110, 2390871412, 150689939006, 9394670, 634504029, 4522073096, 63395566566, 5160905755362, 192831696582, 3068824154606, 289158899744046, 116561588867106

Offset: 0

Author

Alois P. Heinz, Jul 28 2018

Keywords

• nonn

Links

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

Crossrefs

Cf. A000045, A317128, A317445, A317446, A317447, A317448.

Programs

Maple

g:= (n, s)-> `if`(n in s or not
    (issqr(5*n^2+4) or issqr(5*n^2-4)), 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..30);

Mathematica

g[n_, s_] := If[MemberQ[s, n] || !(
     IntegerQ@Sqrt[5*n^2 + 4] || IntegerQ@Sqrt[5*n^2 - 4]), 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, 1, u}], 0] + Sum[b[u + j - 1, o - j, t + 1, s], {j, 1, o}]];
a[n_] := b[n, 0, 0, {}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 14 2021, after Alois P. Heinz *)