A275592 Number of compositions of n if only the order of the even numbers matter.

1, 1, 2, 3, 5, 7, 12, 16, 26, 35, 56, 74, 117, 154, 241, 317, 492, 645, 998, 1306, 2014, 2634, 4053, 5296, 8139, 10630, 16321, 21310, 32699, 42684, 65472, 85452, 131038, 171012, 262198, 342161, 524552, 684497, 1049300, 1369216, 2098849, 2738710, 4198011

Offset

0,3

Comments

The number of compositions of n = 2k with only even numbers is c(k) = A011782(k). The number of partitions of n with only odd numbers is the strict partition q(n) = A000009(n). Enumerating a(n) is therefore a sum of products of composition numbers and strict partition numbers. (See formulas.)

Links

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

Formula

a(2k+1) = Sum_{j=0..k} c(j)*q(2k+1-2j), where c(j) = A011782(j), the number of compositions of j, and q(j) = A000009(j), the number of strict partitions of j.

a(2k) = Sum_{j=0..k} c(j)*q(2k - 2j).

a(n) = 2*a(n-2) + q(n) - q(n-2).

G.f.: (1 - x^2)/(1 - 2*x^2) * Product_{n>=1} (1 + x^n). - Peter Bala, Aug 03 2016

a(n) ~ c * 2^(n/2), where c = (QPochhammer[-1, 1/sqrt(2)] + (-1)^n*QPochhammer[-1, -1/sqrt(2)])/8, c = 2.002012668882683075956932277149607919866122388... if n is even and c = 1.8471591618236152130512812517147483461076894... if n is odd. - Vaclav Kotesovec, Jun 02 2018

Example

The compositions enumerated by a(6) = 12 are (6), (5,1)=(1,5), (4,2), (2,4), (3,3), (4,1,1)=(1,4,1)=(1,1,4), (3,2,1)=(1,2,3)=(2,3,1)=(2,1,3)=(3,1,2)=(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) = 7 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::even)
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Aug 03 2016

Mathematica

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

Crossrefs

Cf. A000009, A011782, A275548.

Sequence in context: A373297 A308271 A360622 * A319635 A179822 A319769

Adjacent sequences: A275589 A275590 A275591 * A275593 A275594 A275595

Keyword

nonn

Author

Gregory L. Simay, Aug 02 2016

Status

approved