A317669
Number of equivalence classes of binary words of length n for the subword 10110.
Original entry on oeis.org
1, 1, 1, 1, 1, 2, 3, 4, 6, 8, 11, 16, 22, 31, 44, 61, 86, 121, 169, 238, 334, 468, 658, 923, 1295, 1819, 2552, 3582, 5029, 7057, 9906, 13905, 19515, 27393, 38449, 53965, 75748, 106319, 149228, 209460, 293996, 412653, 579204, 812968, 1141085, 1601632, 2248049
Offset: 0
a(11) = 16, the positions of subword 10110 in words of the 16 classes are given by the sets: {}, {0}, {1}, {2}, {3}, {4}, {5}, {6}, {0,3}, {1,4}, {0,5}, {2,5}, {0,6}, {1,6}, {3,6}, {0,3,6}, where 0 indicates the leftmost position. Example words for class {2,5} are xx10110110x, where each x can be replaced by 0 or by 1 and both occurrences of the subword overlap. There is only one word in class {0,3,6}: 10110110110. Class {1,6} has two words: 01011010110 and 11011010110.
- Alois P. Heinz, Table of n, a(n) for n = 0..2500
- Michael A. Allen, Combinations without specified separations and restricted-overlap tiling with combs, arXiv:2210.08167 [math.CO], 2022.
- Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,1).
-
b:= proc(n, t) option remember; `if`(n<0, 0, `if`(n=0, 1,
add(b(n-j, j), j={1, 5, `if`(t=1, 1, 3)})))
end:
a:= n-> b(n, 1):
seq(a(n), n=0..60);
# second Maple program:
a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
<0|0|0|0|1>, <1|-1|1|0|1>>^n.<<[1$5][]>>)[1$2]:
seq(a(n), n=0..60);
# third Maple program:
a:= proc(n) option remember; `if`(n<5, 1, a(n-1) +a(n-3) -a(n-4) +a(n-5)) end:
seq(a(n), n=0..60);
-
LinearRecurrence[{1, 0, 1, -1, 1}, {1, 1, 1, 1, 1}, 100] (* Jean-François Alcover, Sep 23 2022 *)
A209888
Number of binary words of length n containing no subword 01101.
Original entry on oeis.org
1, 2, 4, 8, 16, 31, 60, 116, 225, 436, 845, 1637, 3172, 6146, 11909, 23075, 44711, 86633, 167863, 325256, 630226, 1221144, 2366125, 4584673, 8883398, 17212733, 33351899, 64623621, 125216632, 242623433, 470114310, 910907331, 1765000872, 3419917668, 6626533192
Offset: 0
a(6) = 60 because among the 2^6 = 64 binary words of length 6 only 4, namely 001101, 011010, 011011 and 101101 contain the subword 01101.
-
a:= n-> (Matrix(5, (i, j)-> `if`(i=j-1, 1, `if`(i=5, [-1, 2, -1, 0, 2][j], 0)))^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);
-
CoefficientList[Series[(x + 1)*(x^2 - x + 1)/(x^5 - 2*x^4 + x^3 - 2*x + 1), {x, 0, 40}], x] (* Wesley Ivan Hurt, Apr 28 2017 *)
LinearRecurrence[{2,0,-1,2,-1},{1,2,4,8,16},40] (* Harvey P. Dale, Sep 17 2017 *)
A317780
Number of binary words of length n containing exactly one occurrence of the subword 01101.
Original entry on oeis.org
1, 4, 12, 30, 72, 166, 375, 828, 1802, 3872, 8243, 17404, 36501, 76104, 157888, 326126, 671054, 1376090, 2813303, 5735864, 11665683, 23672756, 47940341, 96904034, 195540645, 393953334, 792531849, 1592204570, 3194717138, 6402570594, 12817347502, 25632678412
Offset: 5
- Alois P. Heinz, Table of n, a(n) for n = 5..2000
- Index entries for linear recurrences with constant coefficients, signature (4,-4,-2,8,-10,3,4,-6,4,-1).
A317781
Number of binary words of length n containing exactly two (possibly overlapping) occurrences of the subword 01101.
Original entry on oeis.org
1, 4, 13, 35, 92, 230, 562, 1333, 3106, 7114, 16090, 35968, 79637, 174812, 380903, 824469, 1774122, 3797436, 8089574, 17158409, 36250415, 76309260, 160102335, 334877607, 698461293, 1452964434, 3015112497, 6242510786, 12896941964, 26591579894, 54724833014
Offset: 8
- Alois P. Heinz, Table of n, a(n) for n = 8..2000
- Index entries for linear recurrences with constant coefficients, signature (6,-12,5,18,-39,33,6,-42,47,-21,-9,20,-15,6,-1).
Showing 1-4 of 4 results.
Comments