OFFSET
0,3
COMMENTS
A Dyck word is a binary word representing a string of balanced parentheses, with 0 the left parenthesis and 1 the right parenthesis.
It is a 2-regular sequence and obeys the following relations:
a(4n+2) = 2a(2n+1);
a(8n+1) = 3a(2n+1) - (1/2) a(4n) + a(4n+1) - a(4n+3) + (1/2) a(8n);
a(8n+3) = -a(2n+1) -(1/2) a(4n) + a(4n+1) + a(4n+3) + (1/2) a(8n);
a(8n+4) = 4a(2n+1) - 4a(4n) + 2a(8n);
a(8n+5) = -a(2n) -3a(2n+1) + 2a(4n+1) + 2a(4n+3);
a(8n+7) = -a(2n) + a(2n+1) + 2a(4n+3);
a(16n) = -2a(4n) + 3a(8n);
a(16n+8) = 8a(2n+1) - 8a(4n) + 4a(8n).
LINKS
Lucas Mol, Narad Rampersad, and Jeffrey Shallit, Dyck Words, Pattern Avoidance, and Automatic Sequences, arXiv:2301.06145 [cs.DM], 2023.
EXAMPLE
For n = 5 the 4 Dyck words of length 10 appearing in the Thue-Morse word are {0011001011, 0010110011, 0011010011, 0100101101}.
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jun 10 2021
STATUS
approved