A072214 Number of partitions of Fibonacci(n).

1, 1, 1, 2, 3, 7, 22, 101, 792, 12310, 451276, 49995925, 22540654445, 60806135438329, 1596675274490756791, 758949605954969709105721, 14362612091531863067120268402228, 29498346711208035625096160181520548669694, 23537552807178094028466621551669121053281242290608650

Offset: 0

Author

Jeff Burch, Jul 03 2002

Keywords

• nonn

Comments

Also number of partitions of F(n+2) whose highest term is F(n+1) ( or, which is the same, whose number of terms is F(n+1)). - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Sep 14 2007

Divide the set of partitions P(i,j) in two subsets : 1) Partitions containing at least one term 1; Deleting a term 1, we prove that their number is P(i-1,j-1) 2). Subtracting 1 from each term of the other partitions we prove that their number is P(i-j,j) Hence P(i,j) - P(i-1,j-1) = P(i-j,j) Replacing successively in this formula i by i-1 and j by j-1 and summing all these equalities we get, if j>= floor((i+1)/2) P(i,j)=sum ({k,1,j}P(i-j;k))= A000041(i-j) As for i=F(n+2) and j=F(n+1) the condition is satisfied : P(F(n+2),F(n+1)) = P (F(n+2),F(n+1)= A000041(n) = 1072214(n). - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Sep 14 2007

Examples

			F(5) = 5, F(4) = 3: 5 = 3+2 = 3+1+1 (or 5 = 3+1+1 = 2+2+1), then P(5,3) = 2 = A000041(2) = A000041(F(3)) = A072214(3).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..30 (terms n = 1..26 from Seiichi Manyama)

Crossrefs

Cf. A000041, A000045, A072241.

Programs

Haskell

a072214 = a000041 . a000045 . (+ 1)  -- Reinhard Zumkeller, Dec 09 2015

Magma

[NumberOfPartitions(Fibonacci(n)): n in [1..18]]; // Vincenzo Librandi May 09 2016

Maple

F:= n-> (<<0|1>, <1|1>>^n)[1, 2]:
a:= n-> combinat[numbpart](F(n)):
seq(a(n), n=0..18);  # Alois P. Heinz, Apr 06 2021

Mathematica

Table[PartitionsP[Fibonacci[n]], {n, 1, 17}]

PARI

a(n) = numbpart(fibonacci(n)); \\ Michel Marcus, May 09 2016

Python

from sympy import npartitions as p, fibonacci as f
def a(n): return p(f(n)) # Indranil Ghosh, Jun 08 2017

Formula

Let P(i,j) denote the number of partitions of i whose highest term is j A072214(n) = A000041(F(n)) = P(F(n+2),F(n+1)) - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Sep 14 2007

a(n) = A000041(A000045(n)). - Michel Marcus, May 09 2016

a(n) = [x^Fibonacci(n)] Product_{k>=1} 1/(1 - x^k). - Ilya Gutkovskiy, Jun 08 2017

Extensions

Edited by Robert G. Wilson v, Jul 06 2002

a(18) by Vincenzo Librandi, May 09 2016

a(0)=1 prepended by Alois P. Heinz, Apr 06 2021