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

Offset: 0

Author

Gregory L. Simay, Aug 01 2016

Keywords

• nonn

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.

Examples

			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).
		

Links

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

Crossrefs

Cf. A000041, A000045, A275592.

Programs

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 *)

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