|
| |
|
|
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
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
|
Sam Chow and Tom Slattery, On Fibonacci partitions, Journal of Number Theory, Volume 225, August 2021, Pages 310-326.
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.
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.)
|
|
|
FORMULA
|
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
|
|
|
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))
(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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
