

A052944


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


17



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

Shortest length of bitstring containing all bitstrings of given length n.  Rainer Rosenthal, Apr 30 2003
Such a bitstring can be obtained by taking a length2^n binary de Bruijn sequence and repeating the n1 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. 461467.


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, 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
T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152, 2015
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.: (23*x)/((12*x)*(1x)^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) = 4a(n+2)  5a(n+1) + 2a(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, 4step ).  Sergei N. Gladkovskii, Dec 01 2012
G.f.: G(0)*x/(1x) 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/(1x), 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


EXAMPLE

a(3)=10 because "0001110100" has length 10 and contains all possible patterns of 3 bits.


MAPLE

spec := [S, {S=Prod(Union(Sequence(Union(Z, Z)), Sequence(Z)), Sequence(Z))}, unlabeled ]: seq(combstruct[count ](spec, size=n), n=0..20);


MATHEMATICA

Table[2^n+n1, {n, 0, 100}] (* 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+n1 \\ Charles R Greathouse IV, Nov 20 2011


CROSSREFS

Cf. A000215, A000051, A160692.
Sequence in context: A065613 A249557 A061705 * A132736 A263366 A068035
Adjacent sequences: A052941 A052942 A052943 * A052945 A052946 A052947


KEYWORD

easy,nonn


AUTHOR

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


STATUS

approved



