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
Keywords
Examples
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).
Programs
-
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
Formula
a(n) = Sum_{d|n} mu(d) * Fibonacci(n/d-1).
Comments