A377168 a(0) = 1, for n > 0 a(n) is defined by a recurrence with brackets matching the n-th Dyck word in lexicographic order, see comments for more details.

1, 1, 2, 1, 3, 2, 2, 2, 2, 4, 3, 3, 3, 3, 3, 2, 3, 1, 1, 3, 1, 1, 1, 5, 4, 4, 4, 4, 4, 3, 4, 2, 2, 4, 2, 2, 2, 4, 3, 3, 3, 3, 4, 3, 2, 3, 3, 2, 3, 3, 2, 4, 3, 2, 3, 3, 2, 3, 2, 1, 2, 2, 1, 2, 1, 6, 5, 5, 5, 5, 5, 4, 5, 3, 3, 5, 3, 3, 3, 5, 4, 4, 4, 4, 5, 4, 3

Offset

0,3

Comments

The transformation from a Dyck word or well-formed bracket expression into a recurrence formula is defined by the ordered steps, "()" -> "(k)" where k is the number of pairs of outer brackets inclosing the brackets in question, then ")(" -> ")+(", and finally "(" -> "a(".

For k > 1, the first occurrence of k occurs at A155587(k)-1.

Links

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

Example

For n = 53 the 53rd Dyck word in lexicographic order is 1110010010 or ((())())() written as a well-formed bracket expression. The first adjacent pair of closed brackets is twice nested, the second pair once, and the last pair is open; giving (((2))(1))(0). Next "+" is added in between each pair of adjacent opposite brackets ")(", and finally "a" is appended to the left of each right bracket "(", yielding the formula a(53) = a(a(a(2)) + a(1)) + a(0).
The formulas for a(n) begin:
 n | n-th Dyck word | a(n)
 0        *           1
 1        ()          a(0)
 2       ()()         a(0)+a(0)
 3       (())         a(a(1))
 4      ()()()        a(0)+a(0)+a(0)
 5      ()(())        a(0)+a(a(1))
 6      (())()        a(a(1))+a(0)
 7      (()())        a(a(1)+a(1))
 8      ((()))        a(a(a(2)))
 9     ()()()()       a(0)+a(0)+a(0)+a(0)
 10    ()()(())       a(0)+a(0)+a(a(1))
 ...

Prog

(Python)
from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A014486_gen():
    return #from Chai Wah Wu, see A014486
def A377168_list(maxn):
    A = [1]
    D = list(islice(A014486_gen(), maxn+1))
    for n in range(1, maxn+1):
        c, c2 = 0, 0
        y = bin(D[n])[2:].replace("1", "u").replace("0", "v")
        z = y
        for i in range(1, len(y)):
            if y[i] == "u":
                c += 1
                if y[i-1] == "v":
                    z = z[:i+c2] + '+' + z[i+c2:]
                    c2 += 1
            else:
                if y[i-1] == "u":
                    z = z[:i+c2] + str(c) + z[i+c2:]
                    c2 += (len(str(c)))
                c -= 1
        A.append(eval(z.replace("u", "A[").replace("v", "]")))
    return(A)

Crossrefs

Cf. A063171 (Dyck words in lexicographic order).

Cf. A000108, A014486, A155587.

Sequence in context: A347240 A308751 A057514 * A273568 A140720 A033559

Adjacent sequences: A377165 A377166 A377167 * A377169 A377170 A377171

Keyword

nonn,easy

Author

John Tyler Rascoe, Oct 18 2024

Status

approved