Kragujevac J. Math. 24 (2002) 19-41.
ENUMERATING KAUTZ SEQUENCESVladimir 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.
