

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 qary alphabet in which every qary 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_{rm} phi(m/r) * ((r*q)! / (r!^q))^(q^(n1)), 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), 439474 Preprint.
Glenn Tesler, List of the cyclic sequences for cases n=3 and n=4


FORMULA

a(n) = (6^(2^(n1)) + 2^(2^(n1))) / 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^(n1)) + 2^(2^(n1))) / 2^(n+1) \\ Felix FrÃ¶hlich, Aug 15 2017


CROSSREFS

Cf. A016031.
Sequence in context: A096266 A123978 A303482 * A201113 A309089 A120798
Adjacent sequences: A290949 A290950 A290951 * A290953 A290954 A290955


KEYWORD

nonn,easy


AUTHOR

Glenn Tesler, Aug 14 2017


STATUS

approved



