cp's OEIS Frontend

A000119 Number of representations of n as a sum of distinct Fibonacci numbers.

%I A000119 M0101 N0037 #144 Jul 02 2025 16:01:53
%S A000119 1,1,1,2,1,2,2,1,3,2,2,3,1,3,3,2,4,2,3,3,1,4,3,3,5,2,4,4,2,5,3,3,4,1,
%T A000119 4,4,3,6,3,5,5,2,6,4,4,6,2,5,5,3,6,3,4,4,1,5,4,4,7,3,6,6,3,8,5,5,7,2,
%U A000119 6,6,4,8,4,6,6,2,7,5,5,8,3,6,6,3,7,4,4,5,1,5,5,4,8,4,7,7,3,9,6,6,9,3,8,8,5
%N A000119 Number of representations of n as a sum of distinct Fibonacci numbers.
%C A000119 Number of partitions into distinct Fibonacci parts (1 counted as single Fibonacci number).
%C A000119 Inverse Euler transform of sequence has generating function Sum_{n>1} (x^F(n) - x^(2*F(n))) where F() are the Fibonacci numbers.
%C A000119 a(n) = 1 if and only if n+1 is a Fibonacci number. The length of such a quasi-period (from Fib(i)-1 to Fib(i+1)-1, inclusive) is a Fibonacci number + 1. The maximum value of a(n) within each subsequent quasi-period increases by a Fibonacci number. For example, from n = 143 to n = 232, the maximum is 13. From 232 to 376, the maximum is 16, an increase of 3. From 376 to 609, 21, an increase of 5. From 609 to 986, 26, increasing by 5 again. Each two subsequent maxima seem to increase by the same increment, the next Fibonacci number. - _Kerry Mitchell_, Nov 14 2009
%C A000119 The maxima of the quasi-periods are in A096748. - _Max Barrentine_, Sep 13 2015
%C A000119 Stockmeyer proves that a(n) <= sqrt(n+1) with equality iff n = Fibonacci(m)^2 - 1 for some m >= 2 (cf. A080097). - _Michel Marcus_, Mar 02 2016
%D A000119 M. Bicknell-Johnson, pp. 53-60 in "Applications of Fibonacci Numbers", volume 8, ed: F. T. Howard, Kluwer (1999); see Theorem 3.
%D A000119 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000119 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000119 T. D. Noe, <a href="/A000119/b000119.txt">Table of n, a(n) for n = 0..6765</a>
%H A000119 Federico Ardila, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/42-3/quartardila03_2004.pdf">The coefficients of a Fibonacci power series</a>, Fib. Quart. 42 (3) (2004), 202-204.
%H A000119 Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, <a href="https://arxiv.org/abs/2503.11055">A new combinatorial interpretation of partial sums of m-step Fibonacci numbers</a>, arXiv:2503.11055 [math.CO], 2025. See p. 2.
%H A000119 Jean Berstel, <a href="http://www-igm.univ-mlv.fr/~berstel/">Home Page</a>
%H A000119 Jean Berstel, <a href="http://www-igm.univ-mlv.fr/~berstel/Articles/2001ExerciceAldo.pdf">An Exercise on Fibonacci Representations</a>, RAIRO/Informatique Theorique, Vol. 35, No 6, 2001, pp. 491-498, in the issue dedicated to Aldo De Luca on the occasion of his 60th anniversary.
%H A000119 Pierre Bonardo and Anna E. Frid, <a href="https://arxiv.org/abs/1806.09534">Number of valid decompositions of Fibonacci prefixes</a>, arXiv:1806.09534 [math.CO], 2018.
%H A000119 Alfred Brousseau, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/fibonacci-tables.html">Fibonacci and Related Number Theoretic Tables</a>, Fibonacci Association, San Jose, CA, 1972. See p. 54.
%H A000119 Leonard Carlitz, <a href="https://fq.math.ca/Scanned/6-4/carlitz.pdf">Fibonacci Representations</a>, Fibonacci Quarterly, volume 6, number 4, October 1968, pages 193-220, a(n) = R(N).
%H A000119 Sam Chow and Tom Slattery, <a href="https://arxiv.org/abs/2009.08222">On Fibonacci partitions</a>, arXiv:2009.08222 [math.NT], 2020.
%H A000119 Sam Chow and Tom Slattery, <a href="https://doi.org/10.1016/j.jnt.2021.02.010">On Fibonacci partitions</a>, Journal of Number Theory, Volume 225, August 2021, Pages 310-326.
%H A000119 Sam Chow and Owen Jones, <a href="https://arxiv.org/abs/2308.15415">On the variance of the Fibonacci partition function</a>, arXiv:2308.15415 [math.NT], 2023.
%H A000119 Michel Dekking and Ad van Loon, <a href="https://arxiv.org/abs/2304.11387">Counting base phi representations</a>, arXiv:2304.11387 [math.NT], 2023.
%H A000119 Tom Kempton, <a href="https://arxiv.org/abs/2311.06006">The Dynamics of the Fibonacci Partition Function</a>, arXiv:2311.06006 [math.NT], 2023.
%H A000119 David A. Klarner, Representations of N as a sum of distinct elements from special sequences, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/4-4/klarner-a.pdf">part 1</a>, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/4-4/klarner-b.pdf">part 2</a>, Fib. Quart., 4 (1966), 289-306 and 322.
%H A000119 Ron Knott, <a href="http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibrep.html#sumoffib">Sumthing about Fibonacci Numbers</a>
%H A000119 Neville Robbins, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/34-4/robbins.pdf">Fibonacci partitions</a>, Fib. Quart. 34 (4) (1996), 306-313.
%H A000119 Jeffrey Shallit, <a href="https://cs.uwaterloo.ca/~shallit/Papers/ntfl.ps">Number theory and formal languages</a>, in D. A. Hejhal, J. Friedman, M. C. Gutzwiller and A. M. Odlyzko, eds., Emerging Applications of Number Theory, IMA Volumes in Mathematics and Its Applications, V. 109, Springer-Verlag, 1999, pp. 547-570. (Eq. 9.2.)
%H A000119 Jeffrey Shallit, <a href="https://arxiv.org/abs/2007.14930">Robbins and Ardila meet Berstel</a>, Arxiv preprint arXiv:2007.14930 [math.CO], 2020.
%H A000119 Paul K. Stockmeyer, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/46_47-2/Stockmeyer.pdf">A Smooth Tight Upper Bound for the Fibonacci Representation Function R(N)</a>, Fibonacci Quarterly, Volume 46/47, Number 2, May 2009.
%H A000119 Scott V. Tezlaf, <a href="https://arxiv.org/abs/1806.00331">On ordinal dynamics and the multiplicity of transfinite cardinality</a>, arXiv:1806.00331 [math.NT], 2018. See p. 42.
%F A000119 a(A000045(n)) = A065033(n).
%F A000119 a(n) = (1/n)*Sum_{k=1..n} b(k)*a(n-k), b(k) = Sum_{f} (-1)^(k/f+1)*f, where the last sum is taken over all Fibonacci numbers f dividing k. - _Vladeta Jovovic_, Aug 28 2002
%F A000119 a(n) = 1, if n <= 2; a(n) = a(Fibonacci(i-2)+k)+a(k) if n>2 and 0<=k<Fibonacci(i-3); a(n)= 2*a(k) if n>2 and Fibonacci(i-3)<=k<Fibonacci(i-2); a(n) = a(Fibonacci(i+1)-2-k) otherwise where Fibonacci(i) is the largest Fibonacci number (A000045) <= n and k=n-Fibonacci(i). [Bicknell-Johnson] - _Ron Knott_, Dec 06 2004
%F A000119 a(n) = f(n,1,1) with f(x,y,z) = if x<y then 0^x else f(x-y,y+z,y)+f(x,y+z,y). - _Reinhard Zumkeller_, Nov 11 2009
%F A000119 G.f.: Product_{n>=1} 1 + q^F(n+1) = 1 + Sum_{n>=1} ( q^F(n+1) * Product_{k=1..n-1} 1 + q^F(k+1) ). - _Joerg Arndt_, Oct 20 2012
%F A000119 a(A000071(n)) = 1. - _Reinhard Zumkeller_, Dec 28 2012
%p A000119 with(combinat): p := product((1+x^fibonacci(i)), i=2..25): s := series(p,x,1000): for k from 0 to 250 do printf(`%d,`,coeff(s,x,k)) od: # _James Sellers_, May 29 2000
%t A000119 CoefficientList[ Normal@Series[ Product[ 1+z^Fibonacci[ k ], {k, 2, 13} ], {z, 0, 233} ], z ]
%t A000119 nmax = 104; s = Union@Table[Fibonacci[n], {n, nmax}];
%t A000119 Table[Length@Select[IntegerPartitions[n, All, s], DeleteDuplicates[#] == # &], {n, 0, nmax}] (* _Robert Price_, Aug 17 2020 *)
%o A000119 (PARI) a(n)=local(A,m,f); if(n<0,0,A=1+x*O(x^n); m=2; while((f=fibonacci(m))<=n,A*=1+x^f; m++); polcoeff(A,n))
%o A000119 (PARI) f(x,y,z)=if(x<y, 0^x, f(x-y,y+z,y)+f(x,y+z,y))
%o A000119 a(n)=f(n,1,1) \\ _Charles R Greathouse IV_, Dec 14 2015
%o A000119 (Haskell)
%o A000119 a000119 = p $ drop 2 a000045_list where
%o A000119    p _      0 = 1
%o A000119    p (f:fs) m = if m < f then 0 else p fs (m - f) + p fs m
%o A000119 -- _Reinhard Zumkeller_, Dec 28 2012, Oct 21 2011
%Y A000119 Cf. A007000, A003107, A000121, A080097, A096748. Least inverse is A013583.
%K A000119 nonn,nice,look
%O A000119 0,4
%A A000119 _N. J. A. Sloane_
%E A000119 More terms from _James Sellers_, May 29 2000