OFFSET
1,1
COMMENTS
Let m,q,n be positive integers. A cyclic multi de Bruijn sequence is a cyclic sequence over a q-ary alphabet in which every q-ary word of length n occurs exactly m times. Each such sequence has length m*q^n. Tesler (2017) shows the number of cyclic multi de Bruijn sequences is 1/(m*q^n) Sum_{r|m} phi(m/r) * ((r*q)! / (r!^q))^(q^(n-1)), where phi() is the Euler totient function A000010. Case m=1 is de Bruijn sequences; see A016031 for binary de Bruijn sequences (m=1, q=2, n>=1). Case m=2, q=2, n>=1 is a(n).
LINKS
Glenn Tesler, Table of n, a(n) for n = 1..11
Glenn Tesler, Multi de Bruijn sequences, Journal of Combinatorics, Vol. 8, No. 3 (2017), 439-474 Preprint.
Glenn Tesler, List of the cyclic sequences for cases n=3 and n=4
FORMULA
a(n) = (6^(2^(n-1)) + 2^(2^(n-1))) / 2^(n+1).
EXAMPLE
For n=1, the a(1)=2 solutions are (0011) and (0101); each has two 0's and two 1's. Cyclic sequences have multiple representations via circular shifts: (0011)=(1001)=(1100)=(0110) all count as the same cyclic sequence, as do (0101)=(1010).
For n=2, the a(2)=5 solutions are (00010111), (00011011), (00011101), (00100111), and (00110011); each has two occurrences of each of 00, 01, 10, and 11. Note that in a cyclic sequence, occurrences may wrap around: in (00010111), there is one 10 in the middle, and another 10 that wraps around from the end to the start. Or, use a different rotation of the sequence: (00010111)=(10001011) shows both occurrences of 10 without wrapping.
For n=3 and 4, see the links section.
MATHEMATICA
Table[(6^(2^(n - 1)) + 2^(2^(n - 1)))/2^(n + 1), {n, 8}] (* Michael De Vlieger, Aug 15 2017 *)
PROG
(PARI) a(n) = (6^(2^(n-1)) + 2^(2^(n-1))) / 2^(n+1) \\ Felix Fröhlich, Aug 15 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Glenn Tesler, Aug 14 2017
STATUS
approved