cp's OEIS Frontend

A317669 Number of equivalence classes of binary words of length n for the subword 10110.

%I A317669 #24 Oct 21 2022 14:33:46
%S A317669 1,1,1,1,1,2,3,4,6,8,11,16,22,31,44,61,86,121,169,238,334,468,658,923,
%T A317669 1295,1819,2552,3582,5029,7057,9906,13905,19515,27393,38449,53965,
%U A317669 75748,106319,149228,209460,293996,412653,579204,812968,1141085,1601632,2248049
%N A317669 Number of equivalence classes of binary words of length n for the subword 10110.
%C A317669 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.
%H A317669 Alois P. Heinz, <a href="/A317669/b317669.txt">Table of n, a(n) for n = 0..2500</a>
%H A317669 Michael A. Allen, <a href="https://arxiv.org/abs/2210.08167">Combinations without specified separations and restricted-overlap tiling with combs</a>, arXiv:2210.08167 [math.CO], 2022.
%H A317669 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,1,-1,1).
%F A317669 G.f.: (x^3-1)/(x^5-x^4+x^3+x-1).
%F A317669 a(n) = a(n-1) +a(n-3) -a(n-4) +a(n-5) for n >= 5, a(n) = 1 for n < 5.
%e A317669 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.
%p A317669 b:= proc(n, t) option remember; `if`(n<0, 0, `if`(n=0, 1,
%p A317669       add(b(n-j, j), j={1, 5, `if`(t=1, 1, 3)})))
%p A317669     end:
%p A317669 a:= n-> b(n, 1):
%p A317669 seq(a(n), n=0..60);
%p A317669 # second Maple program:
%p A317669 a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
%p A317669           <0|0|0|0|1>, <1|-1|1|0|1>>^n.<<[1$5][]>>)[1$2]:
%p A317669 seq(a(n), n=0..60);
%p A317669 # third Maple program:
%p A317669 a:= proc(n) option remember; `if`(n<5, 1, a(n-1) +a(n-3) -a(n-4) +a(n-5)) end:
%p A317669 seq(a(n), n=0..60);
%t A317669 LinearRecurrence[{1, 0, 1, -1, 1}, {1, 1, 1, 1, 1}, 100] (* _Jean-François Alcover_, Sep 23 2022 *)
%Y A317669 Cf. A209888, A277751, A317783, A317779.
%K A317669 nonn,easy
%O A317669 0,6
%A A317669 _Alois P. Heinz_, Aug 03 2018