login
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
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 each single subword.
All terms are odd.
FORMULA
G.f.: (-x^4-x^3+x-1)/(x^5+x^3-x^2+2*x-1).
a(n) = 2*a(n-1) -a(n-2) +a(n-3) +a(n-5) for n >= 5.
EXAMPLE
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).
MAPLE
a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
<0|0|0|0|1>, <1|0|1|-1|2>>^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(n-1) -a(n-2) +a(n-3) +a(n-5))
end:
seq(a(n), n=0..45);
MATHEMATICA
LinearRecurrence[{2, -1, 1, 0, 1}, {1, 1, 1, 3, 7}, 40] (* Jean-François Alcover, Apr 30 2022 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Aug 06 2018
STATUS
approved