cp's OEIS Frontend

A317783 Number of equivalence classes of binary words of length n for the set of subwords {010, 101}.

%I A317783 #27 Apr 30 2022 07:58:07
%S A317783 1,1,1,3,7,13,23,41,75,139,257,473,869,1597,2937,5403,9939,18281,
%T A317783 33623,61841,113743,209207,384793,707745,1301745,2394281,4403769,
%U A317783 8099795,14897847,27401413,50399055,92698313,170498779,313596147,576793241,1060888169,1951277557
%N A317783 Number of equivalence classes of binary words of length n for the set of subwords {010, 101}.
%C A317783 Two binary words of the same length are equivalent with respect to a given subword set if they have equal sets of occurrences for each single subword.
%C A317783 All terms are odd.
%H A317783 Alois P. Heinz, <a href="/A317783/b317783.txt">Table of n, a(n) for n = 0..2000</a>
%H A317783 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,1,0,1).
%F A317783 G.f.: (-x^4-x^3+x-1)/(x^5+x^3-x^2+2*x-1).
%F A317783 a(n) = 2*a(n-1) -a(n-2) +a(n-3) +a(n-5) for n >= 5.
%e A317783 a(6) = 23: [|], [|0], [0|], [|1], [|2], [|3], [1|], [2|], [3|], [|03], [03|], [1|0], [0|1], [2|1], [1|2], [3|2], [2|3], [02|1], [1|02], [13|2], [2|13], [13|02], [02|13].  Here [13|2] describes the class whose members have occurrences of 010 at positions 1 and 3 and an occurrence of 101 at position 2 and no other occurrences of both subwords: 001010.  [|] describes the class that avoids both subwords and has 26 members for n=6, in general 2*A000045(n+1) (for n>0).
%p A317783 a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
%p A317783           <0|0|0|0|1>, <1|0|1|-1|2>>^n.<<1, 1, 1, 3, 7>>)[1$2]:
%p A317783 seq(a(n), n=0..45);
%p A317783 # second Maple program:
%p A317783 a:= proc(n) option remember; `if`(n<5, [1$3, 3, 7][n+1],
%p A317783       2*a(n-1) -a(n-2) +a(n-3) +a(n-5))
%p A317783     end:
%p A317783 seq(a(n), n=0..45);
%t A317783 LinearRecurrence[{2, -1, 1, 0, 1}, {1, 1, 1, 3, 7}, 40] (* _Jean-François Alcover_, Apr 30 2022 *)
%Y A317783 Cf. A000045, A128588, A164146, A303696, A317669, A317779.
%K A317783 nonn,easy
%O A317783 0,4
%A A317783 _Alois P. Heinz_, Aug 06 2018