A233533 -id:A233533 - cp's OEIS frontend

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.

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

Offset: 0

Geoffrey Critzer, Dec 09 2013

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

			a(3) = 4 because we have: 000, 001, 110, 111.

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 170.

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
S. Wolfram, A New Kind of Science
Wolfram Research, Wolfram Atlas of Simple Programs
Eric Weisstein's World of Mathematics, Distinguishing Number
Index entries for sequences related to cellular automata
Index to 2D 5-Neighbor Cellular Automata
Index to Elementary Cellular Automata
Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

Cf. A233533.

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 *)

a(n)=2^n-2^ceil(n/2) \\ Charles R Greathouse IV, Dec 09 2013

G.f.: 2*x^2/( (1 - 2*x^2)*(1-2x) ).
a(n) = 2^n - 2^ceiling(n/2).
a(n) = 2*A032085(n) = 2*A122746(n-2) for n>=2. - Alois P. Heinz, Dec 09 2013

Misplaced comment added by Andrew Howroyd, Sep 30 2017

A233530 Triangle, read by rows, that transforms diagonals in the table of coefficients in the successive iterations of the g.f. (A233531) such that column 0 consists of all zeros after row 1.

Original entry on oeis.org

1, 1, 1, 0, 2, 1, 0, 3, 3, 1, 0, 8, 9, 4, 1, 0, 38, 40, 18, 5, 1, 0, 268, 264, 112, 30, 6, 1, 0, 2578, 2379, 953, 240, 45, 7, 1, 0, 31672, 27568, 10500, 2505, 440, 63, 8, 1, 0, 475120, 392895, 143308, 32686, 5445, 728, 84, 9, 1, 0, 8427696, 6663624, 2342284, 514660, 82176, 10423, 1120, 108, 10, 1, 0, 172607454, 131211423, 44677494, 9514570, 1467837, 178689, 18214, 1632, 135, 11, 1

Offset: 0

Paul D. Hanna, Dec 11 2013

			Triangle begins:
1;
1, 1;
0, 2, 1;
0, 3, 3, 1;
0, 8, 9, 4, 1;
0, 38, 40, 18, 5, 1;
0, 268, 264, 112, 30, 6, 1;
0, 2578, 2379, 953, 240, 45, 7, 1;
0, 31672, 27568, 10500, 2505, 440, 63, 8, 1;
0, 475120, 392895, 143308, 32686, 5445, 728, 84, 9, 1;
0, 8427696, 6663624, 2342284, 514660, 82176, 10423, 1120, 108, 10, 1;
0, 172607454, 131211423, 44677494, 9514570, 1467837, 178689, 18214, 1632, 135, 11, 1;
0, 4008441848, 2943137604, 974898636, 202185010, 30319020, 3572037, 349720, 29718, 2280, 165, 12, 1; ...
in which column 0 consists of all zeros after row 1.
ILLUSTRATION OF GENERATING METHOD.
The g.f. of A233531 begins:
G(x) = x + x^2 - 2*x^3 + 6*x^4 - 18*x^5 + 44*x^6 - 56*x^7 - 300*x^8 + 2024*x^9 - 22022*x^10 - 130456*x^11 - 4241064*x^12 - 103538532*x^13 - 2893308780*x^14 - 88314189664*x^15 - 2924814872208*x^16 - 104538530634844*x^17 - 4010605941377292*x^18 +...
If we form a table of coefficients in the iterations of G(x) like so:
[1,  0,   0,   0,    0,     0,      0,      0,       0,        0, ...];
[1,  1,  -2,   6,  -18,    44,    -56,   -300,    2024,   -22022, ...];
[1,  2,  -2,   3,    2,   -48,    228,   -734,   -1298,   -14630, ...];
[1,  3,   0,  -3,   18,   -54,    -24,    625,   -6324,   -46064, ...];
[1,  4,   4,  -6,   12,    26,   -332,    244,   -2078,  -108754, ...];
[1,  5,  10,   0,  -10,    90,   -192,  -2044,   -3190,  -137176, ...];
[1,  6,  18,  21,  -18,    54,    312,  -3178,  -22032,  -203692, ...];
[1,  7,  28,  63,   42,   -28,    616,   -931,  -46722,  -457746, ...];
[1,  8,  40, 132,  248,   156,    504,   3144,  -51348,  -913356, ...];
[1,  9,  54, 234,  702,  1296,   1656,   6924,  -24444, -1366530, ...];
[1, 10,  70, 375, 1530,  4580,   9916,  22122,   38570, -1538042, ...];
[1, 11,  88, 561, 2882, 11814,  38280, 104929,  273592,  -987932, ...];
[1, 12, 108, 798, 4932, 25542, 110604, 407932, 1351614,  2563858, ...]; ...
then this triangle T transforms one diagonal in the above table into another:
T*[1, 1, -2, -3, 12, 90, 312, -931, -51348, -1366530, ...]
= [1, 2, 0, -6, -10, 54, 616, 3144, -24444, -1538042, ...];
T*[1, 2, 0, -6, -10, 54, 616, 3144, -24444, -1538042, ...]
= [1, 3, 4,  0, -18,-28, 504, 6924,  38570,  -987932, ...];
T*[1, 3, 4,  0, -18,-28, 504, 6924,  38570,  -987932, ...]
= [1, 4,10, 21,  42,156,1656,22122, 273592,  2563858, ...].

Cf. A233531, A233532, A233533, A233534, A233535 (row sums).

/* Given Root Series G, Calculate T(n,k) of Triangle: */
{T(n, k)=local(F=x, M, N, P, m=max(n, k)); M=matrix(m+2, m+2, r, c, F=x;
for(i=1, r+c-2, F=subst(F, x, G +x*O(x^(m+2)))); polcoeff(F, c));
N=matrix(m+1, m+1, r, c, M[r, c]);
P=matrix(m+1, m+1, r, c, M[r+1, c]); (P~*N~^-1)[n+1, k+1]}
/* Calculates Root Series G and then Prints ROWS of Triangle: */
{ROWS=12;V=[1,1];print("");print1("Root Sequence: [1, 1, ");
for(i=2,ROWS,V=concat(V,0);G=x*truncate(Ser(V));
for(n=0,#V-1,if(n==#V-1,V[#V]=-T(n,0));for(k=0,n, T(n,k)));print1(V[#V]", "););
print1("...]");print("");print("");print("Triangle begins:");
for(n=0,#V-2,for(k=0,n,print1(T(n,k),", "));print(""))}

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A233530 Triangle, read by rows, that transforms diagonals in the table of coefficients in the successive iterations of the g.f. (A233531) such that column 0 consists of all zeros after row 1.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

A233532 Second column of triangle A233530.

Views

Author

Keywords

Crossrefs

A233534 Fourth column of triangle A233530.

Views

Author

Keywords

Crossrefs

A233535 Row sums of triangle A233530.

Views

Author

Keywords

Crossrefs