A331606 Number of compositions of n with the multiplicity of the first part odd.

1, 1, 4, 4, 12, 18, 44, 72, 158, 288, 604, 1146, 2332, 4528, 9126, 17944, 35940, 71130, 142132, 282344, 563630, 1121936, 2239060, 4462530, 8906236, 17764160, 35458774, 70761520, 141272876, 282025466, 563159588, 1124543256, 2245918406, 4485670168, 8960061076

Offset: 1

Author

Arnold Knopfmacher, Jan 22 2020

Keywords

• nonn

Examples

			For n=3, a(4)=4 as we count 4, 3+1, 1+3 and 2+1+1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• M. Archibald, A. Blecher, A. Knopfmacher, M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.

Crossrefs

Cf. A011782, A331609 (similar, with even).

Programs

Maple

b:= proc(n, p, t) option remember; `if`(n=0, t,
      add(b(n-j, p, `if`(p=j, 1-t, t)), j=1..n))
    end:
a:= n-> add(b(n-j, j, 1), j=1..n):
seq(a(n), n=1..38);  # Alois P. Heinz, Jan 23 2020

Mathematica

gf[x_] := x/(2 (1 - 2 x)) + Sum[(1 - x) x^i/(2 (-2 x^(i + 1) + 2 x^i - 2 x + 1))  , {i, 1, 40}]; CL := CoefficientList[Series[gf[x], {x, 0, 35}], x];
Drop[CL, 1] (* Peter Luschny, Jan 23 2020 *)

Formula

G.f.: Sum_{i>=1} (1-x)*x^i/(2*(-2*x^(i+1)+2*x^i-2*x+1)) + x/(2*(1-2*x)).

a(n) = A011782(n) - A331609(n). - Alois P. Heinz, Jan 23 2020