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
LINKS
Peter Luschny, A generator for the A368279 compositions.
Peter Luschny, Some perfectly balanced, ordered trees illustrating A368279.
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.
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
KEYWORD
nonn
AUTHOR
Peter Luschny, Jan 04 2024
STATUS
approved