比利时vs摩洛哥足彩
,
university of california san diego
****************************
math 269 - combinatorics
glenn tesler
ucsd
multi de bruijn sequences
abstract:
we generalize the notion of a de bruijn sequence to a ``multi de bruijn sequence'': a cyclic or linear sequence that contains every $k$-mer over an alphabet of size $q$ exactly $m$ times. for example, over the binary alphabet $\{0,1\}$, the cyclic sequence $(00010111)$ and the linear sequence $000101110$ each contain two instances of each $2$-mer $00,01,10,11$. we derive formulas for the number of such sequences. the formulas and derivation generalize classical de bruijn sequences (the case $m=1$). we also determine the number of multisets of aperiodic cyclic sequences containing every $k$-mer exactly $m$ times; for example, the pair of cyclic sequences $(00011)(011)$ contains two instances of each $2$-mer listed above. this uses an extension of the burrows-wheeler transform due to mantaci et al., and generalizes a result by higgins for the case $m=1$.
organizer: jeff remmel
april 11, 2017
4:00 pm
ap&m 7321
****************************