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

Crossrefs

Cf. A000041, A000045, A275592.

Sequence in context: A062114 A094768 A301753 * A260710 A359994 A093830

Adjacent sequences: A275545 A275546 A275547 * A275549 A275550 A275551

Keyword

nonn

Author

Gregory L. Simay, Aug 01 2016

Status

approved