

A317783


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


3



1, 1, 1, 3, 7, 13, 23, 41, 75, 139, 257, 473, 869, 1597, 2937, 5403, 9939, 18281, 33623, 61841, 113743, 209207, 384793, 707745, 1301745, 2394281, 4403769, 8099795, 14897847, 27401413, 50399055, 92698313, 170498779, 313596147, 576793241, 1060888169, 1951277557
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Two binary words of the same length are equivalent with respect to a given subword set if they have equal sets of occurrences for all each single subword.
All terms are odd.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (2,1,1,0,1).


FORMULA

G.f.: (x^4x^3+x1)/(x^5+x^3x^2+2*x1).
a(n) = 2*a(n1) a(n2) +a(n3) +a(n5) for n >= 5.


EXAMPLE

a(6) = 23: [], [0], [0], [1], [2], [3], [1], [2], [3], [03], [03], [10], [01], [21], [12], [32], [23], [021], [102], [132], [213], [1302], [0213]. Here [132] 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).


MAPLE

a:= n> (<<01000>, <00100>, <00010>,
<00001>, <10112>>^n.<<1, 1, 1, 3, 7>>)[1$2]:
seq(a(n), n=0..45);
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [1$3, 3, 7][n+1],
2*a(n1) a(n2) +a(n3) +a(n5))
end:
seq(a(n), n=0..45);


CROSSREFS

Cf. A000045, A128588, A164146, A303696, A317669, A317779.
Sequence in context: A227121 A078447 A066624 * A061761 A081494 A161909
Adjacent sequences: A317780 A317781 A317782 * A317784 A317785 A317786


KEYWORD

nonn,easy


AUTHOR

Alois P. Heinz, Aug 06 2018


STATUS

approved



