A118430
Number of binary sequences of length n containing exactly one subsequence 010.
Original entry on oeis.org
0, 0, 0, 1, 4, 10, 22, 47, 98, 199, 396, 777, 1508, 2900, 5534, 10492, 19782, 37119, 69358, 129118, 239578, 443229, 817822, 1505389, 2764986, 5068435, 9273928, 16940488, 30897020, 56271128, 102347564, 185922589, 337353688, 611462514
Offset: 0
a(4) = 4 because we have 0100, 0101, 0010 and 1010.
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- T. Mansour and M. Shattuck, Counting Peaks and Valleys in a Partition of a Set, J. Int. Seq. 13 (2010), 10.6.8, Lemma 2.1, k=2, 1 peak.
- Index entries for linear recurrences with constant coefficients, signature (4,-6,6,-5,2,-1).
-
g:=z^3/(1-2*z+z^2-z^3)^2: gser:=series(g,z=0,40): seq(coeff(gser,z,n),n=0..38);
-
LinearRecurrence[{4, -6, 6, -5, 2, -1}, {0, 0, 0, 1, 4, 10}, 40] (* Jean-François Alcover, May 11 2019 *)
A164146
Number of binary strings of length n with equal numbers of 010 and 101 substrings.
Original entry on oeis.org
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
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
-
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 *)
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
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.
-
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
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.
-
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 *)
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
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).
-
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 *)
Showing 1-5 of 5 results.
Comments