A007000 -id:A007000 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane

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

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

T. D. Noe, Table of n, a(n) for n = 0..6765
Federico Ardila, The coefficients of a Fibonacci power series, Fib. Quart. 42 (3) (2004), 202-204.
Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, A new combinatorial interpretation of partial sums of m-step Fibonacci numbers, arXiv:2503.11055 [math.CO], 2025. See p. 2.
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.
Leonard 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.
David 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.
Ron Knott, Sumthing about Fibonacci Numbers
Neville 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.

Cf. A007000, A003107, A000121, A080097, A096748. Least inverse is A013583.

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

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

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

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

f(x,y,z)=if(xCharles R Greathouse IV, Dec 14 2015

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<=k2 and Fibonacci(i-3)<=kA000045) <= 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 xReinhard 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

More terms from James Sellers, May 29 2000

A003107 Number of partitions of n into Fibonacci parts (with a single type of 1).

Original entry on oeis.org

1, 1, 2, 3, 4, 6, 8, 10, 14, 17, 22, 27, 33, 41, 49, 59, 71, 83, 99, 115, 134, 157, 180, 208, 239, 272, 312, 353, 400, 453, 509, 573, 642, 717, 803, 892, 993, 1102, 1219, 1350, 1489, 1640, 1808, 1983, 2178, 2386, 2609, 2854, 3113, 3393, 3697, 4017, 4367, 4737

Offset: 0

N. J. A. Sloane, Herman P. Robinson

The partitions allow repeated items but the order of items is immaterial (1+2=2+1). - Ron Knott, Oct 22 2003

A098641(n) = a(A000045(n)). - Reinhard Zumkeller, Apr 24 2005

			a(4) = 4 since the 4 partitions of 4 using only Fibonacci numbers, repetitions allowed, are 1+1+1+1, 2+2, 2+1+1, 3+1.

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

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)
G. Almkvist, Partitions with Parts in a Finite Set and with Parts Outside a Finite Set, Exper. Math. vol 11 no 4 (2002) p 449-456.
Igor Pak, Complexity problems in enumerative combinatorics, arXiv:1803.06636 [math.CO], 2018.
Herman P. Robinson, Letter to N. J. A. Sloane, Jan 1974.

Cf. A007000, A005092, A028290 (where the only Fibonacci numbers allowed are 1, 2, 3, 5 and 8).
Cf. A000045, A000119, A102848, A238998.
Row sums of A319394.

import Data.MemoCombinators (memo2, integral)
a003107 n = a003107_list !! n
a003107_list = map (p' 2) [0..] where
   p' = memo2 integral integral p
   p _ 0 = 1
   p k m | m < fib   = 0
         | otherwise = p' k (m - fib) + p' (k + 1) m where fib = a000045 k
-- Reinhard Zumkeller, Dec 09 2015

F:= combinat[fibonacci]:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
       b(n, i-1)+`if`(F(i)>n, 0, b(n-F(i), i))))
    end:
a:= proc(n) local j; for j from ilog[(1+sqrt(5))/2](n+1)
       while F(j+1)<=n do od; b(n, j)
    end:
seq(a(n), n=0..100);  # Alois P. Heinz, Jul 11 2013

CoefficientList[ Series[1/ Product[1 - x^Fibonacci[i], {i, 2, 21}], {x, 0, 53}], x] (* Robert G. Wilson v, Mar 28 2006 *)
nmax = 53;
s = Table[Fibonacci[n], {n, nmax}];
Table[Count[IntegerPartitions@n, x_ /; SubsetQ[s, x]], {n, 0, nmax}] (* Robert Price, Jul 31 2020 *)
F = Fibonacci;
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 2, 0,
     b[n, i - 1] + If[F[i] > n, 0, b[n - F[i], i]]]];
a[n_] := Module[{j}, For[j = Floor@Log[(1+Sqrt[5])/2, n+1],
     F[j + 1] <= n, j++]; b[n, j]];
a /@ Range[0, 100] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

f(x,y,z)=if(xCharles R Greathouse IV, Dec 14 2015

a(n) = (1/n)*Sum_{k=1..n} A005092(k)*a(n-k), n > 1, a(0)=1. - Vladeta Jovovic, Jan 21 2002
G.f.: Product_{i>=2} 1/(1-x^fibonacci(i)). - Ron Knott, Oct 22 2003
a(n) = f(n,1,1) with f(x,y,z) = if xReinhard Zumkeller, Nov 11 2009
G.f.: 1 + Sum_{i>=2} x^Fibonacci(i) / Product_{j=2..i} (1 - x^Fibonacci(j)). - Ilya Gutkovskiy, May 07 2017

More terms from Vladeta Jovovic, Jan 21 2002

A290807 Number of partitions of n into Pell parts (A000129).

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 14, 15, 18, 20, 23, 26, 29, 32, 36, 39, 44, 47, 53, 57, 63, 68, 74, 81, 88, 95, 103, 110, 120, 128, 139, 148, 159, 170, 182, 195, 208, 221, 236, 250, 267, 282, 300, 317, 336, 355, 375, 396, 418, 440, 464, 487, 514, 539, 568, 595, 625, 655, 687, 720, 754, 788

Offset: 0

Ilya Gutkovskiy, Aug 11 2017

nonn

			a(5) = 4 because we have [5], [2, 2, 1], [2, 1, 1, 1] and [1, 1, 1, 1, 1].

Eric Weisstein's World of Mathematics, Pell Number
Index entries for sequences related to partitions

Cf. A000129, A007000, A003107, A067592, A067593, A290808.

CoefficientList[Series[Product[1/(1 - x^Fibonacci[k, 2]), {k, 1, 15}], {x, 0, 67}], x]

G.f.: Product_{k>=1} 1/(1 - x^A000129(k)).

A357380 Expansion of Product_{k>=1} (1 - x^Fibonacci(k)).

Original entry on oeis.org

1, -2, 0, 1, 1, -1, 0, 1, -2, 1, 0, 1, -2, 0, 2, -1, 0, 0, 1, -2, 0, 1, 1, 0, -2, 1, 0, 0, 0, 1, -2, 0, 1, 1, -1, 0, 1, -1, -1, 0, 2, -1, 0, 0, 0, 0, 0, 1, -2, 0, 1, 1, -1, 0, 1, -2, 1, 0, 1, -2, 1, 0, -1, 1, 1, 0, -2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -2, 0, 1, 1, -1, 0, 1, -2, 1, 0, 1, -2, 0, 2, -1, 0, 0, 1, -2, 0, 2, -1, 0, -1

Offset: 0

Ilya Gutkovskiy, Sep 26 2022

sign

Convolution inverse of A007000.

First differences of A093996.

Cf. A000045, A007000, A093996, A357381.

nmax = 100; CoefficientList[Series[Product[(1 - x^Fibonacci[k]), {k, 1, 21}], {x, 0, nmax}], x]

A280168 Expansion of Product_{k>=2} 1/(1 - x^(Fibonacci(k)^2)).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 9, 9, 10, 11, 12, 12, 13, 15, 16, 17, 18, 20, 21, 22, 23, 25, 27, 28, 30, 32, 34, 35, 37, 39, 41, 43, 45, 48, 50, 52, 54, 57, 60, 62, 65, 68, 72, 74, 77, 80, 84, 87, 90, 94, 98, 102, 106, 110, 114, 118, 123, 127, 132, 136, 142, 147, 152, 157, 163, 169, 174, 180, 186, 193, 199

Offset: 0

Ilya Gutkovskiy, Dec 27 2016

nonn

Number of partitions of n into squares of Fibonacci numbers (with a single type of 1).

			a(8) = 3 because we have [4, 4], [4, 1, 1, 1, 1] and [1, 1, 1, 1, 1, 1, 1, 1].

Cf. A000119, A000121, A001156, A003107, A007000, A007598, A238999, A239002.

CoefficientList[Series[Product[1/(1 - x^Fibonacci[k]^2), {k, 2, 20}], {x, 0, 82}], x]

G.f.: Product_{k>=2} 1/(1 - x^(Fibonacci(k)^2)).

A356928 a(n) is the number of solutions, j >= 0 and 1 <= m_1 <= ... <= m_n, of the equation Sum_{k=1..n} F(m_k) = 2^j where F(i) is the i-th Fibonacci number.

Original entry on oeis.org

0, 4, 9, 15, 60, 106

Offset: 0

Pagdame Tiebekabe, Sep 05 2022

a(6) >= 298. We do not have information about whether 298 has been proved to be a(6). - Peter Munn, Sep 08 2022

a(7) >= 772. - Jon E. Schoenfield, Sep 05 2022

			For n=2, the a(2) = 9 solutions are 1 with (1,1), 1 with (1,2), 2 with (1,4), 1 with (2,2), 2 with (2,4), 2 with (3,3), 3 with (4,5), 4 with (4,7), and 4 with (6,6) according to the paper of Bravo and Luca. [That is, 2=1+1, 2=1+1 (again), 4=1+3, 2=1+1 (again), 4=1+3 (again), 4=2+2, 8=3+5, 16=3+13, and 16=8+8.]

J. J. Bravo, and F. Luca, On the Diophantine equation F_n+F_m=2^a, Quaest. Math. 39 (2016) 391-400.
P. Tiebekabe and I. Diouf, On solutions of Diophantine equation F_{n_1}+F_{n_2}+F_{n_3}+F_{n_4}=2^a, Journal of Algebra and Related Topics, Volume 9, Issue 2 (2021), 131-148.

E. F. Bravo and J. J. Bravo, Powers of two as sums of three Fibonacci numbers, Lithuanian Mathematical Journal, 55, pp. 301-311 (2015).
Pagdame Tiebekabe and Ismaïla Diouf, On the Diophantine equation Sum_{k=1..5} F(n_k) = 2^a, arXiv:2209.07871 [math.NT], 2022.

Cf. A007000.

a(0)=0 added by Peter Munn, Sep 05 2022

Name and example edited by Peter Munn, Sep 06 2022

A288122 Number of partitions of n into prime Fibonacci numbers (A005478).

Original entry on oeis.org

1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6, 6, 8, 8, 9, 11, 11, 13, 14, 15, 17, 18, 20, 22, 23, 26, 27, 30, 32, 34, 37, 39, 42, 45, 47, 51, 54, 57, 61, 64, 68, 72, 76, 80, 84, 89, 93, 98, 103, 108, 113, 119, 124, 130, 136, 142, 148, 155, 161, 168, 175, 182, 190, 197, 205, 213, 221, 230

Offset: 0

Ilya Gutkovskiy, Jun 05 2017

nonn

			a(8) = 3 because we have [5, 3], [3, 3, 2] and [2, 2, 2, 2].

Eric Weisstein's World of Mathematics, Fibonacci Prime
Index entries for related partition-counting sequences

Cf. A000045, A000607, A003107, A005478, A007000.

CoefficientList[Series[Product[1/(1 - Boole[PrimeQ[Fibonacci[k]]] x^Fibonacci[k]), {k, 1, 30}], {x, 0, 70}], x]

G.f.: Product_{k>=1} 1/(1 - x^A005478(k)).

A350240 Number of representations of n as a sum of distinct Fibonacci numbers where 1 can be included twice.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 3, 3, 4, 3, 5, 4, 4, 5, 3, 4, 4, 4, 6, 5, 5, 6, 4, 6, 5, 5, 6, 4, 4, 5, 4, 7, 6, 6, 8, 5, 7, 6, 6, 8, 6, 6, 7, 5, 8, 6, 6, 7, 4, 5, 5, 5, 8, 7, 7, 9, 6, 9, 8, 8, 10, 7, 7, 8, 6, 10, 8, 8, 10, 6, 8, 7, 7, 10, 8, 8, 9, 6

Offset: 0

Kung Yue Tong, Dec 21 2021

nonn

A part of size 1 can be included twice in the partitions enumerated by this sequence, but there is only 1 way to include it once. The sequence A000119 only allows 1 to be included once and A000121 allows it to be included twice, but it in two different ways once.
Some connections with the upper Wythoff sequence (A001950):
  a(n) = A000121(n) for n in A001950.
  a(n) = A000119(n) for n-1 in A001950.
  a(n) = A000121(n) - A000119(n) for n+1 in A001950.

			The a(10)=4 partitions are: 8+2 = 8+1+1 = 5+3+1+1 = 5+3+2.
The a(11)=3 partitions are: 8+3 = 8+2+1 = 5+3+2+1.
The a(12)=3 partitions are: 8+3+1 = 8+2+1+1 = 5+3+2+1+1.

Cf. A000045, A000119, A000121, A001950, A003107, A007000, A239002.

seq(n)=my(m=2); while(fibonacci(m)Andrew Howroyd, Dec 21 2021

G.f.: (1 + x + x^2)*Product_{k>=3} (1 + x^Fibonacci(k)). - Andrew Howroyd, Dec 21 2021

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Formula

Extensions

A003107 Number of partitions of n into Fibonacci parts (with a single type of 1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A290807 Number of partitions of n into Pell parts (A000129).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A357380 Expansion of Product_{k>=1} (1 - x^Fibonacci(k)).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A280168 Expansion of Product_{k>=2} 1/(1 - x^(Fibonacci(k)^2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A356928 a(n) is the number of solutions, j >= 0 and 1 <= m_1 <= ... <= m_n, of the equation Sum_{k=1..n} F(m_k) = 2^j where F(i) is the i-th Fibonacci number.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A288122 Number of partitions of n into prime Fibonacci numbers (A005478).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs