login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A172491
Number of partitions of n into consecutive initial Fibonacci numbers.
1
1, 2, 3, 5, 7, 10, 14, 19, 25, 33, 42, 54, 68, 85, 105, 129, 157, 190, 228, 273, 324, 384, 452, 530, 619, 720, 834, 964, 1109, 1273, 1456, 1661, 1890, 2145, 2428, 2743, 3091, 3477, 3902, 4371, 4887, 5454, 6076, 6758, 7503, 8319, 9208, 10178, 11234, 12382
OFFSET
1,2
COMMENTS
The Fibonacci sequence starts with two 1's, that are to be considered distinct (see illustration).
EXAMPLE
The first (positive) Fibonacci numbers are: 1, 1, 2, 3, 5, 8...
The number 5 can be partitioned into:
- 1 consecutive initial Fibonacci number in 1 way: 5*1,
- 2 consecutive initial Fibonacci numbers in 4 ways: 4*1 + 1*1, 3*1 + 2*1, 2*1 + 3*1, 1*1 + 4*1,
- 3 consecutive initial Fibonacci numbers in 2 way: 2*1 + 1*1 + 1*2, 1*1 + 2*1 + 1*2.
Hence, a(5) = 1+4+2 = 7.
MAPLE
with(combinat):
b:= proc(n, i) option remember; local f; f:= fibonacci(i);
`if`(n=0 or i=1, 1, `if`(i<1 , 0, `if`(i=2, n+1,
b(n, i-1)+`if`(f>n, 0, b(n-f, i)))))
end:
a:= proc(n) local i, m, s; m, s:= n, 0;
for i do m:= m-fibonacci(i);
if m<0 then break fi;
s:= s+ b(m, i)
od; s
end:
seq(a(n), n=1..100); # Alois P. Heinz, Apr 29 2013
MATHEMATICA
b[n_, i_] := b[n, i] = Module[{f = Fibonacci[i]}, If[n==0 || i==1, 1, If[i < 1, 0, If[i==2, n + 1, b[n, i - 1] + If[f>n, 0, b[n - f, i]]]]]];
a[n_] := Module[{i, m = n, s = 0}, 0; For[i = 1, True, i++, m = m - Fibonacci[i]; If[m<0, Break[]]; s = s + b[m, i]]; s];
Array[a, 100] (* Jean-François Alcover, Nov 20 2020, after Alois P. Heinz *)
PROG
(PARI)
a(n) = {
my(s=0, P=1, k=1, x='x);
while(P!=0,
s=s+polcoeff(P, n);
P=(P*sum(z=1, n/fibonacci(k), x^(fibonacci(k)*z)))+O(x^(n+1));
k=k+1
);
return(s); } /* Paul Tek, Apr 28 2013 */
CROSSREFS
Cf. A000045 (Fibonacci numbers).
Cf. A000009.
Sequence in context: A304712 A175842 A008581 * A036469 A238658 A116480
KEYWORD
nonn
AUTHOR
Frank Schwellinger (nummer_eins(AT)web.de), Feb 05 2010
EXTENSIONS
Corrected and extended by Paul Tek, Apr 28 2013
STATUS
approved