A317783 -id:A317783 - cp's OEIS frontend

A317669 Number of equivalence classes of binary words of length n for the subword 10110.

1, 1, 1, 1, 1, 2, 3, 4, 6, 8, 11, 16, 22, 31, 44, 61, 86, 121, 169, 238, 334, 468, 658, 923, 1295, 1819, 2552, 3582, 5029, 7057, 9906, 13905, 19515, 27393, 38449, 53965, 75748, 106319, 149228, 209460, 293996, 412653, 579204, 812968, 1141085, 1601632, 2248049

Offset: 0

Alois P. Heinz, Aug 03 2018

Two binary words of the same length are equivalent with respect to a given subword if they have equal sets of occurrences of this subword.

			a(11) = 16, the positions of subword 10110 in words of the 16 classes are given by the sets: {}, {0}, {1}, {2}, {3}, {4}, {5}, {6}, {0,3}, {1,4}, {0,5}, {2,5}, {0,6}, {1,6}, {3,6}, {0,3,6}, where 0 indicates the leftmost position. Example words for class {2,5} are xx10110110x, where each x can be replaced by 0 or by 1 and both occurrences of the subword overlap. There is only one word in class {0,3,6}: 10110110110.  Class {1,6} has two words: 01011010110 and 11011010110.

Alois P. Heinz, Table of n, a(n) for n = 0..2500
Michael A. Allen, Combinations without specified separations and restricted-overlap tiling with combs, arXiv:2210.08167 [math.CO], 2022.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,1).

Cf. A209888, A277751, A317783, A317779.

b:= proc(n, t) option remember; `if`(n<0, 0, `if`(n=0, 1,
      add(b(n-j, j), j={1, 5, `if`(t=1, 1, 3)})))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..60);
# second Maple program:
a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
          <0|0|0|0|1>, <1|-1|1|0|1>>^n.<<[1$5][]>>)[1$2]:
seq(a(n), n=0..60);
# third Maple program:
a:= proc(n) option remember; `if`(n<5, 1, a(n-1) +a(n-3) -a(n-4) +a(n-5)) end:
seq(a(n), n=0..60);

LinearRecurrence[{1, 0, 1, -1, 1}, {1, 1, 1, 1, 1}, 100] (* Jean-François Alcover, Sep 23 2022 *)

G.f.: (x^3-1)/(x^5-x^4+x^3+x-1).

a(n) = a(n-1) +a(n-3) -a(n-4) +a(n-5) for n >= 5, a(n) = 1 for n < 5.

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

Original entry on oeis.org

1, 1, 1, 3, 7, 14, 26, 47, 86, 160, 300, 562, 1051, 1962, 3661, 6833, 12757, 23820, 44477, 83045, 155052, 289493, 540506, 1009172, 1884217, 3518007, 6568439, 12263866, 22897737, 42752130, 79822071, 149034991, 278261743, 519539714, 970027388, 1811128400

Offset: 0

Alois P. Heinz, Aug 08 2018

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.

			a(7) = 47: [||], [|0|], [0||], [|1|], [|2|], [|3|], [|4|], [1||], [2||], [3||], [4||], [|0|0], [|04|], [03||], [04||], [14||], [1|0|], [0|1|], [2|1|], [1|2|], [3|2|], [2|3|], [4|3|], [3|4|], [|1|1], [|2|2], [02|1|], [1|02|], [13|2|], [2|13|], [14|0|], [24|3|], [03|4|], [3|24|], [|03|0], [|14|1], [0|1|1], [1|2|2], [13|02|], [02|13|], [24|13|], [13|24|], [1|02|2], [4|03|0], [0|14|1], [024|13|], [13|024|].  Here [1|02|2] describes the class whose members have an occurrence of 010 at position 1 and occurrences of 101 at positions 0 and 2 and an occurrence of 10110 at position 2 and no other occurrences of the subwords: 1010110.

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

Cf. A000045, A317669, A317783.

a:= n-> coeff(series((x^9+2*x^8+2*x^7-x^6-3*x^5-2*x^4+x^2-1)/
             (-x^10-x^9-x^8+x^7+x^6+x^3+x^2+x-1),x,n+1),x,n):
seq(a(n), n=0..35);

G.f.: (x^9+2*x^8+2*x^7-x^6-3*x^5-2*x^4+x^2-1)/(-x^10-x^9-x^8+x^7+x^6+x^3+x^2+x-1).

cp's OEIS Frontend

A317669 Number of equivalence classes of binary words of length n for the subword 10110.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula