OFFSET
0,3
COMMENTS
a(0)=1 counts the empty word.
For n>=1, a(n)=b_{2,2}^{cm}(2n) in the notation of Au and Bremner; see Section 4.2.
Here two bracketed words are equivalent if they differ only by permuting factors in any concatenation.
In each maximal chain of nested unary brackets, the bracket types are weakly increasing from outermost to innermost.
Equivalently, a(n) counts rooted unordered trees with n vertices in which each leaf represents *, each unary internal node is labeled 1 or 2, every non-unary internal node has at least 2 unordered children, and the labels along every maximal unary chain are weakly increasing from the root toward the leaves.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Yu Hin Au and Murray R. Bremner, Enumerating Multi-Operator Monomials in Commutative and Noncommutative Settings, arXiv:2604.25731 [math.CO], 2026. See pp. 4, 30 (Table 8).
FORMULA
G.f.: 1 + A(x) = exp(Sum_{k>=1} (x^k + (2*x^k - x^(2*k))*A(x^k))/k).
n*a(n) = c(n) + Sum_{k=1..n-1} c(k)*a(n-k) for n>1, with a(0)=a(1)=1, where c(n) = Sum_{m|n} m*b(m), b(1)=1, and b(n) = Sum_{j=1..min(2,n-1)} (-1)^(j+1)*binomial(2,j)*a(n-j) for n>=2.
EXAMPLE
a(3)=8. Representatives for the 8 equivalence classes are ***, (**), [**], (*)*, [*]*, ((*)), ([*]), [[*]].
MATHEMATICA
nn=30; a={1, 1}; Do[b[m_]:=If[m==1, 1, Sum[(-1)^(j+1) Binomial[2, j] a[[m-j+1]], {j, 1, Min[4, m-1]}]];
c[t_]:=Sum[d*b[d], {d, Divisors[t]}]; AppendTo[a, (c[n]+Sum[c[k] a[[n-k+1]], {k, 1, n-1}])/n]; , {n, 2, nn}]; a (* Vincenzo Librandi, May 02 2026 *)
PROG
(Magma) N:=30; a:=[1, 1]; for n in [2..N] do b:=func<m|m eq 1 select 1 else &+[(-1)^(j+1)*Binomial(2, j)*a[m-j+1]: j in [1..Minimum(4, m-1)]]>; c:=func<t|&+[d*b(d): d in Divisors(t)]>; Append(~a, (c(n)+&+[c(k)*a[n-k+1]: k in [1..n-1]]) div n); end for; a; // Vincenzo Librandi, May 02 2026
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Yu Hin Au, Apr 30 2026
STATUS
approved