A345199 Number of distinct length-2n blocks in the Thue-Morse sequence (A010060) that are Dyck words.

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

Table of n, a(n) for n=0..68.

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

Cf. A010060, A063171.

Sequence in context: A128502 A349382 A244306 * A079159 A192298 A341098

Adjacent sequences: A345196 A345197 A345198 * A345200 A345201 A345202

Keyword

nonn

Author

Jeffrey Shallit, Jun 10 2021

Status

approved