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

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)

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

Adjacent sequences: A076736 A076737 A076738 * A076740 A076741 A076742

Keyword

nonn

Author

David W. Wilson, Jun 19 2003

Status

approved