login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A317669 Number of equivalence classes of binary words of length n for the subword 10110. 5
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

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.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..2500

Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,1).

FORMULA

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.

EXAMPLE

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.

MAPLE

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

CROSSREFS

Cf. A209888, A277751, A317783, A317779.

Sequence in context: A271486 A226187 A294922 * A208887 A017911 A057048

Adjacent sequences:  A317666 A317667 A317668 * A317670 A317671 A317672

KEYWORD

nonn,easy

AUTHOR

Alois P. Heinz, Aug 03 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 14:23 EDT 2019. Contains 322349 sequences. (Running on oeis4.)