|
%I #18 Aug 15 2017 16:43:31
%S 2,5,82,52496,44079843328,62177039921456290463744,
%T 247422994777239366039696433386055989663945981952,
%U 7835921708100840781377057397856335571660942358870727003819788990112934851947892015462438777389056
%N Multi de Bruijn Sequences: Number of ways to arrange 2^(n+1) binary digits in a circle so that every length n binary string occurs exactly twice.
%C 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).
%H Glenn Tesler, <a href="/A290952/b290952.txt">Table of n, a(n) for n = 1..11</a>
%H Glenn Tesler, <a href="http://dx.doi.org/10.4310/JOC.2017.v8.n3.a3">Multi de Bruijn sequences</a>, Journal of Combinatorics, Vol. 8, No. 3 (2017), 439-474 <a href="https://arxiv.org/abs/1708.03654">Preprint</a>.
%H Glenn Tesler, <a href="http://www.math.ucsd.edu/~gptesler/multidebruijn/">List of the cyclic sequences for cases n=3 and n=4</a>
%F a(n) = (6^(2^(n-1)) + 2^(2^(n-1))) / 2^(n+1).
%e 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).
%e 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.
%e For n=3 and 4, see the links section.
%t Table[(6^(2^(n - 1)) + 2^(2^(n - 1)))/2^(n + 1), {n, 8}] (* _Michael De Vlieger_, Aug 15 2017 *)
%o (PARI) a(n) = (6^(2^(n-1)) + 2^(2^(n-1))) / 2^(n+1) \\ _Felix Fröhlich_, Aug 15 2017
%Y Cf. A016031.
%K nonn,easy
%O 1,1
%A _Glenn Tesler_, Aug 14 2017
| 