Onion De Bruijn Sequences: Fixed-Window Counting by Growing the Alphabet
This work formalizes a novel counting system for De Bruijn sequences, offering theoretical foundations and efficient algorithms for enumeration and arithmetic, which may benefit combinatorial generation and coding theory.
The paper introduces onion De Bruijn sequences, a fixed-window counting system with a growing alphabet, and proves structural properties including an explicit product formula for counting compatible finite prefixes. For orders n=2 and 3, it provides rank/unrank formulas and arithmetic operations with linear carry complexity.
We study a fixed-window counting system in which integers are represented by words of constant length while the alphabet grows as needed. This viewpoint arises from De Bruijn sequences: for fixed order $n$, the reverse prefer-max sequence is compatible with alphabet growth, since for each $k$ its restriction to $[k]^n$ is a De Bruijn sequence, yielding an infinite sequence over $\mathbb{N}$. We formalize this through the notion of an onion De Bruijn sequence, prove the resulting structural properties, and count compatible finite onion prefixes by an explicit product formula. For orders $n=2,3$, we give explicit rank and unrank formulas and describe addition and multiplication via finite normalization, with exact carry counts and linear carry complexity in the input layers.