login
Number of partitions of n into Fibonacci parts (with a single type of 1).
(Formerly M0556)
33

%I M0556 #82 Oct 29 2023 01:43:38

%S 1,1,2,3,4,6,8,10,14,17,22,27,33,41,49,59,71,83,99,115,134,157,180,

%T 208,239,272,312,353,400,453,509,573,642,717,803,892,993,1102,1219,

%U 1350,1489,1640,1808,1983,2178,2386,2609,2854,3113,3393,3697,4017,4367,4737

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

%C The partitions allow repeated items but the order of items is immaterial (1+2=2+1). - _Ron Knott_, Oct 22 2003

%C A098641(n) = a(A000045(n)). - _Reinhard Zumkeller_, Apr 24 2005

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

%H 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 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 Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.

%H Herman P. Robinson, <a href="/A003105/a003105.pdf">Letter to N. J. A. Sloane, Jan 1974</a>.

%F a(n) = (1/n)*Sum_{k=1..n} A005092(k)*a(n-k), n > 1, a(0)=1. - _Vladeta Jovovic_, Jan 21 2002

%F G.f.: Product_{i>=2} 1/(1-x^fibonacci(i)). - _Ron Knott_, Oct 22 2003

%F 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 G.f.: 1 + Sum_{i>=2} x^Fibonacci(i) / Product_{j=2..i} (1 - x^Fibonacci(j)). - _Ilya Gutkovskiy_, May 07 2017

%e 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 F:= combinat[fibonacci]:

%p b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0,

%p b(n, i-1)+`if`(F(i)>n, 0, b(n-F(i), i))))

%p end:

%p a:= proc(n) local j; for j from ilog[(1+sqrt(5))/2](n+1)

%p while F(j+1)<=n do od; b(n, j)

%p end:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Jul 11 2013

%t CoefficientList[ Series[1/ Product[1 - x^Fibonacci[i], {i, 2, 21}], {x, 0, 53}], x] (* _Robert G. Wilson v_, Mar 28 2006 *)

%t nmax = 53;

%t s = Table[Fibonacci[n], {n, nmax}];

%t Table[Count[IntegerPartitions@n, x_ /; SubsetQ[s, x]], {n, 0, nmax}] (* _Robert Price_, Jul 31 2020 *)

%t F = Fibonacci;

%t b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 2, 0,

%t b[n, i - 1] + If[F[i] > n, 0, b[n - F[i], i]]]];

%t a[n_] := Module[{j}, For[j = Floor@Log[(1+Sqrt[5])/2, n+1],

%t F[j + 1] <= n, j++]; b[n, j]];

%t a /@ Range[0, 100] (* _Jean-François Alcover_, May 21 2021, after _Alois P. Heinz_ *)

%o (Haskell)

%o import Data.MemoCombinators (memo2, integral)

%o a003107 n = a003107_list !! n

%o a003107_list = map (p' 2) [0..] where

%o p' = memo2 integral integral p

%o p _ 0 = 1

%o p k m | m < fib = 0

%o | otherwise = p' k (m - fib) + p' (k + 1) m where fib = a000045 k

%o -- _Reinhard Zumkeller_, Dec 09 2015

%o (PARI) f(x,y,z)=if(x<y, 0^x, f(x-y,y,z)+f(x,y+z,y))

%o a(n) = f(n,1,1) \\ _Charles R Greathouse IV_, Dec 14 2015

%Y Cf. A007000, A005092, A028290 (where the only Fibonacci numbers allowed are 1, 2, 3, 5 and 8).

%Y Cf. A000045, A000119, A102848, A238998.

%Y Row sums of A319394.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_, _Herman P. Robinson_

%E More terms from _Vladeta Jovovic_, Jan 21 2002