cp's OEIS Frontend

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.

%I A377168 #19 Nov 01 2024 09:35:38
%S A377168 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 A377168 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 A377168 5,5,5,4,5,3,3,5,3,3,3,5,4,4,4,4,5,4,3
%N 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.
%C A377168 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 A377168 For k > 1, the first occurrence of k occurs at A155587(k)-1.
%e A377168 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 A377168 The formulas for a(n) begin:
%e A377168  n | n-th Dyck word | a(n)
%e A377168  0        *           1
%e A377168  1        ()          a(0)
%e A377168  2       ()()         a(0)+a(0)
%e A377168  3       (())         a(a(1))
%e A377168  4      ()()()        a(0)+a(0)+a(0)
%e A377168  5      ()(())        a(0)+a(a(1))
%e A377168  6      (())()        a(a(1))+a(0)
%e A377168  7      (()())        a(a(1)+a(1))
%e A377168  8      ((()))        a(a(a(2)))
%e A377168  9     ()()()()       a(0)+a(0)+a(0)+a(0)
%e A377168  10    ()()(())       a(0)+a(0)+a(a(1))
%e A377168  ...
%o A377168 (Python)
%o A377168 from itertools import count, islice
%o A377168 from sympy.utilities.iterables import multiset_permutations
%o A377168 def A014486_gen():
%o A377168     return #from _Chai Wah Wu_, see A014486
%o A377168 def A377168_list(maxn):
%o A377168     A = [1]
%o A377168     D = list(islice(A014486_gen(),maxn+1))
%o A377168     for n in range(1,maxn+1):
%o A377168         c,c2 = 0,0
%o A377168         y = bin(D[n])[2:].replace("1","u").replace("0","v")
%o A377168         z = y
%o A377168         for i in range(1,len(y)):
%o A377168             if y[i] == "u":
%o A377168                 c += 1
%o A377168                 if y[i-1] == "v":
%o A377168                     z = z[:i+c2] + '+' + z[i+c2:]
%o A377168                     c2 += 1
%o A377168             else:
%o A377168                 if y[i-1] == "u":
%o A377168                     z = z[:i+c2] + str(c) + z[i+c2:]
%o A377168                     c2 += (len(str(c)))
%o A377168                 c -= 1
%o A377168         A.append(eval(z.replace("u","A[").replace("v","]")))
%o A377168     return(A)
%Y A377168 Cf. A063171 (Dyck words in lexicographic order).
%Y A377168 Cf. A000108, A014486, A155587.
%K A377168 nonn,easy
%O A377168 0,3
%A A377168 _John Tyler Rascoe_, Oct 18 2024