A007000 Number of partitions of n into Fibonacci parts (with 2 types of 1). (Formerly M1045)

1, 2, 4, 7, 11, 17, 25, 35, 49, 66, 88, 115, 148, 189, 238, 297, 368, 451, 550, 665, 799, 956, 1136, 1344, 1583, 1855, 2167, 2520, 2920, 3373, 3882, 4455, 5097, 5814, 6617, 7509, 8502, 9604, 10823, 12173, 13662, 15302, 17110, 19093, 21271, 23657, 26266

Offset

0,2

References

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

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)

James Propp and N. J. A. Sloane, Email, March 1994.

Formula

a(n) = 1/n*Sum_{k=1..n} (A005092(k)+1)*a(n-k), n > 1, a(0)=1. - Vladeta Jovovic, Aug 22 2002

G.f.: 1/Product_{j>=1} (1-x^fibonacci(j)). - Emeric Deutsch, Mar 05 2006

G.f.: Sum_{i>=0} x^Fibonacci(i) / Product_{j=1..i} (1 - x^Fibonacci(j)). - Ilya Gutkovskiy, May 07 2017

Example

a(2)=4 because we have [2],[1',1'],[1',1],[1,1] (the two types of 1 are denoted 1 and 1').

Maple

with(combinat): gf := 1/product((1-q^fibonacci(k)), k=1..20): s := series(gf, q, 200): for i from 0 to 199 do printf(`%d, `, coeff(s, q, i)) od: # James A. Sellers, Feb 08 2002

Mathematica

CoefficientList[ Series[ 1/Product[1 - x^Fibonacci[i], {i, 1, 15}], {x, 0, 50}], x]
nmax = 46; f = Table[Fibonacci[n], {n, nmax}];
Table[Length[IntegerPartitions[n, All, f]], {n, 0, nmax}] (* Robert Price, Aug 02 2020 *)

Prog

(Haskell)
import Data.MemoCombinators (memo2, integral)
a007000 n = a007000_list !! n
a007000_list = map (p' 1) [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

Crossrefs

Cf. A003107.

Cf. A000045.

Sequence in context: A067997 A175491 A034379 * A073472 A096914 A004250

Adjacent sequences: A006997 A006998 A006999 * A007001 A007002 A007003

Keyword

nonn

Author

N. J. A. Sloane, Mira Bernstein

Extensions

More terms from James A. Sellers, Feb 08 2002

Status

approved