A128588 -id:A128588 - cp's OEIS frontend

A306293 Number of binary words of length n such that in every prefix and in every suffix the number of 0's and the number of 1's differ by at most two.

1, 2, 4, 6, 10, 16, 26, 42, 70, 110, 194, 288, 550, 754, 1586, 1974, 4630, 5168, 13634, 13530, 40390, 35422, 120146, 92736, 358390, 242786, 1071074, 635622, 3205030, 1664080, 9598706, 4356618, 28763350, 11405774, 86224514, 29860704, 258542470, 78176338

Offset: 0

Alois P. Heinz, Feb 04 2019

All terms with index n > 0 are even.

			a(3) = 6: 001, 010, 011, 100, 101, 110.
a(4) = 10: 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101.
a(5) = 16: 00101, 00110, 01001, 01010, 01011, 01100, 01101, 01110, 10001, 10010, 10011, 10100, 10101, 10110, 11001, 11010.
a(6) = 26: 001010, 001011, 001100, 001101, 001110, 010010, 010011, 010100, 010101, 010110, 011001, 011010, 011100, 100011, 100101, 100110, 101001, 101010, 101011, 101100, 101101, 110001, 110010, 110011, 110100, 110101.
a(7) = 42: 0010101, 0010110, 0011001, ..., 1100110, 1101001, 1101010.
a(8) = 70: 00101010, ..., 00111100, ..., 11000011, ..., 11010101.

Alois P. Heinz, Table of n, a(n) for n = 0..4193
Index entries for linear recurrences with constant coefficients, signature (0,8,0,-22,0,23,0,-6).

Bisections of a(n+2)/2 give: A007689 (even part), A001906(n+2) (odd part).

Cf. A068911, A128588, A303696, A306306, A306315.

a:= n-> `if`(n<2, 1+n, 2*(<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>,
        <-6|23|-22|8>>^iquo(n-2, 2, 'r').[<<2, 5, 13, 35>>,
        <<3, 8, 21, 55>>][1+r])[1, 1]):
seq(a(n), n=0..50);

G.f.: -(x+1)*(4*x^7-4*x^6-7*x^5-5*x^4+5*x^3+5*x^2-x-1) / ((3*x^2-1) *(2*x^2-1) *(x^2+x-1) *(x^2-x-1)).

a(n) <= A306306(n).

A317783 Number of equivalence classes of binary words of length n for the set of subwords {010, 101}.

Original entry on oeis.org

1, 1, 1, 3, 7, 13, 23, 41, 75, 139, 257, 473, 869, 1597, 2937, 5403, 9939, 18281, 33623, 61841, 113743, 209207, 384793, 707745, 1301745, 2394281, 4403769, 8099795, 14897847, 27401413, 50399055, 92698313, 170498779, 313596147, 576793241, 1060888169, 1951277557

Offset: 0

Alois P. Heinz, Aug 06 2018

Two binary words of the same length are equivalent with respect to a given subword set if they have equal sets of occurrences for each single subword.

All terms are odd.

			a(6) = 23: [|], [|0], [0|], [|1], [|2], [|3], [1|], [2|], [3|], [|03], [03|], [1|0], [0|1], [2|1], [1|2], [3|2], [2|3], [02|1], [1|02], [13|2], [2|13], [13|02], [02|13].  Here [13|2] describes the class whose members have occurrences of 010 at positions 1 and 3 and an occurrence of 101 at position 2 and no other occurrences of both subwords: 001010.  [|] describes the class that avoids both subwords and has 26 members for n=6, in general 2*A000045(n+1) (for n>0).

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (2,-1,1,0,1).

Cf. A000045, A128588, A164146, A303696, A317669, A317779.

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
          <0|0|0|0|1>, <1|0|1|-1|2>>^n.<<1, 1, 1, 3, 7>>)[1$2]:
seq(a(n), n=0..45);
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [1$3, 3, 7][n+1],
      2*a(n-1) -a(n-2) +a(n-3) +a(n-5))
    end:
seq(a(n), n=0..45);

LinearRecurrence[{2, -1, 1, 0, 1}, {1, 1, 1, 3, 7}, 40] (* Jean-François Alcover, Apr 30 2022 *)

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

a(n) = 2*a(n-1) -a(n-2) +a(n-3) +a(n-5) for n >= 5.

A128586 Triangle read by rows: A007318^(-1) * A128540.

Original entry on oeis.org

1, 0, 1, -1, 0, 2, 2, -3, -3, 3, -3, 8, 0, -7, 5, 4, -15, 10, 5, -17, 8, -5, 24, -30, 15, 27, -35, 13, 6, -35, 63, -70, -7, 77, -70, 21, -7, 48, -112, 182, -98, -84, 196, -134, 34, 8, -63, 180, -378, 378, -84, -336, 450, -251, 55, -9, 80, -270, 690, -966, 714, 210, -990, 980, -461, 89

Offset: 1

Gary W. Adamson, Mar 11 2007

Row sums = A128587: (1, 1, 1, -1, 3, -5, 9, -15, 25, -41, ...).

			First few rows of the triangle:
   1;
   0,   1;
  -1,   0,   2;
   2,  -3,  -3,   3;
  -3,   8,   0,  -7,   5;
   4, -15,  10,   5, -17,   8;
  ...

Cf. A007318, A128540, A128587, A128588, A130595.

Inverse binomial transform of A128540.

Matrix product A130595 * A128540. - Georg Fischer, Jun 01 2023

a(33) corrected, a(42)=-84 inserted and more terms from Georg Fischer, Jun 01 2023

A242593 Triangular array read by rows: T(n,k) is the number of length n words on {B,G} that contain exactly k occurrences of the contiguous substrings BGB or GBG. The substrings are allowed to overlap; n>=0, 0<=k<=max(n-2,0).

Original entry on oeis.org

1, 2, 4, 6, 2, 10, 4, 2, 16, 10, 4, 2, 26, 20, 12, 4, 2, 42, 40, 26, 14, 4, 2, 68, 76, 58, 32, 16, 4, 2, 110, 142, 120, 78, 38, 18, 4, 2, 178, 260, 244, 172, 100, 44, 20, 4, 2, 288, 470, 482, 374, 232, 124, 50, 22, 4, 2, 466, 840, 936, 784, 534, 300, 150, 56, 24, 4, 2, 754, 1488, 1788, 1612, 1176, 726, 376, 178, 62, 26, 4, 2

Offset: 0

Geoffrey Critzer, May 18 2014

Equivalently, T(n,k) is the number of ways to arrange n children in a line so that exactly k children are in between two children of opposite gender than their own. Children on the ends of the line cannot be counted as "in between".
Row sums = 2^n.
Column k=0 is A128588.

			Triangle T(n,k) begins:
    1;
    2;
    4;
    6,   2;
   10,   4,   2;
   16,  10,   4,   2;
   26,  20,  12,   4,   2;
   42,  40,  26,  14,   4,  2;
   68,  76,  58,  32,  16,  4,  2;
  110, 142, 120,  78,  38, 18,  4, 2,
  178, 260, 244, 172, 100, 44, 20, 4, 2;
T(4,1) = 4 because we have: BBGB, BGBB, GBGG, GGBG.
T(4,2) = 2 because we have: BGBG, GBGB.

Alois P. Heinz, Rows n = 0..150, flattened

Cf. A128588.

b:= proc(n, t) option remember; `if`(n=0, 1, expand(
      b(n-1, [4, 3, 4, 4, 3][t])*`if`(t=5, x, 1)+
      b(n-1, [2, 2, 5, 5, 2][t])*`if`(t=3, x, 1)))
    end:
T:= n-> (p-> seq(coeff(p,x,i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..16);  # Alois P. Heinz, May 18 2014

nn=10;sol=Solve[{A==va(z^3+z^2A+z B),B==va(z^3+z^2 B + z A)},{A,B}]; Fz[z_,y_]:=Simplify[1/(1-2z-A-B)/.sol/.va->y-1]; Map[Select[#,#>0&]&, Level[CoefficientList[Series[Fz[z,y],{z,0,nn}],{z,y}],{2}]]//Grid

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

A099172 Array T(m, n) read by antidiagonals: number of binary strings with m 1's and n 0's without zigzags.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 4, 2, 1, 1, 2, 5, 5, 2, 1, 1, 2, 6, 8, 6, 2, 1, 1, 2, 7, 11, 11, 7, 2, 1, 1, 2, 8, 14, 18, 14, 8, 2, 1, 1, 2, 9, 17, 26, 26, 17, 9, 2, 1, 1, 2, 10, 20, 35, 42, 35, 20, 10, 2, 1, 1, 2, 11, 23, 45, 62, 62, 45, 23, 11, 2, 1, 1, 2, 12, 26, 56, 86, 100, 86, 56, 26, 12, 2, 1

Offset: 0

Ralf Stephan, Oct 10 2004

			Array begins:
1, 1, 1,  1,  1,  1,   1,   1,
1, 2, 2,  2,  2,  2,   2,   2,
1, 2, 4,  5,  6,  7,   8,   9,
1, 2, 5,  8, 11, 14,  17,  20,
1, 2, 6, 11, 18, 26,  35,  45,
1, 2, 7, 14, 26, 42,  62,  86,
1, 2, 8, 17, 35, 62, 100, 150,
1, 2, 9, 20, 45, 86, 150, 242,

E. Munarini and N. Z. Salvi, Binary strings without zigzags, [alternative link], Séminaire Lotharingien de Combinatoire, B49h (2004), 15 pp.
R. Pemantle and M. C. Wilson, Twenty combinatorial examples of asymptotics derived from multivariate generating functions, arXiv:math/0512548 [math.CO], 2005-2007.
R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-372. See p. 269

Main diagonal is A078678. Antidiagonal sums are A128588.

gf:=(1 + x*y + x^2*y^2)/(1 - x - y + x*y - x^2*y^2);seq(seq(coeff(series(coeff(series(gf,y,m+1),y,m),x,d-m+1),x,d-m), m=0..d), d=0..9);

T[m_, n_] := Sum[Binomial[m - k + 2 Floor[k/3], Floor[k/3]] Binomial[n - k + 2 Floor[k/3], Floor[k/3]], {k, 0, Min[m+Floor[m/2], n+Floor[n/2]]}];
Table[T[m-n, n], {m, 0, 12}, {n, 0, m}] // Flatten (* Jean-François Alcover, Aug 17 2018 *)

T(m,n)=sum(k=0,min(m+m\2,n+n\2),binomial(m-k+2*(k\3),k\3)*binomial(n-k+2*(k\3),k\3))

T(n,k) = {x = xx + xx*O(xx^n); y = yy + yy*O(yy^k); polcoeff(polcoeff((1 + x*y + x^2*y^2)/(1 - x - y + x*y - x^2*y^2), n, xx), k, yy);} \\ Michel Marcus, Nov 25 2013

{A(n, m) = if( n<0 || m<0, 0, polcoeff( polcoeff( (1 + x*y + x^2*y^2 ) / (1 - x - y + x*y - x^2*y^2) + x * O(x^n), n) + y * O(y^m), m))}; /* Michael Somos, Jun 06 2016 */

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

T(m, n) = Sum{k=0..min(m+[m/2], n+[n/2]), C(m-k+2[k/3], [k/3])*C(n-k+2[k/3], [k/3]) }.

A198834 Number of sequences of n coin flips that win on the last flip, if the sequence of flips ends with (0,1,1) or (1,1,1).

Original entry on oeis.org

0, 0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset: 1

Paul Weisenhorn, Oct 30 2011

If the sequence ends with (011) Abel wins; if it ends with (111) Kain wins.
Kain(n)=0 for n <> 3; Kain(3)=1.
Abel(n) = A128588(n-2) for n > 2.
a(n) = A006355(n-1) for n > 2.
Win probability for Abel: Sum_{n>=1} Abel(n)/2^n = 7/8.
Win probability for Kain: Kain(3)/8 = 1/8.
Mean length of the game: Sum_{n>=1} n*a(n)/2^n = 7.
Appears to be essentially the same as A163733, A118658, A055389. - R. J. Mathar, Oct 31 2011

			For n=6 the a(6)=6 solutions are (0,0,0,0,1,1), (1,0,0,0,1,1); (0,1,0,0,1,1), (1,1,0,0,1,1), (0,0,1,0,1,1), (1,0,1,0,1,1) all for Abel.

A. Engel, Wahrscheinlichkeit und Statistik, Band 2, Klett, 1978, pages 25-26.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Tian-Xiao He, Peter J.-S. Shiue, Zihan Nie, Minghao Chen, Recursive sequences and Girard-Waring identities with applications in sequence transformation, Electronic Research Archive (2020) Vol. 28, No. 2, 1049-1062.
Index entries for linear recurrences with constant coefficients, signature (1,1).

Cf. A006355, A055389, A118658, A128588, A163733.

a(1):=0: a(2):=0: a(3):=2:
ml:=0.75: pot:=8:
for n from 4 to 100 do
  pot:=2*pot:
  a(n):=a(n-1)+a(n-2):
  ml:=ml+n*a(n)/pot:
end do:
printf("%12.8f",ml);
seq(a(n),n=1..100);

Join[{0, 0}, Table[2*Fibonacci[n], {n, 70}]] (* Vladimir Joseph Stephan Orlovsky, Feb 10 2012 *)
Join[{0},LinearRecurrence[{1,1},{0,2},50]] (* Vincenzo Librandi, Feb 19 2012 *)

a(n) = a(n-1) + a(n-2) for n > 3.
G.f.: 2*x^3/(1 - x - x^2).
a(n) = 2*A000045(n-2). - R. J. Mathar, Jan 11 2017
E.g.f.: 2 - 2*x + 2*exp(x/2)*(3*sqrt(5)*sinh(sqrt(5)*x/2) - 5*cosh(sqrt(5)*x/2))/5. - Stefano Spezia, Feb 19 2023

A365746 Table read by antidiagonals upward: T(n,k) is the number of binary strings of length k with the property that every substring of length A070939(n) is lexicographically earlier than the binary expansion of n; n, k >= 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 4, 5, 2, 1, 0, 1, 2, 4, 4, 8, 2, 1, 0, 1, 2, 4, 5, 4, 13, 2, 1, 0, 1, 2, 4, 6, 7, 4, 21, 2, 1, 0, 1, 2, 4, 7, 10, 11, 4, 34, 2, 1, 0, 1, 2, 4, 8, 13, 16, 16, 4, 55, 2, 1, 0, 1, 2, 4, 8, 8, 24

Offset: 0

Peter Kagey, Sep 17 2023

			Table begins:
 n\k | 0  1  2  3   4   5   6   7    8    9   10   11
-----+----------------------------------------------------
   0 | 1, 0, 0, 0,  0,  0,  0,  0,   0,   0,   0,   0, ...
   1 | 1, 1, 1, 1,  1,  1,  1,  1,   1,   1,   1,   1, ...
   2 | 1, 2, 2, 2,  2,  2,  2,  2,   2,   2,   2,   2, ...
   3 | 1, 2, 3, 5,  8, 13, 21, 34,  55,  89, 144, 233, ...
   4 | 1, 2, 4, 4,  4,  4,  4,  4,   4,   4,   4,   4, ...
   5 | 1, 2, 4, 5,  7, 11, 16, 23,  34,  50,  73, 107, ...
   6 | 1, 2, 4, 6, 10, 16, 26, 42,  68, 110, 178, 288, ...
   7 | 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, ...
   8 | 1, 2, 4, 8,  8,  8,  8,  8,   8,   8,   8,   8, ...
   9 | 1, 2, 4, 8,  9, 11, 15, 23,  32,  43,  58,  81, ...
For (n,k) = (3,4), we see that T(3,4) = 8 because there are 8 binary strings of length k = 4 where all length A070939(3) = 2 substrings are lexicographically earlier than "11" (the binary expansion of n = 3): 0000, 0001, 0010, 0100, 0101, 1000, 1001, and 1010.

Cf. A030190, A070939, A209972.

Cf. A000045 (row 3), A164316 (row 5), A128588 (row 6), A000073 (row 7).

A365746Row[s_,
  numberOfTerms_] := (digits = If[s == 0, 1, Ceiling[Log[2, s + 1]]];
  m = 2^(digits - 1);
  transferMatrix =
   If[s == 0, {{0}},
    Table[If[(Ceiling[i/2] ==
         j) || ((i <= s - m) && (Ceiling[i/2] == j - m/2)), 1, 0], {i,
       1, m}, {j, 1, m}]];
  sequence =
   Table[2^k, {k, 0, digits - 1}] ~Join~
    Table[MatrixPower[transferMatrix, k] // Total // Total, {k, 1,
      numberOfTerms - digits}];
  Take[sequence, numberOfTerms])

G.f. for row n = 0: 1;
G.f. for row n = 1: 1/(1 - x);
G.f. for row n = 2: (1 + x)/(1 - x);
G.f. for row n = 3: (1 + x)/(1 - x - x^2);
G.f. for row n = 4: (1 + x + 2x^2)/(1 - x);
G.f. for row n = 5: (1 + x + 2x^2)/(1 - x - x^3);
G.f. for row n = 6: (1 + x + x^2)/(1 - x - x^2);
G.f. for row n = 7: (1 + x + x^2)/(1 - x - x^2 - x^3);
G.f. for row n = 8: (1 + x + 2 x^2 + 4 x^3)/(1 - x);
G.f. for row n = 9: (1 + x + 2x^2 + 4x^3)/(1 - x - x^4).

cp's OEIS Frontend

A306293 Number of binary words of length n such that in every prefix and in every suffix the number of 0's and the number of 1's differ by at most two.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A317783 Number of equivalence classes of binary words of length n for the set of subwords {010, 101}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A128586 Triangle read by rows: A007318^(-1) * A128540.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A242593 Triangular array read by rows: T(n,k) is the number of length n words on {B,G} that contain exactly k occurrences of the contiguous substrings BGB or GBG. The substrings are allowed to overlap; n>=0, 0<=k<=max(n-2,0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A099172 Array T(m, n) read by antidiagonals: number of binary strings with m 1's and n 0's without zigzags.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A198834 Number of sequences of n coin flips that win on the last flip, if the sequence of flips ends with (0,1,1) or (1,1,1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A365746 Table read by antidiagonals upward: T(n,k) is the number of binary strings of length k with the property that every substring of length A070939(n) is lexicographically earlier than the binary expansion of n; n, k >= 0.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica