A368279 a(n) is the number of compositions of n where the first part is the largest part and the last part is not 1. Row sums of A368579.

1, 0, 1, 1, 2, 3, 6, 10, 19, 34, 63, 116, 216, 402, 754, 1417, 2674, 5061, 9608, 18286, 34888, 66706, 127798, 245284, 471561, 907964, 1750695, 3379992, 6533458, 12643162, 24491796, 47490688, 92170704, 179040096, 348064190, 677174709, 1318429534, 2568691317

Offset: 0

Author

Peter Luschny, Jan 04 2024

Keywords

• nonn

Comments

Considering more generally the family of generating functions (1 - x)^n * Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k)) one finds several sequences related to compositions as indicated in the cross-references.

The compositions considered here can also be understood as perfectly balanced, ordered trees. See the linked illustrations. - Peter Luschny, Feb 26 2024

Examples

			a(0) = card({[0]}) = 1.
a(1) = card({}) = 0.
a(2) = card({[2]}) = 1.
a(3) = card({[3]}) = 1.
a(4) = card({[2, 2], [4]}) = 2.
a(5) = card({[2, 1, 2], [3, 2], [5]}) = 3.
a(6) = card({[2, 2, 2], [2, 1, 1, 2], [3, 3], [3, 1, 2], [4, 2], [6]}) = 6.
a(7) = card({[2, 2, 1, 2], [2, 1, 2, 2], [2, 1, 1, 1, 2], [3, 2, 2], [3, 1, 3], [3, 1, 1, 2], [4, 3], [4, 1, 2], [5, 2], [7]}) = 10.
a(8) = card({[2, 2, 2, 2],  [2, 2, 1, 1, 2], [2, 1, 2, 1, 2], [2, 1, 1, 2, 2], [2, 1, 1, 1, 1, 2], [3, 3, 2], [3, 2, 3], [3, 2, 1, 2], [3, 1, 2, 2], [3, 1, 1, 3], [3, 1, 1, 1, 2], [4, 4], [4, 2, 2], [4, 1, 3], [4, 1, 1, 2], [5, 3], [5, 1, 2], [6, 2], [8]}) = 19.
		

Links

• Peter Luschny, A generator for the A368279 compositions.
• Peter Luschny, Some perfectly balanced, ordered trees illustrating A368279.

Crossrefs

Cf. A368579, A369492, A007059, A092921, A188541.

Cf. A369115 (n=-2), A186537 left shifted (n=-1), A079500 (n=0), this sequence (n=1), A369116 (n=2).

Programs

Maple

gf := (1 - x)*sum(x^j / (1 - sum(x^k, k = 1..j)), j = 0..42):
ser := series(gf, x, 40): seq(coeff(ser, x, n), n = 0..37);
# Peter Luschny, Jan 19 2024

Python

from functools import cache
@cache
def F(k, n):
    return sum(F(k,n-j) for j in range(1,min(k,n))) if n>1 else n
def a(n): return sum(F(k+1, n+1-k) - F(k+1, n-k) for k in range(n+1))
print([a(n) for n in range(38)])

SageMath

def C(n): return sum(Compositions(n, max_part=k, inner=[k]).cardinality()
                 for k in (0..n))
def a(n): return C(n) - C(n-1) if n > 1 else 1 - n
print([a(n) for n in (0..28)])

Formula

a(n) = Sum_{k=0..n} (F(k+1, n+1-k) - F(k+1, n-k)) where F(k, n) = Sum_{j=1..min(k, n)} F(k, n-j) if n > 1 and otherwise n. F(k, n) refers to the generalized Fibonacci number A092921.

a(n) = A007059(n+1) - A007059(n).

G.f.: (1 - x)*(Sum_{j>=0} (x^j / (1 - Sum_{k=1..j} x^k ))) = (1 - x) * GfA079500. - Peter Luschny, Jan 20 2024