Enumeration of Both-Ends-Fixed k-ary Necklaces and Its Applications

摘要

We consider both-ends-fixed -ary necklaces and enumerateall such necklaces of length from the viewpoints of symbolic dynamicsand -expansions, where and (≥ 2) are natural numbers and (> 1) isa real number. Recently, Sawada et al. proposed an efficient constructionof -ary de Bruijn sequence of length , which for each ≥ 1, requires ( ) space but generates a single -ary de Bruijn sequence of length in (1)-amortized time per bit. Based on the enumeration of both-ends-fixed -ary necklaces of length , we evaluate auto-correlation values of the -ary de Bruijn sequences of length constructed by Sawada et al. We alsoestimate the asymptotic behaviour of the obtained auto-correlation valuesas tends to infinity.