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,1

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.

Links

Table of n, a(n) for n=1..22.

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.

Example

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.

Crossrefs

The ternary analog of A317586.

Sequence in context: A202699 A058137 A250304 * A256916 A164705 A073754

Adjacent sequences: A330304 A330305 A330306 * A330308 A330309 A330310

Keyword

nonn,more

Author

Jeffrey Shallit, Dec 10 2019

Status

approved