A102848 Number of partitions of n into Fibonacci number of integer parts.

1, 1, 2, 3, 4, 6, 8, 10, 14, 18, 23, 29, 37, 47, 59, 74, 92, 114, 141, 173, 213, 261, 318, 387, 470, 569, 687, 827, 994, 1192, 1426, 1702, 2028, 2412, 2863, 3392, 4012, 4738, 5585, 6574, 7726, 9067, 10624, 12433, 14528, 16957, 19763, 23007, 26749, 31067, 36034

Offset: 0

Author

Lior Manor, Feb 28 2005

Keywords

• easy
• nonn

Comments

A003107 & this sequence are different sequences. A003107 gives the number of partitions in which each part of n is a Fibonacci number, this sequence gives the number of partitions in which the number of parts is a Fibonacci number. Both sequences share the same values for the first 9 values. For example A003107(4) = 4 because of the following 4 partitions of 5: (3,1), (2,2), (2,1,1), (1,1,1,1) whereas a(4) is also 4 but because of different set of partitions: (4), (3,1), (2,2), (2,1,1).

Examples

			a(5) = 6 since out of 7 possible partitions of 5 into integer parts, only 6 include a Fibonacci number of parts: (5), (4,1), (3,2), (3,1,1), (2,2,1), (1,1,1,1,1). The 7th integer partitions of 5 (2,1,1,1) is not counted since it includes 4 integer parts and 4 is not a Fibonacci number.
		

Links

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

Crossrefs

Cf. A000040, A000045, A003107.

Programs

Maple

b:= proc(n, i, t) option remember; `if`(n=0 or i=1,
      `if`((h-> issqr(h+4) or issqr(h-4))(5*(t+n)^2), 1, 0),
         b(n, i-1, t) + b(n-i, min(i, n-i), t+1))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..80);  # Alois P. Heinz, Jul 29 2017

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n == 0 || i == 1, If[IntegerQ @ Sqrt[# + 4] || IntegerQ @ Sqrt[# - 4]&[5*(t + n)^2], 1, 0], b[n, i - 1, t] + b[n - i, Min[i, n - i], t + 1]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, May 20 2018, after Alois P. Heinz *)

Formula

G.f.: 1 + Sum_{n>=2} x^Fibonacci(n)/Product_{i=1..Fibonacci(n)} (1-x^i). - Vladeta Jovovic, Mar 02 2005

Extensions

More terms from Vladeta Jovovic, Mar 02 2005

a(0)=1 prepended by Alois P. Heinz, Jul 29 2017