A318134 - OEIS

A318134

Number of periodic sequences of period 3n generated by the random period doubling substitution 0 --> {01, 10}, 1 --> {00}.

3, 15, 21, 375, 108, 2427, 402, 176391, 1533, 216030, 10992, 19375935, 24612, 13106514

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

From an initial seed letter 0, the random substitution iteratively acts on words and outputs all possible outcomes from applying all combinations of the allowed substitution rules independently to each letter in a word. So we have:

0 -->

{01, 10} -->

{0100, 1000, 0001, 0010} -->

{01000101, 01000110, 01001001, 01001010, 10000101, 10000110, 10001001, 10001010, 00010101, 00010110, 00011001, 00011010, 00100101, 00100110, 00101001, 00101010, 01010100, 01011000, 01100100, 01101000, 10010100, 10011000, 10100100, 10101000, 01010001, 01010010, 01100001, 01100010, 10010001, 10010010, 10100001, 10100010} --> ...

An infinite sequence is generated by the random substitution if all subwords of the sequence appear as subwords of some word appearing in the infinite list generated above. Some of these infinite sequences will be periodic and so we can enumerate them.

All periodic sequences have period a multiple of 3.

LINKS

Table of n, a(n) for n=1..14.

D. Rust, Periodic points in random substitution subshifts, (2018).

EXAMPLE

The periodic sequences of length 3 generated by the random period doubling substitution have periodic blocks 001, 010, 100.

The periodic sequences of length 6 generated by the random period doubling substitution have periodic blocks 010100, 101000, 010001, 100010, 000101, 001010, 011000, 110000, 100001, 000011, 000110, 001100, 100100, 001001, 010010.

CROSSREFS

Cf. A096268, A275202.

Sequence in context: A117801 A347303 A277585 * A087674 A212846 A276804

Adjacent sequences: A318131 A318132 A318133 * A318135 A318136 A318137

KEYWORD

nonn,more

AUTHOR

Dan Rust, Aug 18 2018

STATUS

approved