1

I am trying to find the number of linear sequences of length $100$ with a period of $10$ constructed using an alphabet of $a$ characters.

Here are my thoughts. The number of sequences of length $n$ and period $d$ is the same as the number of sequences of length $d$ and period $d$. So I need to find the number of linear sequences of length $10$ and period $10$.

Total number of linear sequences of length $n$ constructed with the alphabet of $a$ is $T(n) = a^n$. This total number consists of sequences with various periods (divisors of the $n$). Let $D(p)$ is the set of all the sequences of length $n$ with a period of $d$. So $T(n) = \sum_{d|n}D(d)$

But the number of sequences of linear sequences of length $n$ and period $d$ is the same as the number of linear sequences of length $d$ and period $d$. So if $W(d)$ is the same as the number of linear sequences of length $d$ and period $d$, then:

$$|T(n)| = a^n = \sum_{d|n}|W(d)|$$

So

$a^1 = |W(1)|$

$a^2 = |W(1)| + |W(2)|$

$a^5 = |W(1)| + |W(5)|$

$a^{10} = |W(1)| + |W(2)| + |W(5)| + |W(10)|$

So |W(10)| is $a^{10} - a^5 - a^2 + a$. And this is basically the answer.

But it looks like it is not correct.

Can anyone explain a correct approach?

Salvador Dali
  • 2,645

1 Answers1

1

Call a sequence primitive if it isn't a repetition of a shorter sequence, and use $p_n$ for the number of primitive sequences of length $n$. As any sequence is repetitions of a primitive sequence (of length $d$ that divides its length), and in all there are $a^n$ sequences of length $n$, we can write:

$\begin{align} a^n = \sum_{d \mid n} p_d \end{align}$

By Möbius inversion we have:

$\begin{align} p_n = \sum_{d \mid n} \mu(n/d) a^d \end{align}$

In your particular case, you are interested in the number of primitive sequences of length $10$:

$\begin{align} p_{10} &= \sum_{d \mid 10} \mu(10/d) a^d \\ &= \mu(10) a^1 + \mu(5) a^2 + \mu(2) a^5 + \mu(1) a^{10} \\ &= a^1 + (-1) a^2 + (-1) a^5 + a^{10} \\ &= a^{10} - a^5 - a^2 + a \end{align}$

vonbrand
  • 27,812
  • Thank you. Just because my resulting answer looks almost the same as yours (apart of the $+a$), do you see any error in my logic? – Salvador Dali Jan 06 '16 at 20:54
  • @SalvadorDali, your discussion is essentially the same as mine, just restricted to the particular case $n = 10$, So, yes, I think yours is fine. I made a mistake, $\mu(10) = 1$, not $0$. Fixed now. – vonbrand Jan 06 '16 at 20:56