cp's OEIS Frontend

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

%I A003107 M0556 #82 Oct 29 2023 01:43:38
%S A003107 1,1,2,3,4,6,8,10,14,17,22,27,33,41,49,59,71,83,99,115,134,157,180,
%T A003107 208,239,272,312,353,400,453,509,573,642,717,803,892,993,1102,1219,
%U A003107 1350,1489,1640,1808,1983,2178,2386,2609,2854,3113,3393,3697,4017,4367,4737
%N A003107 Number of partitions of n into Fibonacci parts (with a single type of 1).
%C A003107 The partitions allow repeated items but the order of items is immaterial (1+2=2+1). - _Ron Knott_, Oct 22 2003
%C A003107 A098641(n) = a(A000045(n)). - _Reinhard Zumkeller_, Apr 24 2005
%D A003107 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A003107 Reinhard Zumkeller, <a href="/A003107/b003107.txt">Table of n, a(n) for n = 0..10000</a> (first 1000 terms from T. D. Noe)
%H A003107 G. Almkvist, <a href="http://projecteuclid.org/euclid.em/1057864654">Partitions with Parts in a Finite Set and with Parts Outside a Finite Set</a>, Exper. Math. vol 11 no 4 (2002) p 449-456.
%H A003107 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.
%H A003107 Herman P. Robinson, <a href="/A003105/a003105.pdf">Letter to N. J. A. Sloane, Jan 1974</a>.
%F A003107 a(n) = (1/n)*Sum_{k=1..n} A005092(k)*a(n-k), n > 1, a(0)=1. - _Vladeta Jovovic_, Jan 21 2002
%F A003107 G.f.: Product_{i>=2} 1/(1-x^fibonacci(i)). - _Ron Knott_, Oct 22 2003
%F A003107 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
%F A003107 G.f.: 1 + Sum_{i>=2} x^Fibonacci(i) / Product_{j=2..i} (1 - x^Fibonacci(j)). - _Ilya Gutkovskiy_, May 07 2017
%e A003107 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.
%p A003107 F:= combinat[fibonacci]:
%p A003107 b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,
%p A003107        b(n, i-1)+`if`(F(i)>n, 0, b(n-F(i), i))))
%p A003107     end:
%p A003107 a:= proc(n) local j; for j from ilog[(1+sqrt(5))/2](n+1)
%p A003107        while F(j+1)<=n do od; b(n, j)
%p A003107     end:
%p A003107 seq(a(n), n=0..100);  # _Alois P. Heinz_, Jul 11 2013
%t A003107 CoefficientList[ Series[1/ Product[1 - x^Fibonacci[i], {i, 2, 21}], {x, 0, 53}], x] (* _Robert G. Wilson v_, Mar 28 2006 *)
%t A003107 nmax = 53;
%t A003107 s = Table[Fibonacci[n], {n, nmax}];
%t A003107 Table[Count[IntegerPartitions@n, x_ /; SubsetQ[s, x]], {n, 0, nmax}] (* _Robert Price_, Jul 31 2020 *)
%t A003107 F = Fibonacci;
%t A003107 b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 2, 0,
%t A003107      b[n, i - 1] + If[F[i] > n, 0, b[n - F[i], i]]]];
%t A003107 a[n_] := Module[{j}, For[j = Floor@Log[(1+Sqrt[5])/2, n+1],
%t A003107      F[j + 1] <= n, j++]; b[n, j]];
%t A003107 a /@ Range[0, 100] (* _Jean-François Alcover_, May 21 2021, after _Alois P. Heinz_ *)
%o A003107 (Haskell)
%o A003107 import Data.MemoCombinators (memo2, integral)
%o A003107 a003107 n = a003107_list !! n
%o A003107 a003107_list = map (p' 2) [0..] where
%o A003107    p' = memo2 integral integral p
%o A003107    p _ 0 = 1
%o A003107    p k m | m < fib   = 0
%o A003107          | otherwise = p' k (m - fib) + p' (k + 1) m where fib = a000045 k
%o A003107 -- _Reinhard Zumkeller_, Dec 09 2015
%o A003107 (PARI) f(x,y,z)=if(x<y, 0^x, f(x-y,y,z)+f(x,y+z,y))
%o A003107 a(n) = f(n,1,1) \\ _Charles R Greathouse IV_, Dec 14 2015
%Y A003107 Cf. A007000, A005092, A028290 (where the only Fibonacci numbers allowed are 1, 2, 3, 5 and 8).
%Y A003107 Cf. A000045, A000119, A102848, A238998.
%Y A003107 Row sums of A319394.
%K A003107 nonn,easy
%O A003107 0,3
%A A003107 _N. J. A. Sloane_, _Herman P. Robinson_
%E A003107 More terms from _Vladeta Jovovic_, Jan 21 2002