  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.
