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

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

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.

Formula

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

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

Prog

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

Crossrefs

Cf. A000119, A274262, A356874.

Least inverse is A083853.

Sequence in context: A264982 A134674 A253894 * A230022 A049846 A086712

Adjacent sequences: A000118 A000119 A000120 * A000122 A000123 A000124

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from James A. Sellers, Jun 18 2000

Status

approved