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:
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
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Luschny, Jan 29 2024
STATUS
approved