0,6

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.

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).

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.

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.

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);

# Alternative:

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);

# Alternative:

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 *)

Cf. A209888, A277751, A317783, A317779.

Sequence in context: A271486 A226187 A294922 * A208887 A017911 A057048

Adjacent sequences: A317666 A317667 A317668 * A317670 A317671 A317672

nonn,easy

Alois P. Heinz, Aug 03 2018

approved