Sequence A000119: Partitions into Fibonacci Parts

This sequence, Sloane's A0119, counts the number of distinct ways to express the number n as a sub of distinct positive numbers each of which is a Fibonacci number (A0045). Though the number 1 appears twice in the Fibonacci sequence, a 1 may be used only once for the porposes of A0119. Also, reordering the terms does not count as a different "way to express".

The sequence starts:

A000119: 1, 1, 1, 2, 1, 2, 2, 1, 3, 2, 2, 3, 1, 3, 3, 2, 4, 2, 3, 3, 1, 4, 3, 3, 5, 2, 4, 4, 2, 5, 3, 3, 4, 1, 4, 4, 3, 6, 3, 5, 5, 2, 6, 4, 4, 6, 2, 5, 5, 3, 6, 3, 4, 4, 1, 5, 4, 4, 7, 3, 6, 6, 3, 8, 5, 5, 7, 2, 6, 6, 4, 8, 4, 6, 6, 2, 7, 5, 5, 8, 3, 6, 6, 3, 7, 4, 4, 5, 1, 5, 5, 4, 8, 4, 7, 7, 3, 9, 6, 6, 9, 3, 8, 8, 5, ...

For n=0 to 12, the terms in A0119 correspond to the following different ways to form the sums:

A0119(0)=1: ("null sum")
A0119(1)=1: 1
A0119(2)=1: 2
A0119(3)=2: 3 = 2+1
A0119(4)=1: 3+1
A0119(5)=2: 5 = 3+2
A0119(6)=2: 5+1 = 3+2+1
A0119(7)=1: 5+2
A0119(8)=3: 8 = 5+3 = 5+2+1
A0119(9)=2: 8+1 = 5+3+1
A0119(10)=2: 8+2 = 5+3+2
A0119(11)=3: 8+3 = 8+2+1 = 5+3+2+1
A0119(12)=1: 8+3+1
...

Breakdown by Number of Summed Parts

This sequence can be broken up into an array (or triangle) of related sequences in which each column indicates the total n, and each row gives the number of terms (distinct Fibonacci numbers) that were added together to make the total n. For example under the number 26, in the "3 parts" row, we see the number 2, which means that there are 2 ways to form the sum 26 out of 3 distinct Fibonacci numbers (specifically, 21+3+2 and 13+8+5).

sum n:	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36	37	38	39
0 parts:	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1 part:		1	1	1	0	1	0	0	1	0	0	0	0	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0
2 parts:			0	1	1	1	1	1	1	1	1	1	0	1	1	1	1	0	1	0	0	1	1	1	1	0	1	0	0	1	0	0	0	0	1	1	1	1	0	1
3 parts:				0	0	0	1	0	1	1	1	1	1	1	1	1	2	1	1	1	1	1	1	1	2	1	2	1	1	1	1	1	1	0	1	1	1	2	1	2
4 parts:					0	0	0	0	0	0	0	1	0	0	1	0	1	1	1	1	0	1	1	1	1	1	1	2	1	2	1	1	1	1	1	1	1	2	1	1
5 parts:						0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	1	0	0	1	0	1	1	1	1	0	0	1	0	1	1	1
6 parts:							0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0

In the OEIS, rows 1-4 of this table are sequences A10056, A357731, A357732, and A357722. The column sums of the table are A0119.

A paper by Felix Weinstein ¹ came to my attention in 1994. It discusses these partitions in some detail and at one point comes to a derivation of a sequence that requires the same summation as A6874, leading to the same sequence.

1 : Felix V. Weinstein, "Notes on Fibonacci partitions." Experimental Mathematics 25(4 (2016): pp. 482-499.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2024 Mar 13.

s.30