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

%I #36 Oct 30 2023 08:01:19

%S 1,1,2,4,7,14,26,49,94,177,336,637,1206,2288,4335,8216,15574,29515,

%T 55943,106030,200959,380889,721906,1368251,2593291,4915135,9315811,

%U 17656534,33464955,63427148,120215370,227847814,431846824,818492263

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

%C From _Gary W. Adamson_, Sep 12 2008: (Start)

%C Equals right border of triangle A144172 and row sums with offset 1.

%C 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)

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

%H Alois P. Heinz, <a href="/A076739/b076739.txt">Table of n, a(n) for n = 0..3600</a> (first 301 terms from T. D. Noe)

%F G.f.: 1/(1-Sum_{k>1} x^Fibonacci(k)). - _Vladeta Jovovic_, Jun 20 2003

%F a(n) ~ c * d^n, where d=1.8953300920998046150867311236880760382884608526935119695..., c=0.5615834114640436146286049301387868479914202616794427372... - _Vaclav Kotesovec_, May 01 2014

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

%p a:= proc(n) option remember; local r, f;

%p if n=0 then 1 else r, f:= 0, [1$2];

%p while f[2] <= n do r:= r+a(n-f[2]);

%p f:= [f[2], f[1]+f[2]]

%p od; r

%p fi

%p end:

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Feb 20 2017

%t 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_ *)

%Y Cf. A080888.

%Y Cf. A144172, A010056. - _Gary W. Adamson_, Sep 12 2008

%K nonn

%O 0,3

%A _David W. Wilson_, Jun 19 2003