A052944 a(n) = 2^n + n - 1.

0, 2, 5, 10, 19, 36, 69, 134, 263, 520, 1033, 2058, 4107, 8204, 16397, 32782, 65551, 131088, 262161, 524306, 1048595, 2097172, 4194325, 8388630, 16777239, 33554456, 67108889, 134217754, 268435483, 536870940, 1073741853, 2147483678

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

Comments

Shortest length of bit-string containing all bit-strings of given length n. - Rainer Rosenthal, Apr 30 2003

Such a bitstring can be obtained by taking a length-2^n binary de Bruijn sequence and repeating the n-1 initial symbols at the end. - Joerg Arndt, Mar 16 2015

Bit string definition is equivalent to minimum number of tosses of a coin to achieve all possible outcomes of n tosses. - Maurizio De Leo, Mar 01 2015

Also the indices of Fermat numbers that can be represented as cyclotomic numbers. Specifically, F(a(n)) = cyclotomic(2^2^n,2^2^n). - T. D. Noe, Oct 17 2003

a(n) = A006127(n) - 1. - Reinhard Zumkeller, Apr 13 2011

Randomly select (with uniform distribution) a length n binary word w. a(n) is apparently the expected wait time for the first occurrence of w over all infinite binary sequences. For example: a(4)=19. We consider A005434(4)=4 distinct classes of length 4 binary words that share the same autocorrelation. There are A003000(4)=6 words that have waiting time = 16; 2 words with waiting time =20; 6 words with waiting time = 18; and 2 words with waiting time =30. 1/16*(6*16 + 2*20 + 6*18 + 2*30) = 19. - Geoffrey Critzer, Feb 27 2014

Examples

			a(3) = 10 because "0001110100" has length 10 and contains all possible patterns of 3 bits:
  0001110100
  ----------
  000.......
  .001......
  ......010.
  ..011.....
  .......100
  .....101..
  ....110...
  ...111....
		

References

• Discussed in newsgroup de.rec.denksport in Apr 2003
• N. G. de Bruijn: A combinatorial problem. Indagationes Math. 8 (1946), pp. 461-467.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012; J. Int. Seq. 15 (2012) # 12.6.2.
• A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 178. Book's website
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1001
• Viktor Lopatkin, Pasha Zusmanovich, Commutative Lie algebras and commutative cohomology in characteristic 2, arXiv:1907.03690 [math.KT], 2019.
• T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015-2016.
• E. H. Rivals, Autocorrelation of Strings.
• Eric Weisstein's World of Mathematics, Cyclotomic Polynomial
• Eric Weisstein's World of Mathematics, Coin Tossing
• Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Crossrefs

Cf. A000051, A000215, A160692.

Programs

GAP

List([0..40], n-> 2^n +n-1); # G. C. Greubel, Oct 18 2019

Magma

[2^n + n - 1: n in [0..40]]; // Vincenzo Librandi, Jun 20 2011

Maple

spec:= [S,{S=Prod(Union(Sequence(Union(Z,Z)),Sequence(Z)),Sequence(Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
seq(2^n + n-1, n=0..40); # G. C. Greubel, Oct 18 2019

Mathematica

Table[2^n+n-1, {n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Oct 25 2008 *)

PARI

a(n)=2^n+n-1 \\ Charles R Greathouse IV, Nov 20 2011

Sage

[2^n +n-1 for n in (0..40)] # G. C. Greubel, Oct 18 2019

Formula

G.f.: (2-3*x)/((1-2*x)*(1-x)^2).

a(n+1) = 2*a(n) - n + 2 with a(0)=0. - Pieter Moree, Mar 06 2004

For n>=1: partial sums of A000051. - Emeric Deutsch, Mar 04 2004

a(0)=0, a(1)=2, a(2)=5, a(n+3) = 4*a(n+2) - 5*a(n+1) + 2*a(n). - Hermann Kremer (Hermann.Kremer(AT)online.de), Mar 16 2004

a(n) = A000225(n) + n. - Zerinvary Lajos, May 29 2009

E.g.f.: U(0), where U(k) = 1 + x/(2^k + 2^k/(x - 1 - x^2*2^(k+1)/(x*2^(k+1) - (k+1)/U(k+1) )));(continued fraction, 3rd kind, 4-step ). - Sergei N. Gladkovskii, Dec 01 2012

G.f.: G(0)*x/(1-x) where G(k) = 1 + 2^k/(1 - x/(x + 2^k/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, May 24 2013

G.f.: Q(0)*x/(1-x), where Q(k)= 1 + 1/(2^k - 2*x*4^k/(2*x*2^k + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 24 2013

E.g.f.: exp(2*x) - (1-x)*exp(x). - G. C. Greubel, Oct 18 2019