OFFSET
0,6
COMMENTS
Two binary words of the same length are equivalent with respect to a given subword if they have equal sets of occurrences of this subword.
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).
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.
EXAMPLE
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.
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 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Aug 03 2018
STATUS
approved