VOOZH about

URL: https://oeis.org/A076739

⇱ A076739 - OEIS

login
A076739
Number of compositions of n into Fibonacci numbers (1 counted as single Fibonacci number).
22
1, 1, 2, 4, 7, 14, 26, 49, 94, 177, 336, 637, 1206, 2288, 4335, 8216, 15574, 29515, 55943, 106030, 200959, 380889, 721906, 1368251, 2593291, 4915135, 9315811, 17656534, 33464955, 63427148, 120215370, 227847814, 431846824, 818492263, 1551313038, 2940250271, 5572744810, 10562190960
OFFSET
0,3
COMMENTS
From Gary W. Adamson, Sep 12 2008: (Start)
Equals right border of triangle A144172 and row sums with offset 1.
Equals INVERT transform of the characteristic function of the Fibonacci numbers starting with offset 1: (1, 1, 1, 0, 1, ...) (if the first "1" is retained: = 1, 1, 2, 4, 7, 14, ...). (End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..3600 (first 301 terms from T. D. Noe)
Arnold Knopfmacher and Neville Robbins, On binary and Fibonacci compositions, Annales Univ. Sci. Budapest, Sect. Comp. 22 (2003) 193-206.
FORMULA
G.f.: 1/(1-Sum_{k>1} x^Fibonacci(k)). - Vladeta Jovovic, Jun 20 2003
a(n) ~ c * d^n, where d=1.8953300920998046150867311236880760382884608526935119695..., c=0.5615834114640436146286049301387868479914202616794427372... - Vaclav Kotesovec, May 01 2014
EXAMPLE
a(4) = 7 since 3+1 = 2+2 = 2+1+1 = 1+3 = 1+2+1 = 1+1+2 = 1+1+1+1.
MAPLE
a:= proc(n) option remember; local r, f;
if n=0 then 1 else r, f:= 0, [1$2];
while f[2] <= n do r:= r+a(n-f[2]);
f:= [f[2], f[1]+f[2]]
od; r
fi
end:
seq(a(n), n=0..35); # Alois P. Heinz, Feb 20 2017
MATHEMATICA
max=40; 1/(1-Total[x^Fibonacci[Range[2, Ceiling[Sqrt[max]]+2]]]) + O[x]^max // CoefficientList[#, x]& (* Jean-François Alcover, Mar 29 2017, after Vladeta Jovovic *)
CROSSREFS
Cf. A080888.
Cf. A144172, A010056. - Gary W. Adamson, Sep 12 2008
Sequence in context: A257792 A079975 A253511 * A017996 A287154 A024502
KEYWORD
nonn,changed
AUTHOR
David W. Wilson, Jun 19 2003
STATUS
approved