cp's OEIS Frontend

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.

%I A016031 #67 Jul 18 2025 10:33:37
%S A016031 1,1,2,16,2048,67108864,144115188075855872,
%T A016031 1329227995784915872903807060280344576,
%U A016031 226156424291633194186662080095093570025917938800079226639565593765455331328
%N 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.
%C A016031 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
%C A016031 Number of Ouroborean rings for binary n-tuplets. - _Lekraj Beedassy_, May 06 2004
%C A016031 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
%C A016031 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
%C A016031 Named after the Dutch mathematician Nicolaas Govert de Bruijn (1918-2012). - _Amiram Eldar_, Jun 20 2021
%D A016031 Jonathan L. Gross and Jay Yellen, eds., Handbook of Graph Theory, CRC Press, 2004, p. 255.
%D A016031 Frank Harary and Edgar M. Palmer, Graphical Enumeration, 1973, p. 31.
%D A016031 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.
%D A016031 Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Cor. 5.6.15.
%D A016031 Ian Stewart, Game, Set and Math, pp. 50, Penguin 1991.
%H A016031 Vincenzo Librandi, <a href="/A016031/b016031.txt">Table of n, a(n) for n = 1..12</a>
%H A016031 CombOS - Combinatorial Object Server, <a href="http://combos.org/bruijn">Generate de Bruijn sequences</a>.
%H A016031 Robert Erra, Nik Lygeros and Nigel Stewart, <a href="http://www.dmtcs.org/pdfpapers/dmAA0112.pdf">On Minimal Strings Containing the Elements of S(n) by Decimation</a>, Proceedings AA (DM-CCG), 2001, Section 5.4.
%H A016031 Loïc Foissy, <a href="https://arxiv.org/abs/2304.00810">Hopf algebraic structures on hypergraphs and multi-complexes</a>, arXiv:2304.00810 [math.CO], 2023.
%H A016031 Francisco J. Muñoz and Juan Carlos Nuño, <a href="https://arxiv.org/abs/2507.09764">Rule-based Generation of de Bruijn Sequences: Memory and Learning</a>, arXiv:2507.09764 [cs.FL], 2025. See p. 9.
%H A016031 Wikipedia, <a href="http://en.wikipedia.org/wiki/De_Bruijn_sequence">De Bruijn sequence</a>.
%F A016031 a(n) = 2^A000295(n-1). - _Lekraj Beedassy_, Jan 17 2007
%F A016031 Shifting once to the left gives the binomial transform of A323816. - _Gus Wiseman_, Feb 01 2019
%t A016031 Table[2^(2^(n - 1) - n), {n, 20}] (* _Vincenzo Librandi_, Aug 09 2017 *)
%o A016031 (Magma) [2^(2^(n-1)-n): n in [1..10]]; // _Vincenzo Librandi_, Aug 09 2017
%Y A016031 Cf. A000295, A003465, A006125, A058891 (set systems), A317794 (unlabeled case), A323816 (spanning case), A323817 (connected case), A331691 (alternating signs).
%K A016031 nonn,easy,nice
%O A016031 1,3
%A A016031 _N. J. A. Sloane_, _Robert G. Wilson v_