login
A345199
Number of distinct length-2n blocks in the Thue-Morse sequence (A010060) that are Dyck words.
0
1, 1, 2, 3, 2, 4, 6, 6, 4, 8, 8, 8, 12, 9, 12, 13, 8, 14, 16, 14, 16, 18, 16, 18, 24, 20, 18, 22, 24, 20, 26, 26, 16, 28, 28, 24, 32, 28, 28, 32, 32, 32, 36, 36, 32, 40, 36, 36, 48, 37, 40, 45, 36, 45, 44, 41, 48, 45, 40, 45, 52, 41, 52, 53, 32, 54, 56, 46, 56
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
Sequence in context: A128502 A349382 A244306 * A079159 A192298 A341098
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Jun 10 2021
STATUS
approved