A289249 Number of compositions of n if only the order of parts 1 and 2 matters.

1, 1, 2, 4, 7, 12, 21, 35, 59, 98, 162, 266, 437, 713, 1163, 1893, 3077, 4995, 8105, 13139, 21293, 34492, 55858, 90438, 146406, 236974, 383538, 620703, 1004471, 1625447, 2630249, 4256087, 6886804, 11143447, 18030911, 29175137, 47206975, 76383199, 123591458

Offset: 0

Author

Gregory L. Simay, Jun 29 2017

Keywords

• nonn

Comments

If only the order of parts 1 and 2 matters, then the remaining parts can be frozen "[]" in a partition subsequence; e.g., a(15) would count the sequence 5,4,3,2,1 twice: [5,4,3]2,1 and [5,4,3]1,2. (Also see example.)

Examples

			For n=6, the 21 sequences counted are [6]; [5],1; [4],2; [3,3], [4],1,1; [3],2,1; [3],1,2; 2,2,2; [3],1,1,1; 2,2,1,1; 2,1,2,1; 1,2,2,1; 1,2,1,2; 1,1,2,2; 2,1,1,2; 2,1,1,1,1; 1,2,1,1,1; 1,1,2,1,1; 1,1,1,2,1; 1,1,1,1,2; and 1,1,1,1,1,1.
		

Crossrefs

Cf. A000041, A000045, A275388.

Programs

Mathematica

Table[PartitionsP[n] + Sum[Fibonacci[k] PartitionsP[n - 2 - k], {k, n - 2}], {n, 0, 50}] (* Indranil Ghosh, Jun 29 2017 *)

PARI

a275388(n)=sum(k=1, n, fibonacci(k)*numbpart(n - k));
a(n)=numbpart(n)+a275388(n - 2); \\ Indranil Ghosh, Jun 29 2017

Python

from sympy import fibonacci, npartitions
def a(n): return npartitions(n) + sum([fibonacci(k)*npartitions(n - 2 - k) for k in range(1, n - 1)])
print([a(n) for n in range(51)]) # Indranil Ghosh, Jun 29 2017

Formula

a(n) = A000041(n) + A275388(n-2), the sum of the n-th partition number and the (n-2)th convolution of partition numbers with Fibonacci numbers. E.g., a(8) = 59 = A000041(8) + A275388(6) = 22 + 37 = 59.

a(n) = A275388(n+1) - A275388(n) - A275388(n-1) + A275388(n-2).

G.f.: (1/x)*(1-x)*(1-x^2)*(g.f. of A275388) =(1/x)*(1-x)*(1-x^2)*Sum_{k=1..n} A000045(k)*A000041(n-k).

Extensions

More terms from Indranil Ghosh, Jun 29 2017