A275548 - OEIS

A275548

Number of compositions of n if only the order of the odd numbers matter.

1, 1, 2, 3, 6, 9, 16, 25, 43, 68, 113, 181, 298, 479, 781, 1260, 2048, 3308, 5364, 8672, 14048, 22720, 36782, 59502, 96305, 155807, 252136, 407943, 660113, 1068056, 1728210, 2796266, 4524531, 7320797, 11845394, 19166191, 31011673, 50177864, 81189642, 131367506

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

The number of partitions of n = 2k with only even numbers is p(k) = A000041(k). The number of compositions of n with only odd numbers is F(n) = the n-th Fibonacci number = A000045(n). Enumerating a(n) is therefore a sum of products of partition numbers and Fibonacci numbers.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000

FORMULA

a(2k+1) = Sum_{j=0..k} p(j)*F(2k + 1 - 2j), where p(j) = A000041(j), the number of partitions of j, and F(j) = A000045(j), the j-th Fibonacci number.

a(2k) = p(k) + Sum_{j=0..(k-1)} p(j)*F(2k - 2j).

a(2k+1) = a(2k) + a(2k-1).

a(2k) = a(2k-1) + a(2k-2) + p(k) - p(k-1).

G.f.: 1/(1 - x - x^2) * Product_{n>=2} 1/(1 - x^(2*n)). - Peter Bala, Aug 03 2016 [corrected by Vaclav Kotesovec, Jun 02 2018]

a(n) ~ c * phi^n, where c = 1 / (sqrt(5) * QPochhammer[1/phi^2]) = 0.92890318501026782066... and phi = A001622 = (1 + sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Jun 02 2018

EXAMPLE

The compositions enumerated by a(6) = 16 are (6),(5,1),(1,5),(4,2)=(2,4), (3,3), (4,1,1)=(1,4,1)=(1,1,4), (2,3,1)=(3,2,1)=(3,1,2), (2,1,3)=(1,2,3)=(1,3,2), (2,2,2), (3,1,1,1),(1,3,1,1),(1,1,3,1),(1,1,1,3), (2,2,1,1)=(2,1,2,1)=(2,1,1,2)=(1,2,1,2)=(1,1,2,2)=(1,2,2,1), (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), (1,1,1,1,1,1).

The compositions enumerated by a(5) = 9 are (5), (4,1)=(1,4), (3,2)=(2,3), (3,1,1), (1,3,1), (1,1,3), (2,2,1)=(2,1,2)=(1,2,2), (2,1,1,1)=(1,2,1,1)=(1,1,2,1)=(1,1,1,2), (1,1,1,1,1).

MAPLE

b:= proc(n, i, p) option remember; (t-> `if`(n=0, p!,

`if`(i<1, 0, add(b(n-i*j, i-1, p+`if`(t, j, 0))/

`if`(t, j, 0)!, j=0..n/i))))(i::odd)

end:

a:= n-> b(n$2, 0):

seq(a(n), n=0..50); # Alois P. Heinz, Aug 03 2016

MATHEMATICA

b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i < 1, 0, Sum[b[n - i*j, i - 1, p + If[#, j, 0]]/If[#, j, 0]!, {j, 0, n/i}]]]&[OddQ[i]];

a[n_] := b[n, n, 0];

Table[a[n], {n, 0, 50}] (* Jean-François Alcover, May 21 2018, after Alois P. Heinz *)

nmax = 40; CoefficientList[Series[1/(1 - x - x^2) * Product[1/(1 - x^(2*k)), {k, 2, nmax}], {x, 0, nmax}], x] (* Vaclav Kotesovec, Jun 02 2018 *)