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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 all 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);

CROSSREFS

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

Sequence in context: A227121 A078447 A066624 * A061761 A081494 A161909

Adjacent sequences:  A317780 A317781 A317782 * A317784 A317785 A317786

KEYWORD

nonn,easy

AUTHOR

Alois P. Heinz, Aug 06 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 December 7 22:29 EST 2019. Contains 329850 sequences. (Running on oeis4.)