OFFSET
0,4
COMMENTS
A well-formed bracketed word is a properly nested word using the symbol * together with three types of matching unary brackets; the condition "no empty bracket pair" means that every matching bracket pair encloses at least one symbol.
Under this interpretation there is no object of total length 0, hence the sequence is naturally indexed from n=1.
Equivalently, a(n) is the number of operator monomials of total length n generated from one indeterminate * by associative multiplication and three noncommuting unary operators P_1, P_2, P_3, where * has length 1 and each application of P_i contributes 2 to the total length.
Equivalently, for n>=1, a(n) counts peakless Motzkin paths of length n with 3-colored up steps; here "peakless" means that the path contains no occurrence of UD.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1791
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, 9 (Table 2).
FORMULA
G.f.: 1 + A(x) satisfies A(x) = x + x*A(x) + 3*x^2*A(x) + 3*x^2*A(x)^2.
G.f.: 1 + (1 - x - 3*x^2 - sqrt((1 - x - 3*x^2)^2 - 12*x^3))/(6*x^2).
a(n) = Sum_{k=0..floor((n-1)/2)} 3^k*N(n-k,k), where N(m,k) = A001263(m,k) = binomial(m,k)*binomial(m,k+1)/m are the Narayana numbers.
a(0)=a(1)=1; for n>=2, a(n) = a(n-1) + 3*a(n-2) + 3*Sum_{i=1..n-3} a(i)*a(n-2-i), with a(m)=0 for m<=0.
a(n) = Sum_{k>=0} 3^k * A089732(n,k). - Alois P. Heinz, Apr 12 2026
EXAMPLE
For n=4, a(4)=10. In bracketed-word form (using () for P_1, [] for P_2, and {} for P_3), the 10 objects are ****, (*)*, *(*), (**), [*]*, *[*], [**], {*}*, *{*}, {**}.
MAPLE
a:= proc(n) option remember; `if`(n<4, [1$3, 4][n+1], (-9*(n-4)*a(n-4)+
3*(2*n-5)*a(n-3)+5*(n-1)*a(n-2)+(2*n+1)*a(n-1))/(n+2))
end:
seq(a(n), n=0..29); # Alois P. Heinz, Apr 08 2026
PROG
(PARI) apply( {A394940(n)=sum(k=0, n\/2, 3^k * A089732(n, k))}, [0..30]) \\ Somewhat inefficient with current code for A089732, better compute entire rows. M. F. Hasler, Apr 13 2026
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Yu Hin Au, Apr 08 2026
STATUS
approved