A000121 Number of representations of n as a sum of Fibonacci numbers (1 is allowed twice as a part).

1, 2, 2, 3, 3, 3, 4, 3, 4, 5, 4, 5, 4, 4, 6, 5, 6, 6, 5, 6, 4, 5, 7, 6, 8, 7, 6, 8, 6, 7, 8, 6, 7, 5, 5, 8, 7, 9, 9, 8, 10, 7, 8, 10, 8, 10, 8, 7, 10, 8, 9, 9, 7, 8, 5, 6, 9, 8, 11, 10, 9, 12, 9, 11, 13, 10, 12, 9, 8, 12, 10, 12, 12, 10, 12, 8, 9, 12, 10, 13, 11, 9, 12, 9, 10, 11, 8, 9, 6, 6, 10, 9

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Number of partitions into distinct Fibonacci parts (1 counted as two distinct Fibonacci numbers).

Inverse Euler transform of sequence has generating function sum_{n>0} x^F(n)-x^{2F(n)} where F() is Fibonacci.

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 0..6765
• Zai-Qiao Bai and Steven R. Finch, Fibonacci and Lucas Representations, Fibonacci Quart. 54 (2016), no. 4, 319-326. See Table 1 p. 324.
• D. A. Klarner, Representations of N as a sum of distinct elements from special sequences, part 1, part 2, Fib. Quart., 4 (1966), 289-306 and 322.
• Scott V. Tezlaf, On ordinal dynamics and the multiplicity of transfinite cardinality, arXiv:1806.00331 [math.NT], 2018. See p. 45.

Crossrefs

Cf. A000119, A274262, A356874.

Least inverse is A083853.

Programs

Maple

with(combinat): p := product((1+x^fibonacci(i)), i=1..25): s := series(p,x,1000): for k from 0 to 250 do printf(`%d,`,coeff(s,x,k)) od:

Mathematica

imax = 20; p = Product[1+x^Fibonacci[i], {i, 1, imax}]; CoefficientList[p, x][[1 ;; Fibonacci[imax]+1]] (* Jean-François Alcover, Feb 04 2016, adapted from Maple *)
nmax = 91; s=Total/@Subsets[Select[Table[Fibonacci[i], {i, nmax}], # <= nmax &]];
Table[Count[s, n], {n, 0, nmax}] (* Robert Price, Aug 17 2020 *)

PARI

a(n)=local(A,m,f); if(n<0,0,A=1+x*O(x^n); m=1; while((f=fibonacci(m))<=n,A*=1+x^f; m++); polcoeff(A,n))

Formula

a(0) = 1; for n >= 1, a(n) = A000119(n) + A000119(n-1). - Peter Munn, Jan 19 2018

Extensions

More terms from James Sellers, Jun 18 2000