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

Author

John Tyler Rascoe, Oct 18 2024

Keywords

• nonn
• easy

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.

Examples

			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))
 ...
		

Crossrefs

Cf. A063171 (Dyck words in lexicographic order).

Cf. A000108, A014486, A155587.

Programs

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)