login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A016031 De Bruijn's sequence: 2^(2^(n-1) - n): ways of arranging 2^n bits in circle so all 2^n consecutive strings of length n are distinct. 7
1, 1, 2, 16, 2048, 67108864, 144115188075855872, 1329227995784915872903807060280344576, 226156424291633194186662080095093570025917938800079226639565593765455331328 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Sequence corresponds also to the largest number that may be determined by asking no more than 2^(n-1) - 1 questions("Yes"-or-"No" answerable) with lying allowed at most once. - Lekraj Beedassy, Jul 15 2002

Number of Ouroborean rings for binary n-tuplets. - Lekraj Beedassy, May 06 2004

Also the number of games of Nim that are wins for the second player when the starting position is either the empty heap or heaps of sizes 1 <= t_1 < t_2 < ... < t_k < 2^(n-1) (if n is 1, the only starting position is the empty heap). E.g.: a(4) = 16: the winning positions for the second player when all the heap sizes are different and less than 2^3: (4,5,6,7), (3,5,6), (3,4,7), (2,5,7), (2,4,6), (2,3,6,7), (2,3,4,5), (1,6,7), (1,4,5), (1,3,5,7), (1,3,4,6), (1,2,5,6), (1,2,4,7), (1,2,3), (1,2,3,4,5,6,7) and the empty heap. - Kennan Shelton (kennan.shelton(AT)gmail.com), Apr 14 2006

REFERENCES

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 255.

F. Harary and E. Palmer, Graphical Enumeration, (1973), p. 31.

D. J. Newman, "A variation of the Game of Twenty Question", Prob. 66-20 pp. 121-2 In Problems in Applied Mathematics, Ed. M. S. Klamkin, SIAM PA 1990.

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.6.15.

I. Stewart, Game, Set and Math, pp. 50, Penguin 1991.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..12

R. Erra, N. Lygeros and N. Stewart, On Minimal Strings Containing the Elements of S(n) by Decimation, Proceedings AA (DM-CCG), 2001, Section 5.4.

Wikipedia, De Bruijn sequence

FORMULA

a(n) = 2^A000295(n-1). - Lekraj Beedassy, Jan 17 2007

MAPLE

P:=proc(n) local i, j; for i from 1 by 1 to n do j:=2^(2^(i-1)-i); print(j); od; end: P(20); # Paolo P. Lava, May 11 2006

MATHEMATICA

Table[2^(2^(n - 1) - n), {n, 20}] (* Vincenzo Librandi, Aug 09 2017 *)

PROG

(MAGMA) [2^(2^(n-1)-n): n in [1..10]]; // Vincenzo Librandi, Aug 09 2017

CROSSREFS

Sequence in context: A102103 A060597 A091479 * A001309 A132569 A165644

Adjacent sequences:  A016028 A016029 A016030 * A016032 A016033 A016034

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane, Robert G. Wilson v

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 25 18:05 EDT 2017. Contains 292499 sequences.