De Bruijn sequence

Common card · No. 302958

In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length kn, which is also the number of distinct strings of length n on A. Each of these distinct strings, when taken as a substring of B(k, n), must start at a different position, because substrings starting at the same position are not distinct. Therefore, B(k, n) must have at least kn symbols. And since B(k, n) has exactly kn symbols, de Bruijn sequences are optimally short with respect to the property of containing every string of length n at least once. The number of distinct de Bruijn sequences B(k, n) is ( k ! )...

Read on Wikipedia · Image Eviatar Bach, CC0