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,4

Links

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

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 *)

Crossrefs

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

Sequence in context: A056509 A129722 A133608 * A072577 A231182 A231181

Adjacent sequences: A317441 A317442 A317443 * A317445 A317446 A317447

Keyword

nonn

Author

Alois P. Heinz, Jul 28 2018

Status

approved