A317669 Number of equivalence classes of binary words of length n for the subword 10110.
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
Examples
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.
Links
- 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).
Programs
-
Maple
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); -
Mathematica
LinearRecurrence[{1, 0, 1, -1, 1}, {1, 1, 1, 1, 1}, 100] (* Jean-François Alcover, Sep 23 2022 *)
Formula
G.f.: (x^3-1)/(x^5-x^4+x^3+x-1).
a(n) = a(n-1) +a(n-3) -a(n-4) +a(n-5) for n >= 5, a(n) = 1 for n < 5.
Comments