|
|
A233411
|
|
The number of length n binary words with some prefix which contains two more 1's than 0's or two more 0's than 1's.
|
|
7
|
|
|
0, 0, 2, 4, 12, 24, 56, 112, 240, 480, 992, 1984, 4032, 8064, 16256, 32512, 65280, 130560, 261632, 523264, 1047552, 2095104, 4192256, 8384512, 16773120, 33546240, 67100672, 134201344, 268419072, 536838144, 1073709056, 2147418112, 4294901760, 8589803520
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Also, the number of non-symmetric compositions of n+1, e.g. 4 can be written 1+3, 3+1, 1+1+2, or 2+1+1 (but not 4, 2+2, 1+2+1 or 1+1+1+1). - Henry Bottomley, Jun 27 2005
If we examine the set of all binary words with infinite length we find that the average length of the shortest prefix which satisfies the above conditions is 4.
a(n) is also the number of minimum distinguishing (2-)labelings of the path graph P_n for n > 1. - Eric W. Weisstein, Oct 16 2014
Also, the decimal representation of the diagonal from the origin to the corner of the n-th stage of growth of the two-dimensional cellular automaton defined by "Rule 62", based on the 5-celled von Neumann neighborhood, initialized with a single black (ON) cell at stage zero. - Robert Price, Apr 22 2017
|
|
REFERENCES
|
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 2*x^2/( (1 - 2*x^2)*(1-2x) ).
a(n) = 2^n - 2^ceiling(n/2).
|
|
EXAMPLE
|
a(3) = 4 because we have: 000, 001, 110, 111.
|
|
MATHEMATICA
|
nn=30; CoefficientList[Series[2x^2/(1-2x^2)/(1-2x), {x, 0, nn}], x]
LinearRecurrence[{2, 2, -4}, {0, 0, 2}, 40] (* Harvey P. Dale, Sep 06 2015 *)
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|