Kragujevac J. Math. 24 (2002) 19-41.

ENUMERATING KAUTZ SEQUENCES

Vladimir Raphael Rosenfeld

Institute of Evolution, University of Haifa, Mount Carmel, Haifa 31905, Israel
(e-mail: vladimir@research.haifa.ac.il)

(Received August 5, 2002)

Abstract. A Kautz s-ary closed sequence is a circular sequence of l s-ary digits 0,1,...,s-1 such that consecutive digits are distinct and all subsequences of length q are distinct, too [3]. Kautz sequences (of the maximal length s(s-1)q-1) can also be represented by the series Hs={Hs,q}q=1¥ (s ³ 2) of Kautz digraphs [3]. Namely, Hs,1=Ks, where Ks is a complete s-vertex digraph without self-loops, and Hs,q+1=G(Hs,q)=GqKs, where G is the operator transforming an arbitrary (di-)graph G into its arc-graph G(G) [8].

Under s,q ³ 2, the number of the Kautz sequences of the maximal length s(s-1)q-1 is proven to equal ss-2[(s-1)!]s(s-1)q-2/(s-1)s+q-2. The demonstration is based on our recent results concerning the characteristic polynomial and permanent of the arc-graph [8], applied herein to the Kautz digraphs.

Wherever possible, the main subject is discussed in the wider context of related combinatorial problems, which first includes counting the linear Kautz sequences, whose number under the maximal length s(s-1)q-1+q-1 is equal to ss-1[(s-1)!]s(s-1)q-2/(s-1)s-1.

Obtained results can be used for calculating the number of monocyclic and linear compounds, formed from s sorts of atoms, obeying the specified combinatorial restrictions. The former is equivalent to finding the number of respective necklaces with s kinds of beads.