OFFSET
0,3
COMMENTS
Previous name was: A simple grammar.
a(n) is the number of ordered rooted trees with node weights summing to n. Where the root has weight 0, non-root nodes are each labeled with a subset s of [n] with weight |s|, and the labels of a given tree form a set partition of [n]. - John Tyler Rascoe, Feb 28 2026
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..200
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 871
FORMULA
E.g.f.: (1/2)/(exp(x) - 1)*(1 - (5 - 4*exp(x))^(1/2)).
a(n) = Sum_{k=0..n} k!*Stirling2(n,k)*Catalan(k). - Vladimir Kruchinin, Sep 15 2010
a(n) ~ sqrt(10)*n^(n-1) / (exp(n)*(log(5/4))^(n-1/2)). - Vaclav Kotesovec, Sep 30 2013
E.g.f.: 1/(1 + (1 - exp(x))/(1 + (1 - exp(x))/(1 + (1 - exp(x))/(1 + (1 - exp(x))/(1 + ...))))), a continued fraction. - Ilya Gutkovskiy, Nov 18 2017
From Peter Bala, Jan 15 2018: (Start)
E.g.f.: C(exp(x) - 1), where C(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. for A000108. Cf. A006531.
Conjecture: for fixed k = 1,2,..., the sequence a(n) (mod k) is eventually periodic with the exact period dividing phi(k), where phi(k) is the Euler totient function A000010. For example, modulo 10 the sequence becomes (1, 1, 5, 3, 5, 1, 5, 3, 5, ...), with an apparent period 1, 5, 3, 5 of length 4 = phi(10) beginning at a(1). (End)
O.g.f.: 1 + Sum_{k>=1} A000108(k)*Product_{r=1..k} r*x/(1 - r*x). - Petros Hadjicostas, Jun 12 2020
MAPLE
spec := [S, {C=Set(Z, 1 <= card), S=Sequence(B), B=Prod(C, S)}, labeled]: seq(combstruct[count](spec, size=n), n=0..20);
MATHEMATICA
CoefficientList[Series[(1/2)/(E^x-1)*(1-(5-4*E^x)^(1/2)), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Sep 30 2013 *)
a[n_] = Sum[k! StirlingS2[n, k] CatalanNumber[k], {k, 0, n}];
Table[a[n], {n, 0, 17}] (* Peter Luschny, Jan 15 2018 *)
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
INRIA Encyclopedia of Combinatorial Structures, Jan 25 2000
EXTENSIONS
New name using e.g.f. from Vaclav Kotesovec, Sep 30 2013
STATUS
approved