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

Author

Peter Luschny, Jan 29 2024

Keywords

• nonn

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).

Examples

			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.
		

Crossrefs

Cf. A011782, A122391, A368279.

Programs

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);

SageMath

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

Formula

a(n) = [x^n] (1 + (x - 1)*(1 + x^2/(2*x - 1) + Sum_{k>=1} x^k/(1 - x*(1 - x^k)/(1 - x)))).

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