A118430 -id:A118430 - cp's OEIS frontend

A164146 Number of binary strings of length n with equal numbers of 010 and 101 substrings.

1, 2, 4, 6, 12, 20, 38, 66, 124, 224, 424, 788, 1502, 2838, 5438, 10386, 20004, 38508, 74516, 144264, 280216, 544736, 1061292, 2069596, 4042254, 7902294, 15466842, 30297422, 59404174, 116558270, 228876426, 449713994, 884199348, 1739434972, 3423770240, 6742430340

Offset: 0

R. H. Hardin, Aug 11 2009

			a(5) = 20: 00000, 00001, 00011, 00101, 00110, 00111, 01011, 01100, 01110, 01111, 10000, 10001, 10011, 10100, 11000, 11001, 11010, 11100, 11110, 11111. - _Alois P. Heinz_, Apr 16 2015

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 501 terms from R. H. Hardin)
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, arXiv preprint arXiv:1112.6207, 2011. See subpages for rigorous derivations of g.f., recurrence, asymptotics for this sequence. [From _N. J. A. Sloane_, Apr 07 2012]

Cf. A118430, A255386, A260505, A260668, A260697, A303430.
Column k=1 of A303696.
Column k=0 of A307796.

CoefficientList[Series[-(4*x^4-2*x^3-2*x^2+x+Sqrt[(2*x-1)*(2*x^2-1)*(2*x^2-2*x+1)]) / ((x-1)*(2*x-1)*(2*x^2-1)),{x,0,33}],x] (* Stefano Spezia, Jul 31 2025 *)

G.f.: -(4*x^4-2*x^3-2*x^2+x+sqrt((2*x-1)*(2*x^2-1)*(2*x^2-2*x+1))) / ((x-1)*(2*x-1)*(2*x^2-1)). - Alois P. Heinz, Apr 16 2015

A136444 a(n) = Sum_{k=0..n} kbinomial(n-k, 2k).

Original entry on oeis.org

0, 0, 0, 1, 3, 6, 12, 25, 51, 101, 197, 381, 731, 1392, 2634, 4958, 9290, 17337, 32239, 59760, 110460, 203651, 374593, 687567, 1259597, 2303449, 4205493, 7666560, 13956532, 25374108, 46076436, 83575025, 151431099, 274108826, 495708364, 895670733, 1617003823, 2916984121

Offset: 0

Don Knuth, Apr 04 2008

Consider four related sequences: A_n = sum C(n-k, 2*k), B_n = sum C(n-k, 2*k+1), A^*_n = sum k*C(n-k, 2*k), B^*_n = sum k*C(n-k, 2*k+1).
Sequence A_n, with generating function (1-z)/p(z) where p(z) = 1 - 2*z + z^2 - z^3, is A005251.
Sequence B_n, with generating function z/p(z), is A005314.
Sequence A^*_n is the present sequence.
Sequence B^*_n is A118430, but shifted one place so that the generating function is z^4/p(z)^2 instead of z^3/p(z)^2.
These sequences have many interrelations; for example,
B_{n+1} - B_n = A_n; B^*_{n+1} - B^*_n = A^*_n;
A_{n+1} - A_n = B_{n-1}; A^*{n+1} - A^*_n = B^*{n-1} + B_{n-1}.

D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.

T. Mansour and M. Shattuck, Counting Peaks and Valleys in a Partition of a Set, J. Int. Seq. 13 (2010), #10.6.8, partitions of [n] with 2 blocks with 1 peak.

Cf. A005251, A005314, A118430, A136445, A137356-A137361.

[&+[k*Binomial(n-k, 2*k): k in [0..n]]: n in [0..40]]; // Bruno Berselli, Feb 13 2015

a:= n-> (Matrix([[0,0,1,1,-3,-5]]). Matrix(6, (i,j)-> if (i=j-1) then 1 elif j=1 then [4,-6,6,-5,2,-1][i] else 0 fi)^n)[1,1]: seq(a(n), n=0..37);  # Alois P. Heinz, Aug 13 2008

a[n_] := ({0, 0, 1, 1, -3, -5} . MatrixPower[ Table[If[i == j-1, 1, If[j == 1, {4, -6, 6, -5, 2, -1}[[i]], 0]], {i, 6}, {j, 6}], n])[[1]]; Table[a[n], {n, 0, 37}] (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)
CoefficientList[Series[x^3 (1 - x)/(1 - 2 x + x^2 - x^3)^2, {x, 0, 40}], x] (* Vincenzo Librandi, Aug 15 2015 *)

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

a(n) ~ c * d^n * n, where d = A109134 = 1.75487766624669276... is the root of the equation d*(d-1)^2 = 1, c = 0.072838349685011... is the root of the equation 529*c^3 - 207*c^2 + 26*c = 1. - Vaclav Kotesovec, May 25 2015

A255386 Number of binary words of length n with exactly one occurrence of subword 010 and exactly one occurrence of subword 101.

Original entry on oeis.org

0, 0, 0, 0, 2, 4, 10, 20, 42, 84, 166, 320, 608, 1140, 2116, 3892, 7102, 12868, 23170, 41488, 73918, 131104, 231578, 407520, 714672, 1249368, 2177736, 3785688, 6564362, 11355940, 19602154, 33767228, 58056786, 99638364, 170711134, 292011872, 498747632

Offset: 0

Alois P. Heinz, May 05 2015

nonn

			a(4) = 2: 0101, 1010.
a(5) = 4: 00101, 01011, 10100, 11010.
a(6) = 10: 000101, 001011, 010110, 010111, 011010, 100101, 101000, 101001, 110100, 111010.
a(8) = 42: 00000101, 00001011, 00010110, 00010111, 00011010, 00101100, 00101110, 00101111, 00110100, 00111010, 01001101, 01011000, 01011001, 01011100, 01011110, 01011111, 01100101, 01101000, 01101001, 01110100, 01111010, 10000101, 10001011, 10010110, 10010111, 10011010, 10100000, 10100001, 10100011, 10100110, 10100111, 10110010, 11000101, 11001011, 11010000, 11010001, 11010011, 11100101, 11101000, 11101001, 11110100, 11111010.

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

Cf. A118430, A260697.

a:= n-> coeff(series(-2*x^4*(x-1)^2/
        ((x^2-x+1)*(x^2+x-1)^3), x, n+1), x, n):
seq(a(n), n=0..50);

LinearRecurrence[{4,-4,-2,5,-2,-2,2,1},{0,0,0,0,2,4,10,20},40] (* Harvey P. Dale, Apr 09 2016 *)

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

A260668 Number of binary words of length n such that for every prefix the number of occurrences of subword 101 is larger than or equal to the number of occurrences of subword 010.

Original entry on oeis.org

1, 2, 4, 7, 13, 24, 45, 84, 158, 298, 566, 1079, 2066, 3966, 7635, 14730, 28484, 55188, 107130, 208294, 405594, 790812, 1543766, 3016923, 5901858, 11556244, 22647431, 44418613, 87182680, 171234318, 336532357, 661788956, 1302124526, 2563365624, 5048704640

Offset: 0

Alois P. Heinz, Nov 14 2015

nonn

			a(5) = 2^5 - 8 = 24: 00000, 00001, 00011, 00110, 00111, 01100, 01101, 01110, 01111, 10000, 10001, 10011, 10100, 10101, 10110, 10111, 11000, 11001, 11010, 11011, 11100, 11101, 11110, 11111. These 8 words are not counted: 00010, 00100, 00101, 01000, 01001, 01010, 01011, 10010.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A118430, A164146, A255386, A260505, A260697, A303430.

b:= proc(n, t, c) option remember; `if`(c<0, 0, `if`(n=0, 1,
      b(n-1, [2, 4, 6, 4, 6, 4, 6][t], c-`if`(t=5, 1, 0))+
      b(n-1, [3, 5, 7, 5, 7, 5, 7][t], c+`if`(t=6, 1, 0))))
    end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..40);
# second Maple program:
a:= proc(n) option remember; `if`(n<6, [1, 2, 4, 7, 13, 24][n+1],
      ((680+1441*n-444*n^2+35*n^3)        *a(n-1)
       -(4*(-112+625*n-179*n^2+14*n^3))   *a(n-2)
       +(2*(1521-656*n+63*n^2))           *a(n-3)
       +(2*(-9442+5295*n-947*n^2+56*n^3)) *a(n-4)
       -(4*(-6721+3413*n-591*n^2+35*n^3)) *a(n-5)
       +(4*(2*n-11))*(7*n^2-79*n+254)     *a(n-6)
        )/((n+1)*(7*n^2-93*n+340)))
    end:
seq(a(n), n=0..40);

b[n_, t_, c_] := b[n, t, c] = If[c < 0, 0, If[n == 0, 1,
   b[n - 1, {2, 4, 6, 4, 6, 4, 6}[[t]], c - If[t == 5, 1, 0]] +
   b[n - 1, {3, 5, 7, 5, 7, 5, 7}[[t]], c + If[t == 6, 1, 0]]]];
a[n_] := b[n, 1, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Sep 16 2023, after Alois P. Heinz *)

A260697 Number of binary words w of length n with equal numbers of 010 and 101 subwords such that for every prefix of w the number of occurrences of subword 101 is larger than or equal to the number of occurrences of subword 010.

Original entry on oeis.org

1, 2, 4, 6, 11, 18, 32, 54, 95, 164, 291, 514, 923, 1656, 3000, 5442, 9942, 18216, 33564, 62040, 115167, 214404, 400497, 750070, 1408734, 2652088, 5004833, 9464616, 17935137, 34049044, 64754844, 123351410, 235335966, 449632300, 860241606, 1647932000

Offset: 0

Alois P. Heinz, Nov 16 2015

nonn

			a(3) = 6: 000, 001, 011, 100, 110, 111.
a(4) = 11: 0000, 0001, 0011, 0110, 0111, 1000, 1001, 1010, 1100, 1110, 1111.
a(5) = 18: 00000, 00001, 00011, 00110, 00111, 01100, 01110, 01111, 10000, 10001, 10011, 10100, 11000, 11001, 11010, 11100, 11110, 11111.
a(10) = 291: 0000000000, 0000000001, 0000000011, ..., 0110101010, 1010101000, 1010101001, 1010101010, 1101010100, 1110101010, ..., 1111111100, 1111111110, 1111111111.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A118430, A164146, A255386, A260505, A260668.

b:= proc(n, t, c) option remember;
     `if`(c<0, 0, `if`(n=0, `if`(c=0, 1, 0),
      b(n-1, [2, 4, 6, 4, 6, 4, 6][t], c-`if`(t=5, 1, 0))+
      b(n-1, [3, 5, 7, 5, 7, 5, 7][t], c+`if`(t=6, 1, 0))))
    end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..40);
# second Maple program:
a:= proc(n) option remember;
     `if`(n<7, [1, 2, 4, 6, 11, 18, 32][n+1],
     ((n+3)*(307*n^2-2357*n+196)              *a(n-1)
      -(19280-3372*n-5181*n^2+719*n^3)        *a(n-2)
      +(2*(6582+268*n^3-2857*n^2+6959*n))     *a(n-3)
      +(2*(-3307*n^2+1151*n+384*n^3+9052))    *a(n-4)
      -(2*(1016*n^3-12133*n^2+38927*n-28304)) *a(n-5)
      +(4*(27387*n+431*n^3-38420-6108*n^2))   *a(n-6)
      -(4*(n-7))*(67*n-236)*(2*n-11)          *a(n-7)
      )/((2*(n+4))*(24*n^2-148*n-279)))
    end:
seq(a(n), n=0..40);

b[n_, t_, c_] := b[n, t, c] =
     If[c < 0, 0, If[n == 0, If[c == 0, 1, 0],
     b[n - 1, {2, 4, 6, 4, 6, 4, 6}[[t]], c - If[t == 5, 1, 0]] +
     b[n - 1, {3, 5, 7, 5, 7, 5, 7}[[t]], c + If[t == 6, 1, 0]]]];
a[n_] := b[n, 1, 0];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 02 2022, after Alois P. Heinz *)

A118429 Triangle read by rows: T(n,k) is the number of binary sequences of length n containing k subsequences 010 (n,k >= 0).

Original entry on oeis.org

1, 2, 4, 7, 1, 12, 4, 21, 10, 1, 37, 22, 5, 65, 47, 15, 1, 114, 98, 38, 6, 200, 199, 91, 21, 1, 351, 396, 210, 60, 7, 616, 777, 468, 158, 28, 1, 1081, 1508, 1014, 396, 89, 8, 1897, 2900, 2151, 952, 255, 36, 1, 3329, 5534, 4487, 2212, 687, 126, 9, 5842, 10492, 9229

Offset: 0

Emeric Deutsch, Apr 27 2006

Row n has ceiling(n/2) terms (n >= 1).
Sum of entries in row n is 2^n (A000079).
T(n,0) = A005251(n+3), T(n,1) = A118430(n).
Sum_{k=0..n-1} k*T(n,k) = (n-2)*2^(n-3) (A001787).

			T(6,2) = 5 because we have 010010, 010100, 010101, 001010 and 101010.
Triangle starts:
   1;
   2;
   4;
   7,  1;
  12,  4;
  21, 10, 1;
  37, 22, 5;

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

Cf. A000079, A005251, A001787, A118430.

G:=(1+(1-t)*z^2)/(1-2*z+(1-t)*z^2-(1-t)*z^3): Gser:=simplify(series(G,z=0,18)): P[0]:=1: for n from 1 to 16 do P[n]:=sort(coeff(Gser,z^n)) od: 1; for n from 1 to 16 do seq(coeff(P[n],t,j),j=0..ceil(n/2)-1) od; # yields sequence in triangular form

nn=15;Map[Select[#,#>0&]&,CoefficientList[Series[1/(1-2z-(u-1)z^3/(1-(u-1)z^2)),{z,0,nn}],{z,u}]]//Grid (* Geoffrey Critzer, Dec 03 2013 *)

G.f.: G(t,z) = (1+(1-t)z^2)/(1 - 2z + (1-t)z^2 - (1-t)z^3).

Recurrence relation: T(n,k) = 2T(n-1,k) - T(n-2,k) + T(n-3,k) + T(n-2,k-1) - T(n-3,k-1) for n >= 3.

A260505 Number of binary words of length n with exactly one occurrence of subword 010 and exactly two occurrences of subword 101.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 7, 16, 38, 82, 175, 362, 736, 1468, 2885, 5596, 10736, 20398, 38423, 71818, 133307, 245890, 450970, 822788, 1493992, 2700800, 4862566, 8721608, 15588371, 27770338, 49320863, 87344004, 154263972, 271765362, 477622769, 837519742, 1465470968

Offset: 0

Alois P. Heinz, Nov 11 2015

			a(5) = 1: 10101.
a(6) = 2: 101011, 110101.
a(7) = 7: 0101101, 0110101, 1010110, 1010111, 1011010, 1101011, 1110101.
a(8) = 16: 00101101, 00110101, 01011011, 01011101, 01101011, 01110101, 10101100, 10101110, 10101111, 10110100, 10111010, 11010110, 11010111, 11011010, 11101011, 11110101.
a(9) = 38: 000101101, 000110101, 001011011, ..., 111011010, 111101011, 111110101.
a(10) = 82: 0000101101, 0000110101, 0001011011, ..., 1111011010, 1111101011, 1111110101.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-13,10,6,-18,11,6,-10,2,3,-2,-1).

Cf. A118430, A164146, A255386, A260668, A260697.

gf:= -x^5*(2*x^2-x+1)*(x-1)^3/((x^2-x+1)^2*(x^2+x-1)^4):
a:= n-> coeff(series(gf,x,n+1),x,n):
seq(a(n), n=0..40);

LinearRecurrence[{6,-13,10,6,-18,11,6,-10,2,3,-2,-1},{0,0,0,0,0,1,2,7,16,38,82,175},40] (* Harvey P. Dale, Jun 26 2025 *)

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

A118871 Number of binary sequences of length n containing exactly one subsequence 0101.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 10, 24, 57, 128, 278, 596, 1260, 2628, 5430, 11136, 22683, 45936, 92574, 185764, 371347, 739840, 1469580, 2911224, 5753048, 11343800, 22322444, 43845120, 85973013, 168314604, 329041842, 642385248, 1252552077, 2439430272, 4745767138, 9223159852

Offset: 0

Emeric Deutsch, May 03 2006

nonn

With only two 0's at the beginning, the convolution of A112575 with itself. Column 1 of A118869.

			a(5) = 4 because we have 01010, 01011, 00101 and 10101.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,8,-11,8,-6,4,-1).

Cf. A112575, A118430, A118869, A118870.

R:=PowerSeriesRing(Integers(), 40); [0,0,0,0] cat Coefficients(R!( x^4/(1 -2*x +x^2 -2*x^3 +x^4)^2 )); // G. C. Greubel, Jan 14 2022

g:=z^4/(1-2*z+z^2-2*z^3+z^4)^2: gser:=series(g,z=0,40): seq(coeff(gser, z, n), n=0..35);

LinearRecurrence[{4,-6,8,-11,8,-6,4,-1}, {0,0,0,0,1,4,10,24}, 40] (* G. C. Greubel, Jan 14 2022 *)

@CachedFunction
def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))
def A118871(n): return sum( A112575(j+1)*A112575(n-j-3) for j in (0..n-4) )
[A118871(n) for n in (0..40)] # G. C. Greubel, Jan 14 2022

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

a(n) = Sum_{j=0..n-4} A112575(j+1)*A112575(n-j-3). - G. C. Greubel, Jan 14 2022

A143361 Triangle read by rows: T(n,k) is the number of 010-avoiding binary words of length n containing k 00 subwords (0<=k<=n-1).

Original entry on oeis.org

2, 3, 1, 4, 2, 1, 6, 3, 2, 1, 9, 6, 3, 2, 1, 13, 11, 7, 3, 2, 1, 19, 18, 14, 8, 3, 2, 1, 28, 30, 24, 17, 9, 3, 2, 1, 41, 50, 43, 30, 20, 10, 3, 2, 1, 60, 81, 77, 57, 36, 23, 11, 3, 2, 1, 88, 130, 132, 108, 72, 42, 26, 12, 3, 2, 1, 129, 208, 224, 193, 143, 88, 48, 29, 13, 3, 2, 1

Offset: 1

Emeric Deutsch, Aug 15 2008

Sum of entries in row n = A005251(n+3).
T(n,0) = A000930(n+2).
Sum(k*T(n,k), k=0..n-1) = A118430(n+1).

			T(5,2)=3 because we have 00011, 10001 and 11000.
Triangle starts:
2;
3,   1;
4,   2, 1;
6,   3, 2, 1;
9,   6, 3, 2, 1;
13, 11, 7, 3, 2, 1;

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

Cf. A005251, A000930, A118430.

G:=(1+z-t*z+z^2)/(1-z-t*z+t*z^2-z^3)-1: Gser:=simplify(series(G,z=0,14)): for n to 12 do P[n]:=sort(coeff(Gser,z,n)) end do: for n to 12 do seq(coeff(P[n], t,j),j=0..n-1) end do; # yields sequence in triangular form
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<3,
      expand(b(n-1, i+1) +b(n-1, i)*`if`(i=2, x, 1)), b(n-1, 1)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Dec 18 2013

b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<3, Expand[b[n-1, i+1] + b[n-1, i]*If[i == 2, x, 1]], b[n-1, 1]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 1]]; Table[T[n], {n, 1, 15}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

G.f.: G(t,z) = (1+z-tz+z^2)/(1-z-tz+tz^2-z^3)-1.

cp's OEIS Frontend

A164146 Number of binary strings of length n with equal numbers of 010 and 101 substrings.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A136444 a(n) = Sum_{k=0..n} k*binomial(n-k, 2*k).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A255386 Number of binary words of length n with exactly one occurrence of subword 010 and exactly one occurrence of subword 101.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260668 Number of binary words of length n such that for every prefix the number of occurrences of subword 101 is larger than or equal to the number of occurrences of subword 010.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A260697 Number of binary words w of length n with equal numbers of 010 and 101 subwords such that for every prefix of w the number of occurrences of subword 101 is larger than or equal to the number of occurrences of subword 010.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A118429 Triangle read by rows: T(n,k) is the number of binary sequences of length n containing k subsequences 010 (n,k >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A260505 Number of binary words of length n with exactly one occurrence of subword 010 and exactly two occurrences of subword 101.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A118871 Number of binary sequences of length n containing exactly one subsequence 0101.

Views

A136444 a(n) = Sum_{k=0..n} kbinomial(n-k, 2k).