A076739 Number of compositions of n into Fibonacci numbers (1 counted as single Fibonacci number).

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

Offset: 0

Author

David W. Wilson, Jun 19 2003

Keywords

• nonn

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)

Examples

			a(4) = 7 since 3+1 = 2+2 = 2+1+1 = 1+3 = 1+2+1 = 1+1+2 = 1+1+1+1.
		

References

• A. Knopfmacher & N. Robbins, On binary and Fibonacci compositions, Annales Univ. Sci. Budapest, Sect. Comp. 22 (2003) 193-206. - Neville Robbins, Mar 06 2010

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..3600 (first 301 terms from T. D. Noe)

Crossrefs

Cf. A080888.

Cf. A144172, A010056. - Gary W. Adamson, Sep 12 2008

Programs

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

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