9
$\begingroup$

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$.

In Section 2c of Fredricksen's paper A survey of full length nonlinear shift register cycle algorithms (SIAM Review 24 (1982), 195–221), he states a result that he attributes to "Kibler, personal communication, 1972":

Theorem. The number of cycles of length $2^n-2$ in the De Bruijn graph of order $n$ is ${1\over 3}(2^{2^n-2n})(2^{n-1} + (-1)^n)$.

However, he gives only the bare outline of a proof. By appealing to the BEST theorem, he reduces the calculation to a determinant evaluation, and then simply says, "By induction, the determinant can be evaluated." However, I don't see how to do this.

Can someone explain how to evaluate the determinant, or give an alternative proof of the above fact?

$\endgroup$
2

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.