Counting De Bruijn sequences as perturbations of linear recursions

Abstract

Every binary De~Bruijn sequence of order n satisfies a recursion 0=x_n+x_0+g(x_{n-1}, ..., x_1). Given a function f on (n-1) bits, let N(f; r) be the number of functions generating a De Bruijn sequence of order n which are obtained by changing r locations in the truth table of f. We prove a formula for the generating function \sum_r N(\ell; r) y^r when \ell is a linear function. The proof uses a weighted Matrix Tree Theorem and a description of the in-trees (or rooted trees) in the n-bit De Bruijn graph as perturbations of the Hamiltonian paths in the same graph.