A377168 - OEIS

%I #19 Nov 01 2024 09:35:38

%S 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,

%T 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,

%U 5,5,5,4,5,3,3,5,3,3,3,5,4,4,4,4,5,4,3

%N 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.

%C 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(".

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

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

%e The formulas for a(n) begin:

%e  n | n-th Dyck word | a(n)

%e  0        *           1

%e  1        ()          a(0)

%e  2       ()()         a(0)+a(0)

%e  3       (())         a(a(1))

%e  4      ()()()        a(0)+a(0)+a(0)

%e  5      ()(())        a(0)+a(a(1))

%e  6      (())()        a(a(1))+a(0)

%e  7      (()())        a(a(1)+a(1))

%e  8      ((()))        a(a(a(2)))

%e  9     ()()()()       a(0)+a(0)+a(0)+a(0)

%e  10    ()()(())       a(0)+a(0)+a(a(1))

%e  ...

%o (Python)

%o from itertools import count, islice

%o from sympy.utilities.iterables import multiset_permutations

%o def A014486_gen():

%o     return #from _Chai Wah Wu_, see A014486

%o def A377168_list(maxn):

%o     A = [1]

%o     D = list(islice(A014486_gen(),maxn+1))

%o     for n in range(1,maxn+1):

%o         c,c2 = 0,0

%o         y = bin(D[n])[2:].replace("1","u").replace("0","v")

%o         z = y

%o         for i in range(1,len(y)):

%o             if y[i] == "u":

%o                 c += 1

%o                 if y[i-1] == "v":

%o                     z = z[:i+c2] + '+' + z[i+c2:]

%o                     c2 += 1

%o             else:

%o                 if y[i-1] == "u":

%o                     z = z[:i+c2] + str(c) + z[i+c2:]

%o                     c2 += (len(str(c)))

%o                 c -= 1

%o         A.append(eval(z.replace("u","A[").replace("v","]")))

%o     return(A)

%Y Cf. A063171 (Dyck words in lexicographic order).

%Y Cf. A000108, A014486, A155587.

%K nonn,easy

%O 0,3

%A _John Tyler Rascoe_, Oct 18 2024