OFFSET
0,2
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
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).
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
EXAMPLE
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....
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 *)
PROG
(Magma) [2^n + n - 1: n in [0..40]]; // Vincenzo Librandi, Jun 20 2011
(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
(GAP) List([0..40], n-> 2^n +n-1); # G. C. Greubel, Oct 18 2019
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
STATUS
approved