Counting De Bruijn sequences as perturbations of linear recursions
From MaRDI portal
Publication:6286973
arXiv1705.07835MaRDI QIDQ6286973FDOQ6286973
Authors: Don Coppersmith, Robert C. Rhoades, Jeffrey M. Vanderkam 
Publication date: 22 May 2017
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.
This page was built for publication: Counting De Bruijn sequences as perturbations of linear recursions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6286973)
