Glenn Tesler - cp's OEIS frontend

User: Glenn Tesler

Glenn Tesler has authored 2 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.

2, 5, 82, 52496, 44079843328, 62177039921456290463744, 247422994777239366039696433386055989663945981952, 7835921708100840781377057397856335571660942358870727003819788990112934851947892015462438777389056

Offset: 1

Glenn Tesler, Aug 14 2017

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).

			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.

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

Cf. A016031.

Table[(6^(2^(n - 1)) + 2^(2^(n - 1)))/2^(n + 1), {n, 8}] (* Michael De Vlieger, Aug 15 2017 *)

a(n) = (6^(2^(n-1)) + 2^(2^(n-1))) / 2^(n+1) \\ Felix Fröhlich, Aug 15 2017

a(n) = (6^(2^(n-1)) + 2^(2^(n-1))) / 2^(n+1).

A131209 Maximal distance between two signed permutations of n elements.

Original entry on oeis.org

0, 1, 3, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69

Offset: 0

Brian Hayes, Oct 26 2007, based on email from Glenn Tesler (gptesler(AT)math.ucsd.edu)

nonn

See also the comments in A058986 for background information.
From Glenn Tesler: (Start)
Let d_max = a(n) be the maximal distance.
Then d_max = n for n=0,1,3; d_max = n+1 except for n=0,1,3; however, there are many permutations achieving the max, not just the 2 Gollan permutations as in the unsigned case.
The formula for reversal distance is d = n + 1 - c + h + f,
where c is the number of cycles in the breakpoint graph, h is the number of "hurdles" and f is the number of "fortresses" (0 or 1).
It turns out that c >= h+f.
This is because each hurdle is composed of one or more cycles, distinct from those in other hurdles, and fortresses can be worked into that, too.
So we may rewrite distance as d = n+1 - (c-h-f), where c-h-f>=0. Thus d_max <= n+1.
Except for n=0,1,3, it turns out we can make c-h-f=0.
When n=0: d(null,null) = 0, so d_max = 0 (has c=1, h=0)
When n=1: d( 1, -1 ) = 1, d( 1, 1 ) = 0, so d_max = 1 (first one has c=1, h=0)
When n=2: d( 2 1, 1 2 ) = 3, all other d(sigma, 1 2) < 3 (has c=h=1)
When n=3: d_max = 3 (25 solutions, found by brute force; 20 with c=1, h=0; 5 with c=2, h=1)
When n>3: d_max = n+1 and there are many solutions, obtained by creating a situation in which c=h, f=0. One of them is
n=2m: n 1 m+1 2 m+2 3 m+3 ... m-1 2m-1 m (has c=h=1)
n=2m+1: n 1 m+1 2 m+2 3 m+3 ... m 2m (has c=h=2)
Note that these are indeed signed permutations, in which all signs happen to be positive. This is because "hurdles" require all the signs to be the same.
Also note that these are just examples to show that at least one permutation has d=n+1, which proves d_max=n+1 by the bound; however, there are many more signed permutations that also achieve d=n+1. (End)

Brian Hayes, Sorting out the genome, Amer. Scientist, 95 (2007), 386-391.

Cf. A058986, A078941.

a(n) = n+1 except for n=0,1,3.

cp's OEIS Frontend

User: Glenn Tesler

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula