A016031 De Bruijn's sequence: 2^(2^(n-1) - n): number of ways of arranging 2^n bits in circle so all 2^n consecutive strings of length n are distinct.

1, 1, 2, 16, 2048, 67108864, 144115188075855872, 1329227995784915872903807060280344576, 226156424291633194186662080095093570025917938800079226639565593765455331328

Offset: 1

Author

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

Keywords

• nonn
• easy
• nice

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

a(n + 1) = 2^(2^n-n-1) = 2^A000295(n) is also the number of set-systems on n vertices with no singletons. The case with singletons is A058891. The unlabeled case is A317794. The spanning/covering case is A323816. The antichain case is A006126. The connected case is A323817. The uniform case is A306021(n) - 1. The graphical case is A006125. The chain case is A005840. - Gus Wiseman, Feb 01 2019

Named after the Dutch mathematician Nicolaas Govert de Bruijn (1918-2012). - Amiram Eldar, Jun 20 2021

References

• Jonathan L. Gross and Jay Yellen, eds., Handbook of Graph Theory, CRC Press, 2004, p. 255.
• Frank Harary and Edgar M. Palmer, Graphical Enumeration, 1973, p. 31.
• D. J. Newman, "A variation of the Game of Twenty Question", in: Murray S. Klamkin (ed.), Problems in Applied Mathematics, Philadelphia, PA: SIAM, 1990, Problem 66-20, pp. 121-122.
• Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.6.15.
• Ian Stewart, Game, Set and Math, pp. 50, Penguin 1991.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..12
• CombOS - Combinatorial Object Server, Generate de Bruijn sequences.
• Robert Erra, Nik Lygeros and Nigel Stewart, On Minimal Strings Containing the Elements of S(n) by Decimation, Proceedings AA (DM-CCG), 2001, Section 5.4.
• Loïc Foissy, Hopf algebraic structures on hypergraphs and multi-complexes, arXiv:2304.00810 [math.CO], 2023.
• Francisco J. Muñoz and Juan Carlos Nuño, Rule-based Generation of de Bruijn Sequences: Memory and Learning, arXiv:2507.09764 [cs.FL], 2025. See p. 9.
• Wikipedia, De Bruijn sequence.

Crossrefs

Cf. A000295, A003465, A006125, A058891 (set systems), A317794 (unlabeled case), A323816 (spanning case), A323817 (connected case), A331691 (alternating signs).

Programs

Magma

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

Mathematica

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

Formula

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

Shifting once to the left gives the binomial transform of A323816. - Gus Wiseman, Feb 01 2019