The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000119 Number of representations of n as a sum of distinct Fibonacci numbers.
(Formerly M0101 N0037)
79
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
Number of partitions into distinct Fibonacci parts (1 counted as single Fibonacci number).
Inverse Euler transform of sequence has generating function Sum_{n>1} (x^F(n) - x^(2*F(n)) where F() are the Fibonacci numbers.
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
The maxima of the quasi-periods are in A096748. - Max Barrentine, Sep 13 2015
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
REFERENCES
M. Bicknell-Johnson, pp. 53-60 in "Applications of Fibonacci Numbers", volume 8, ed: F. T. Howard, Kluwer (1999); see Theorem 3.
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
F. Ardila, The coefficients of a Fibonacci power series, Fib. Quart. 42 (3) (2004), 202-204.
Jean Berstel, Home Page
Jean Berstel, An Exercise on Fibonacci Representations, 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.
Pierre Bonardo and Anna E. Frid, Number of valid decompositions of Fibonacci prefixes, arXiv:1806.09534 [math.CO], 2018.
Alfred Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972. See p. 54.
L. Carlitz, Fibonacci Representations, Fibonacci Quarterly, volume 6, number 4, October 1968, pages 193-220, a(n) = R(N).
Sam Chow and Tom Slattery, On Fibonacci partitions, arXiv:2009.08222 [math.NT], 2020.
Sam Chow and Tom Slattery, On Fibonacci partitions, Journal of Number Theory, Volume 225, August 2021, Pages 310-326.
Sam Chow and Owen Jones, On the variance of the Fibonacci partition function, arXiv:2308.15415 [math.NT], 2023.
Michel Dekking and Ad van Loon, Counting base phi representations, arXiv:2304.11387 [math.NT], 2023.
Tom Kempton, The Dynamics of the Fibonacci Partition Function, arXiv:2311.06006 [math.NT], 2023.
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.
N. Robbins, Fibonacci partitions, Fib. Quart. 34 (4) (1996), 306-313.
Jeffrey Shallit, Number theory and formal languages, 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.)
Jeffrey Shallit, Robbins and Ardila meet Berstel, Arxiv preprint arXiv:2007.14930 [math.CO], 2020.
Paul K. Stockmeyer, A Smooth Tight Upper Bound for the Fibonacci Representation Function R(N), Fibonacci Quarterly, Volume 46/47, Number 2, May 2009.
Scott V. Tezlaf, On ordinal dynamics and the multiplicity of transfinite cardinality, arXiv:1806.00331 [math.NT], 2018. See p. 42.
FORMULA
a(A000045(n)) = A065033(n).
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
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
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
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
a(A000071(n)) = 1. - Reinhard Zumkeller, Dec 28 2012
MAPLE
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 A. Sellers, May 29 2000
MATHEMATICA
CoefficientList[ Normal@Series[ Product[ 1+z^Fibonacci[ k ], {k, 2, 13} ], {z, 0, 233} ], z ]
nmax = 104; s = Union@Table[Fibonacci[n], {n, nmax}];
Table[Length@Select[IntegerPartitions[n, All, s], DeleteDuplicates[#] == # &], {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=2; while((f=fibonacci(m))<=n, A*=1+x^f; m++); polcoeff(A, n))
(PARI) f(x, y, z)=if(x<y, 0^x, f(x-y, y+z, y)+f(x, y+z, y))
a(n)=f(n, 1, 1) \\ Charles R Greathouse IV, Dec 14 2015
(Haskell)
a000119 = p $ drop 2 a000045_list where
p _ 0 = 1
p (f:fs) m = if m < f then 0 else p fs (m - f) + p fs m
-- Reinhard Zumkeller, Dec 28 2012, Oct 21 2011
CROSSREFS
Cf. A007000, A003107, A000121, A080097, A096748. Least inverse is A013583.
Sequence in context: A256660 A109967 A359539 * A286326 A097368 A271900
KEYWORD
nonn,nice,look
AUTHOR
EXTENSIONS
More terms from James A. Sellers, May 29 2000
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 14 19:19 EDT 2024. Contains 373401 sequences. (Running on oeis4.)