|
|
A003107
|
|
Number of partitions of n into Fibonacci parts (with a single type of 1).
(Formerly M0556)
|
|
33
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
The partitions allow repeated items but the order of items is immaterial (1+2=2+1). - Ron Knott, Oct 22 2003
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
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 x<y then 0^x else f(x-y,y,z)+f(x,y+z,y). - Reinhard 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
|
|
EXAMPLE
|
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.
|
|
MAPLE
|
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:
|
|
MATHEMATICA
|
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]];
|
|
PROG
|
(Haskell)
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
(PARI) f(x, y, z)=if(x<y, 0^x, f(x-y, y, z)+f(x, y+z, y))
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|