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

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

Author

Alois P. Heinz, Aug 06 2018

Keywords

• nonn
• easy

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.

Examples

			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).
		

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).

Crossrefs

Cf. A000045, A128588, A164146, A303696, A317669, A317779.

Programs

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 *)

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.