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

Author

Alois P. Heinz, May 26 2021

Keywords

• nonn

Examples

			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].
		

Crossrefs

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

Programs

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

Formula

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