login
Convolution of Fibonacci numbers (A000045) and partition numbers (A000041).
2

%I #60 May 09 2021 07:55:18

%S 0,1,2,5,10,20,37,68,120,210,360,612,1028,1717,2846,4698,7720,12649,

%T 20666,33700,54856,89183,144831,235016,381102,617693,1000753,1620882,

%U 2624645,4249245,6878455,11133304,18018601,29160254,47188998,76361562,123565443,199944982

%N Convolution of Fibonacci numbers (A000045) and partition numbers (A000041).

%H Alois P. Heinz, <a href="/A275388/b275388.txt">Table of n, a(n) for n = 0..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FibonacciNumber.html">Fibonacci Number</a>, <a href="http://mathworld.wolfram.com/PartitionFunctionP.html">Partition Function P</a>, <a href="http://mathworld.wolfram.com/q-PochhammerSymbol.html">q-Pochhammer Symbol</a>.

%F a(n) = Sum_{k=1..n} A000045(k)*A000041(n-k).

%F G.f.: x/((1 - x - x^2) * (x; x)_inf), where (x; x)_inf is the q-Pochhammer symbol.

%F a(n+1) - a(n) - a(n-1) = A000041(n).

%F a(n) ~ phi^n / (sqrt(5) * QPochhammer(1/phi)), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - _Vaclav Kotesovec_, Sep 27 2016

%t Table[Sum[Fibonacci[k] PartitionsP[n - k], {k, 1, n}], {n, 0, 30}]

%o (PARI) a(n)=sum(k=1, n, fibonacci(k)*numbpart(n - k)); \\ _Indranil Ghosh_, Jun 29 2017

%o (Python)

%o from sympy import fibonacci, npartitions

%o def a(n): return sum([fibonacci(k)*npartitions(n - k) for k in range(1, n + 1)])

%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jun 29 2017

%Y Cf. A000041, A000045.

%K nonn

%O 0,3

%A _Vladimir Reshetnikov_, Sep 26 2016