login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 7 04:20 EDT 2020. Contains 333292 sequences. (Running on oeis4.)