|
|
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 each single subword.
All terms are odd.
|
|
LINKS
|
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|