EUVIMEDSkopri EUVIMED
Crossref

Phased Multi de Bruijn Sequences

Glenn Tesler

The Electronic Journal of Combinatorics · 2026-04-14 · 33 (2)

DOI: 10.37236/11405 ↗

At a glance

Journal article in The Electronic Journal of Combinatorics, published online on 2026-04-14. Written by Glenn Tesler.

AstrattDettalji biblijografiċiCiteRelated studies

Abstract (original language)

We introduce phased multi de Bruijn sequences, a generalization of de Bruijn sequences. A phased string is a string whose positions sequentially rotate through several alphabets; e.g., “0Ax1Ay1By0Az1Bx” rotates through alphabets $\Omega_0=\{0,1\}$, $\Omega_1=\{A,B\}$, and $\Omega_2=\{x,y,z\}$. We consider cyclic and linear phased strings in which all possible phased $k$-mers (phased strings of length $k$) occur with particular multiplicities, depending on their “phase” (the alphabet they start in). For example, consider the cycle (s)=(0Ax1Ay1By0Az0By1Bx0Ay0Bx1Bz1Ax0Bz1Az) in these alphabets. All possible phased 2-mers starting in phases 0, 1, and 2 respectively have multiplicities 3, 2, and 2; e.g., “0A” occurs three times, “Ax” occurs twice, and “z0” occurs twice (including the occurrence that wraps around the cycle). We determine parameters ($k$, number of phases, alphabet sizes, and multiplicities) for which this is possible. Then we count the total number of phased multi de Bruijn sequences for these parameters, both for cyclic and linear sequences. This extends classical de Bruijn sequences and multi de Bruijn sequences (our previous generalization of de Bruijn sequences in which all possible $k$-mers over one alphabet occur $m$ times each). Our method of counting the sequences uses a change of basis for the Laplacian matrix; this also gives a new proof for the number of classical de Bruijn sequences, as they are a special case of this framework.

Cite

APA

Tesler, G. (2026). Phased Multi de Bruijn Sequences. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/11405

Vancouver

Tesler G. Phased Multi de Bruijn Sequences. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/11405

BibTeX
@article{Tesler2026,
  author = {Tesler, Glenn},
  title = {Phased Multi de Bruijn Sequences},
  journal = {The Electronic Journal of Combinatorics},
  year = {2026},
  volume = {33},
  number = {2},
  doi = {10.37236/11405}
}
Start for free →