|
| |
|
|
A290952
|
|
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.
|
|
1
|
|
|
|
2, 5, 82, 52496, 44079843328, 62177039921456290463744, 247422994777239366039696433386055989663945981952, 7835921708100840781377057397856335571660942358870727003819788990112934851947892015462438777389056
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
