A330307 Number of circular ternary words of length n having the maximum possible number of distinct blocks of length floor(log_3 n) and floor(log_3 n)+1.

3, 3, 2, 9, 18, 20, 24, 36, 24, 108, 468, 1554, 4308, 10128, 21144, 40080, 68496, 105840, 153120, 206976, 259648, 317952

Offset: 1

Author

Jeffrey Shallit, Dec 10 2019

Keywords

• nonn
• more

Comments

A circular word (a.k.a. "necklace") can be viewed as a representative of the equivalence class under cyclic shift.

The words counted by this sequence have 3^i distinct blocks of length i = floor(log_3 n) and n distinct blocks of length i+1.

This sequence counts a certain natural generalization of ternary de Bruijn words, which are cyclic words of length 3^n containing all n-length blocks as subwords.

Examples

			For n = 5 the 18 strings are those arising from applying all permutations of the alphabet to {00102, 00112, 00121, 00122, 01022, 01102, 01121, 01122, 01211, 01221} and selecting the lexicographically least representative up to shift.
		

Links

• D. Gabric, S. Holub, and J. Shallit, Generalized de Bruijn words and the state complexity of conjugate sets, arXiv:1903.05442 [cs.FL], March 13 2019.

Crossrefs

The ternary analog of A317586.