A303696
Number A(n,k) of binary words of length n with k times as many occurrences of subword 101 as occurrences of subword 010; square array A(n,k), n>=0, k>=0, read by antidiagonals.
Original entry on oeis.org
1, 1, 2, 1, 2, 4, 1, 2, 4, 7, 1, 2, 4, 6, 12, 1, 2, 4, 6, 12, 21, 1, 2, 4, 6, 10, 20, 37, 1, 2, 4, 6, 10, 17, 38, 65, 1, 2, 4, 6, 10, 16, 28, 66, 114, 1, 2, 4, 6, 10, 16, 26, 49, 124, 200, 1, 2, 4, 6, 10, 16, 26, 42, 84, 224, 351, 1, 2, 4, 6, 10, 16, 26, 42, 70, 148, 424, 616
Offset: 0
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
2, 2, 2, 2, 2, 2, 2, ...
4, 4, 4, 4, 4, 4, 4, ...
7, 6, 6, 6, 6, 6, 6, ...
12, 12, 10, 10, 10, 10, 10, ...
21, 20, 17, 16, 16, 16, 16, ...
37, 38, 28, 26, 26, 26, 26, ...
65, 66, 49, 42, 42, 42, 42, ...
114, 124, 84, 70, 68, 68, 68, ...
200, 224, 148, 116, 110, 110, 110, ...
351, 424, 263, 196, 178, 178, 178, ...
-
b:= proc(n, t, h, c, k) option remember; `if`(abs(c)>k*n, 0,
`if`(n=0, 1, b(n-1, [1, 3, 1][t], 2, c-`if`(h=3, k, 0), k)
+ b(n-1, 2, [1, 3, 1][h], c+`if`(t=3, 1, 0), k)))
end:
A:= (n, k)-> b(n, 1$2, 0, min(k, n)):
seq(seq(A(n, d-n), n=0..d), d=0..14);
-
b[n_, t_, h_, c_, k_] := b[n, t, h, c, k] = If[Abs[c] > k n, 0, If[n == 0, 1, b[n - 1, {1, 3, 1}[[t]], 2, c - If[h == 3, k, 0], k] + b[n - 1, 2, {1, 3, 1}[[h]], c + If[t == 3, 1, 0], k]]];
A[n_, k_] := b[n, 1, 1, 0, Min[k, n]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Mar 20 2020, from Maple *)
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 *)
A307796
Number T(n,k) of binary words of length n such that k is the difference of numbers of occurrences of subword 101 and subword 010; triangle T(n,k), n>=0, -floor(n/3)<=k<=floor(n/3), read by rows.
Original entry on oeis.org
1, 2, 4, 1, 6, 1, 2, 12, 2, 6, 20, 6, 1, 12, 38, 12, 1, 3, 28, 66, 28, 3, 10, 56, 124, 56, 10, 1, 24, 119, 224, 119, 24, 1, 4, 60, 236, 424, 236, 60, 4, 15, 134, 481, 788, 481, 134, 15, 1, 42, 304, 950, 1502, 950, 304, 42, 1, 5, 114, 656, 1902, 2838, 1902, 656, 114, 5
Offset: 0
T(8,2) = 10: 01101101, 10101101, 10110101, 10110110, 10110111, 10111011, 10111101, 11011011, 11011101, 11101101.
T(8,-2) = 10: 00010010, 00100010, 00100100, 01000010, 01000100, 01001000, 01001001, 01001010, 01010010, 10010010.
T(9,3) = 1: 101101101.
T(9,-3) = 1: 010010010.
Triangle T(n,k) begins:
: 1 ;
: 2 ;
: 4 ;
: 1, 6, 1 ;
: 2, 12, 2 ;
: 6, 20, 6 ;
: 1, 12, 38, 12, 1 ;
: 3, 28, 66, 28, 3 ;
: 10, 56, 124, 56, 10 ;
: 1, 24, 119, 224, 119, 24, 1 ;
: 4, 60, 236, 424, 236, 60, 4 ;
: 15, 134, 481, 788, 481, 134, 15 ;
: 1, 42, 304, 950, 1502, 950, 304, 42, 1 ;
T(3n-4,n-2) gives
A000217 for n >= 3.
-
b:= proc(n, t, h) option remember; `if`(n=0, 1, expand(
`if`(h=3, 1/x, 1)*b(n-1, [1, 3, 1][t], 2)+
`if`(t=3, x, 1)*b(n-1, 2, [1, 3, 1][h])))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=-iquo(n, 3)..iquo(n, 3)))(b(n, 1$2)):
seq(T(n), n=0..15);
-
b[n_, t_, h_] := b[n, t, h] = If[n == 0, 1, Expand[If[h == 3, 1/x, 1]* b[n-1, {1, 3, 1}[[t]], 2] + If[t == 3, x, 1]*b[n-1, 2, {1, 3, 1}[[h]]]]];
T[n_] := Table[Coefficient[#, x, i], {i, -Quotient[n, 3], Quotient[n, 3]}]& @ b[n, 1, 1];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 08 2019, 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 *)
A303430
Number of binary words of length n with exactly twice as many occurrences of subword 101 as occurrences of subword 010.
Original entry on oeis.org
1, 2, 4, 6, 10, 17, 28, 49, 84, 148, 263, 472, 858, 1568, 2893, 5372, 10034, 18824, 35428, 66898, 126683, 240483, 457334, 870956, 1660850, 3171112, 6061596, 11597587, 22206775, 42551339, 81591256, 156553245, 300565760, 577360360, 1109601934, 2133499936
Offset: 0
a(0) = 1: the empty word.
a(1) = 2: 0, 1.
a(2) = 4: 00, 01, 10, 11.
a(3) = 6: 000, 001, 011, 100, 110, 111.
a(4) = 10: 0000, 0001, 0011, 0110, 0111, 1000, 1001, 1100, 1110, 1111.
a(5) = 17: 00000, 00001, 00011, 00110, 00111, 01100, 01110, 01111, 10000, 10001, 10011, 10101, 11000, 11001, 11100, 11110, 11111.
-
b:= proc(n, t, h, c) option remember; `if`(abs(c)>2*n, 0,
`if`(n=0, 1, b(n-1, [1, 3, 1][t], 2, c-`if`(h=3, 2, 0))
+ b(n-1, 2, [1, 3, 1][h], c+`if`(t=3, 1, 0))))
end:
a:= n-> b(n, 1$2, 0):
seq(a(n), n=0..50);
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
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).
-
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 *)
Showing 1-7 of 7 results.
Comments