A368484 Number of compositions (ordered partitions) of n into parts not greater than n/2.

1, 0, 1, 1, 5, 8, 24, 44, 108, 208, 464, 912, 1936, 3840, 7936, 15808, 32192, 64256, 129792, 259328, 521472, 1042432, 2091008, 4180992, 8375296, 16748544, 33525760, 67047424, 134156288, 268304384, 536739840, 1073463296, 2147205120, 4294377472, 8589344768

Offset: 0

Author

Ilya Gutkovskiy, Dec 26 2023

Keywords

• nonn
• easy

Links

• Index entries for sequences related to compositions
• Index entries for linear recurrences with constant coefficients, signature (2,4,-8,-4,8).

Crossrefs

Cf. A011782, A110618, A258259.

Programs

Mathematica

CoefficientList[Series[(1 - 2 x - 3 x^2 + 7 x^3 + 3 x^4 - 6 x^5)/((1 - 2 x) (1 - 2 x^2)^2), {x, 0, 34}], x]
Join[{1}, LinearRecurrence[{2, 4, -8, -4, 8}, {0, 1, 1, 5, 8}, 34]]

Formula

G.f.: (1 - 2*x - 3*x^2 + 7*x^3 + 3*x^4 - 6*x^5) / ((1 - 2*x) * (1 - 2*x^2)^2).

a(n) = [x^n] 1 / (1 - Sum_{1 <= j <= n/2} x^j).