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
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^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