A381936 Number of primitive binary words of length n that avoid 11, start with 1 and end with 0.

0, 1, 1, 1, 3, 3, 8, 11, 20, 30, 55, 83, 144, 224, 373, 597, 987, 1572, 2584, 4146, 6756, 10890, 17711, 28557, 46365, 74880, 121372, 196184, 317811, 513818, 832040, 1345659, 2178253, 3523590, 5702876, 9225784, 14930352, 24155232, 39088024, 63241794, 102334155, 165573148, 267914296

Offset

1,5

Comments

Here primitive means the word is not two or more repetitions of a smaller word.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Formula

a(n) = Sum_{d|n} mu(d) * Fibonacci(n/d-1).

Example

For n=5, the a(6) = 3 words are: 100000, 100010, 101000.
Notice 100100 is not included since it is repetitions of the smaller word 100 (from n=3).

Prog

(PARI) a(n) = sumdiv(n, d, moebius(d)*fibonacci(n/d-1)) \\ Andrew Howroyd, Mar 10 2025
(Python)
from sympy import mobius, fibonacci, divisors
def A381936(n): return sum(mobius(n//d)*fibonacci(d-1) for d in divisors(n, generator=True)) # Chai Wah Wu, Mar 18 2025

Crossrefs

Cf. A000045, A007436, A008683, A056267, A113166.

Sequence in context: A233174 A185350 A279910 * A105039 A358834 A384330

Adjacent sequences: A381933 A381934 A381935 * A381937 A381938 A381939

Keyword

nonn

Author

Aidan Diekmann, Mar 10 2025

Status

approved