login
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.
6
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,5
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
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
EXAMPLE
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.
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
PROG
(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)])
CROSSREFS
Cf. A369115 (n=-2), A186537 left shifted (n=-1), A079500 (n=0), this sequence (n=1), A369116 (n=2).
Sequence in context: A374690 A291875 A227309 * A374631 A123916 A000693
KEYWORD
nonn
AUTHOR
Peter Luschny, Jan 04 2024
STATUS
approved