A394942 Number of well-formed bracketed words of total length n built from the symbol * (of length 1) and two unary bracket types () and [], with no empty bracket pair, where every maximal chain of unary brackets is written in canonical weakly increasing order.

1, 1, 1, 3, 7, 16, 42, 109, 289, 787, 2162, 6013, 16901, 47872, 136602, 392275, 1132674, 3286790, 9579725, 28031888, 82320819, 242538673, 716708853, 2123672215, 6308410522, 18782623833, 56043067377, 167552256398, 501859077675, 1505784274718, 4525272671985

Offset

0,4

Comments

a(0)=1 counts the empty word.

For n>=1, a(n)=b_{2,1}^c(n) in the notation of Au and Bremner; see Section 3.

Equivalently, a(n) counts canonical representatives of such bracketed words under commutativity of the two unary bracket types.

In each maximal chain of nested unary brackets, the bracket types are weakly increasing from outermost to innermost.

Equivalently, a(n) counts rooted ordered trees in which each leaf represents *, each unary internal node is labeled 1 or 2, every non-unary internal node has at least 2 ordered children, and the labels along every maximal unary chain are weakly increasing from the root toward the leaves.

Equivalently, a(n) counts peakless Motzkin paths of length n with two types of up-steps U_1 and U_2, such that along every matched ascent the labels are weakly increasing.

Here a matched ascent is a maximal consecutive block of up-steps whose matching down-steps all belong to the same descent.

Links

Table of n, a(n) for n=0..30.

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, 19 (Table 4).

Formula

G.f.: 1 + (1 - x - 2*x^2 + x^4 - sqrt((1-x-2*x^2+x^4)^2 - 4*x*(2*x^2 - x^4))) / (2*(2*x^2 - x^4)) = 1 + A(x).

G.f. satisfies A(x) = x + x*A(x) + (2*x^2 - x^4)*(A(x) + A(x)^2).

a(n) = f(n-1) + 2*f(n-2) - f(n-4) + 2*Sum_{k=1..n-3} a(k)*a(n-2-k) - Sum_{k=1..n-5} a(k)*a(n-4-k) with a(0)=a(1)=1 where f(n)=a(n) for n>=1 and f(n)=0 for n<=0.

Example

a(5)=16. The 16 canonical bracketed words are *****, (**)*, *(**), (***), [**]*, *[**], [***], (*)**, *(*)*, **(*), [*]**, *[*]*, **[*], ((*)), ([*]), [[*]].

Crossrefs

Cf. A004148, A394943, A394944, A394939.

Sequence in context: A036567 A018023 A144977 * A058300 A000674 A129045

Adjacent sequences: A394939 A394940 A394941 * A394943 A394944 A394945

Keyword

nonn,easy

Author

Yu Hin Au, Apr 30 2026

Status

approved