A369584 a(n) = 2^(n - 3) - A368279(n) for n >= 5, otherwise 0. Number of compositions of n whose first and last part is not equal to 1 and whose first part is not the largest part.

0, 0, 0, 0, 0, 1, 2, 6, 13, 30, 65, 140, 296, 622, 1294, 2679, 5518, 11323, 23160, 47250, 96184, 195438, 396490, 803292, 1625591, 3286340, 6637913, 13397224, 27020974, 54465702, 109725932, 220944768, 444700208, 894701728, 1799419458, 3617792587, 7271505058

Offset

0,7

Comments

We consider a tripartition of the compositions of an integer n >= 1, which we sort in lexicographic order. For this purpose, we define three predicates for a composition C.

(1) The first part of C is the largest part of C.

(2) The first part of C is 1.

(3) The last part of C is 1.

We thus define three classes of compositions:

X(n): compositions for which (1) and not (3) applies;

Y(n): compositions for which (2) or (3) applies;

Z(n): compositions for which not (1) and not (2) and not (3) applies.

X(n), Y(n), and Z(n) are disjoint classes whose union comprises all compositions of n; they thus form a disjoint tripartition of the compositions of n. The number of these compositions are given by:

card(Z(n)) = a(n); card(X(n)) = A368279(n); card(Y(n)) = A122391(n).

Links

Table of n, a(n) for n=0..36.

Formula

a(n) = [x^n] (1 + (x - 1)*(1 + x^2/(2*x - 1) + sum(x^n/(1 - x*(1 - x^n)/(1 - x))).

card(X(n)) + card(Y(n)) + card(Z(n)) = A011782(n) = 2^(n - 1) for n > 0.

Example

The compositions of class Z(n) for n = 5..7 are:
5: [2, 3];
6: [2, 1, 3], [2, 4];
7: [2, 1, 1, 3], [2, 1, 4], [2, 2, 3], [2, 3, 2], [2, 5], [3, 4].
The cardinalities of some tripartitions, |X(n)| + |Y(n)| + |Z(n)| = 2^(n - 1):
 5:  12 +  3 +  1 =  16;
 6:  24 +  6 +  2 =  32;
 7:  48 + 10 +  6 =  64;
 8:  96 + 19 + 13 = 128;
 9: 192 + 34 + 30 = 256;
10: 384 + 63 + 65 = 512.

Maple

gf := 1 + (x - 1)*(1 + x^2 / (2*x - 1) + sum(x^n / (1 - x*(1 - x^n)/(1 - x)),
n = 1..42)): ser := series(gf, x, 40): seq(coeff(ser, x, n), n = 0..36);

Prog

(SageMath)
def A369584(n):
    if n < 5: return 0
    return 2^(n - 3) - A368279(n)
print([A369584(n) for n in range(37)])

Crossrefs

Cf. A011782, A122391, A368279.

Sequence in context: A297388 A115217 A094687 * A336875 A219753 A239305

Adjacent sequences: A369581 A369582 A369583 * A369585 A369586 A369587

Keyword

nonn

Author

Peter Luschny, Jan 29 2024

Status

approved