A343537 Number of partitions of the n-th Fibonacci number into a Fibonacci number of Fibonacci parts.

1, 1, 1, 2, 3, 5, 7, 16, 41, 135, 632, 4091, 37020, 478852, 8897512, 240133480, 9489055662, 552854898873, 47794151866058, 6165361571608551, 1192709563056788508, 347571453153709529743, 153189847887607116894958

Offset

0,4

Links

Table of n, a(n) for n=0..22.

Formula

a(n) = Sum_{k in {A000045}} A319394(A000045(n),k).

Example

a(5) = 5: [5], [3,2], [3,1,1], [2,2,1], [1,1,1,1,1].  Partition [2,1,1,1] is not counted because 4 (the number of parts) is not a Fibonacci number.
a(6) = 7: [8], [5,3], [5,2,1], [3,3,2], [3,2,1,1,1], [2,2,2,1,1], [1,1,1,1,1,1,1,1].
a(7) = 16: [13], [8,5], [8,3,2], [8,2,1,1,1], [5,5,3], [5,5,1,1,1], [5,3,3,1,1], [5,3,2,2,1], [5,2,2,2,2], [5,2,1,1,1,1,1,1], [3,3,3,3,1], [3,3,3,2,2], [3,3,2,1,1,1,1,1], [3,2,2,2,1,1,1,1], [2,2,2,2,2,1,1,1], [1,1,1,1,1,1,1,1,1,1,1,1,1].

Maple

f:= n-> (t-> issqr(t+4) or issqr(t-4))(5*n^2):
h:= proc(n) option remember; `if`(f(n), n, h(n-1)) end:
b:= proc(n, i, c) option remember; `if`(n=0 or i=1, `if`(
      f(c+n), 1, 0), b(n-i, h(min(n-i, i)), c+1)+b(n, h(i-1), c))
    end:
a:= n-> b((<<0|1>, <1|1>>^n)[1, 2]$2, 0):
seq(a(n), n=0..17);

Mathematica

$RecursionLimit = 10000;
f[n_] := With[{t = 5 n^2}, IntegerQ@Sqrt[t+4] || IntegerQ@Sqrt[t-4]];
h[n_] := h[n] = If[f[n], n, h[n - 1]] ;
b[n_, i_, c_] := b[n, i, c] = If[n == 0 || i == 1, If[f[c+n], 1, 0], b[n-i, h[Min[n-i, i]], c+1] + b[n, h[i-1], c]];
a[n_] := a[n] = With[{m = MatrixPower[{{0, 1}, {1, 1}}, n][[1, 2]]}, b[m, m, 0]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 17}] (* Jean-François Alcover, Sep 09 2022, after Alois P. Heinz *)

Crossrefs

Cf. A000045, A098641, A316154, A319394, A344790.

Sequence in context: A073436 A094575 A145968 * A192579 A215658 A295266

Adjacent sequences: A343534 A343535 A343536 * A343538 A343539 A343540

Keyword

nonn

Author

Alois P. Heinz, May 26 2021

Status

approved