A343484 Number of equivalence classes of length n squarefree reduced words over {0, 1, 2, 3} under action of renaming symbols.

0, 1, 1, 2, 3, 5, 8, 13, 18, 27, 41, 62, 90, 134, 198, 293, 423, 619, 908, 1329, 1938, 2832, 4142, 6061, 8824, 12879, 18794, 27425, 39977, 58333, 85109, 124180, 180994, 263931, 384933, 561402, 818617, 1193841, 1740980, 2538896, 3702022, 5398458, 7872351

Offset

0,4

Comments

Any equivalence class of words with length at least 2 has exactly 8 members.

Links

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

Richard A. Dean, A sequence without repeats on x, x^{-1}, y, y^{-1}, Amer. Math. Monthly 72, 1965. pp. 383-385. MR 31 #350.

Tero Harju, Avoiding Square-Free Words on Free Groups, arXiv:2104.06837 [math.CO], 2021.

Formula

a(n) = A343421(n)/8 for n >= 2.

Example

a(5) = 5 corresponds to the 5 words 01210, 01030, 01230, 01032, and 01232.

Crossrefs

Cf. A215075, A343421.

Sequence in context: A001149 A144117 A081612 * A374737 A301754 A120761

Adjacent sequences: A343481 A343482 A343483 * A343485 A343486 A343487

Keyword

nonn

Author

James Rayman, Apr 16 2021

Status

approved