Counting De Bruijn sequences as perturbations of linear recursions

2017/05/22 by Don Coppersmith, Coppersmith, Don, Robert C. Rhoades +3
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1705.07835

arxiv created 2017/05/22 · openalex publication_date 2017/05/22 · arxiv updated 2017/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Every binary De~Bruijn sequence of order n satisfies a recursion 0=x_n+x₀+g(x_n-1, ..., x₁). 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 ∑_r N(ℓ; r) y^r when ℓ 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.

Citations

• Fibonacci and Galois representations of feedback-with-carry shift registers

Related

• Multi-Shift de Bruijn Sequence
• New Successor Rules to Efficiently Produce Exponentially Many Binary de Bruijn Sequences
• Cut-Down de Bruijn Sequences
• Efficient generation of odd order de Bruijn sequence with the same complement and reverse sequences
• Counting the spanning trees of a directed line graph