2
$\begingroup$

Em Português: Seja $n$ um natural fixado. Dizemos que uma sequência $(x_1 , ..., x_n)$ tal que $x_j \in \{ 0,1\}$ para $1 \leq j \leq n$ é aperiódica se não existir divisor $0 < d < n$ tal que a sequência seja formada pela justaposição de $\frac{n}{d}$ cópias do bloco $(x_1 , ..., x_d)$. Calcule, em função de $n$, o número de sequências aperiódica como acima.

English: Let $n$ be a fixed natural number. We say that a sequence $(x_1,...,x_n)$ such that $x_j\in \{ 0,1 \}$ for $1\leq j\leq n$ is aperiodic if there is no divisor $0<d<n$ such that the sequence is formed by the juxtaposition of $\frac{n}{d}$ copies of the block $(x_1, ..., x_d) $. Calculate, as a function of $n$, the number of aperiodic sequences as above.

$\endgroup$
  • 2
    $\begingroup$ @Brian M. Scott Tank You for edited. $\endgroup$ – marcelolpjunior Nov 11 '13 at 17:07
  • $\begingroup$ You’re welcome; Google translate did a pretty good job this time, so I just fixed a couple of little things. $\endgroup$ – Brian M. Scott Nov 11 '13 at 17:10
  • $\begingroup$ @BrianM.Scott As for the question, can you help me? $\endgroup$ – marcelolpjunior Nov 11 '13 at 17:11
  • 2
    $\begingroup$ I may be able to, but I need to think about it a little more to be sure. $\endgroup$ – Brian M. Scott Nov 11 '13 at 17:13
  • $\begingroup$ @BrianM.Scott I need to understand how to do it, is for a challenge, I tried a bit of everything, but I know well these concepts of aperiodic sequences, among others. I would be eternally grateful if you can save me. $\endgroup$ – marcelolpjunior Nov 11 '13 at 17:15
14
+50
$\begingroup$

Let $a_n$ be the number of aperiodic sequences of length $n$. Note that $a_1=2$, since the sequences $0$ and $1$ are vacuously aperiodic.

Suppose that $\sigma$ is a periodic sequence of length $n$, of minimal period $d$. Let $\beta$ be the periodic block of length $d$; then $\beta$ is an aperiodic sequence of length $d$. Conversely, if $0<d<n$, and $d\mid n$, then for each aperiodic sequence $\beta$ of length $d$ the sequence

$$\underbrace{\beta\beta\ldots\beta}_{n/d\text{ times}}$$

is a periodic sequence of length $n$ and minimal period $d$. It follows that there are

$$\sum\{a_d:0<d<n\text{ and }d\mid n\}$$

periodic sequences of length $n$ and hence that

$$a_n=2^n-\sum\{a_d:0<d<n\text{ and }d\mid n\}\;.\tag{0}$$

Let $p$ be any prime. Then $$a_{p^n}=2^{p^n}-\sum_{k=0}^{n-1}a_{p^k}\;,\tag{1}$$

and calculating a few values is very instructive:

$$\begin{array}{cc} 0&1&2&3\\ 2&2^p-2&2^{p^2}-2^p&2^{p^3}-2^{p^2} \end{array}$$

This leads immediately to the conjecture that $$a_{p^n}=2^{p^n}-2^{p^{n-1}}$$ for $n>0$, and the conjecture is easily proved by induction using $(1)$.

More generally, suppose that $n=p_1^{r_1}\ldots p_m^{r_m}$, where $p_1,\ldots,p_m$ are distinct primes and $r_1,\ldots,r_m\ge 1$. Form the product

$$\prod_{k=1}^mp_k^{r_k-1}(p_k-1)=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\prod_{k=1}^m(p_k-1)=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\sum_{S\subseteq[m]}(-1)^{m-|S|}\prod_{k\in S}p_k\;.$$

For each $S\subseteq[m]$ let

$$\alpha_S=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\prod_{k\in S}p_k\;;$$

then

$$a_n=\sum_{S\subseteq[m]}(-1)^{m-|S|}2^{\alpha_S}\;.\tag{2}$$

For example, if $p$ and $q$ are distinct primes,

$$a_{p^2q^2}=2^{\alpha_{\{p,q\}}}-2^{\alpha_{\{p\}}}-2^{\alpha_{\{q\}}}+2^{\alpha_\varnothing}=2^{p^2q^2}-2^{p^2q}-2^{pq^2}+2^{pq}\;.$$

You can probably prove this by induction using $(0)$, but it’s easier to see it as the result of an inclusion-exclusion argument. Rather than formalize this, I’ll illustrate it with an example and leave the formalization to you. Note that $(0)$ implies that $$\sum_{d\mid n}a_d=2^n\;,$$ where as usual the sum is taken over positive divisors. Consider $n=60=2^2\cdot3\cdot5$:

$$a_{60}=2^{60}-(a_1+a_2+a_3+a_4+a_5+a_6+a_{10}+a_{12}+a_{15}+a_{20}+a_{30})\;.$$

The maximal proper divisors of $60$ are $30,20$, and $12$, so every divisor of $60$ is a divisor of one of these three numbers, and to a first approximation $a_{60}$ is $2^{60}-2^{30}-2^{20}-2^{12}$. However, if $d$ is a common divisor of $30$ and $20$, say, then $a_d$ has been subtracted twice from $2^{60}$, once in $2^{30}$ and once in $2^{20}$, so it must be added back in. In particular, that’s true for every divisor of $\gcd(30,20)=10$, so we must add back in $\sum_{d\mid 10}a_d=2^{10}$. The same goes for divisors of $\gcd(30,12)=6$ and of $\gcd(20,12)=4$, so a better approximation to $a_{60}$ is $$2^{60}-2^{30}-2^{20}-2^{12}+2^{10}+2^6+2^4\;.$$ However, if $d\mid\gcd(30,20,12)=2$, then $a_d$ has now been subtracted three times and added back in $3$ times, so we must subtract $2^2$ for the correct result:

$$a_{60}=2^{60}-2^{30}-2^{20}-2^{12}+2^{10}+2^6+2^4-2^2\;.$$

A little thought shows that $(2)$ always yields the same result as the inclusion-exclusion argument.

Someone has kindly sent me a translation to Portuguese:

Seja $a_n$ o número de sequências aperiódicas de comprimento $n$. Repare que $a_1=2$, pois as sequências $0$ e $1$ são trivialmente aperiódicas. Suponha que $\sigma$ é uma sequência periódica de comprimento $n$, de período mínimo $d$. Seja $\beta$ o bloco periódico de comprimento $d$; então $\beta$ é uma sequência aperiódica de comprimento $d$. Reciprocamente, se $0<d<n$ e $d\mid n$, então para cada sequência aperiódica de comprimento $d$ a sequência $$\underbrace{\beta\beta\ldots\beta}_{n/d\text{ vezes}}$$ é uma sequência periódica de comprimento $n$ e período mínimo $d$. Segue-se que há$$\sum\{a_d:0<d<n\text{ e }d\mid n\}$$ sequências periódicas de comprimento $n$ e portanto que

$$a_n=2^n-\sum\{a_d:0<d<n\text{ e }d\mid n\}\;.\tag{0}$$ Seja $p$ um primo. Então $$a_{p^n}=2^{p^n}-\sum_{k=0}^{n-1}a_{p^k}\;,\tag{1}$$ e calcular alguns valores é muito instrutivo: $$\begin{array}{cc}0&1&2&3\\2&2^p-2&2^{p^2}-2^p&2^{p^3}-2^{p^2}\end{array}$$ Isto leva a conjeturar que $$a_{p^n}=2^{p^n}-2^{p^{n-1}}$$ para $n>0$, e a conjetura é facilmente demonstrável por indução usando $(1)$. Mais geralmente, suponha que $n=p_1^{r_1}\ldots p_m^{r_m}$, onde $p_1,\ldots,p_m$ são primos distintos e $r_1,\ldots,r_m\ge 1$. Construa o produto $$\prod_{k=1}^mp_k^{r_k-1}(p_k-1)=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\prod_{k=1}^m(p_k-1)=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\sum_{S\subseteq[m]}(-1)^{m-|S|}\prod_{k\in S}p_k\;.$$ Para cada $S\subseteq[m]$ seja $$\alpha_S=\left(\prod_{k=1}^mp_k^{r_k-1}\right)\prod_{k\in S}p_k\;;$$ então $$a_n=\sum_{S\subseteq[m]}(-1)^{m-|S|}2^{\alpha_S}\;.\tag{2}$$ Por exemplo, se $p$ e $q$ são primos distintos, $$a_{p^2q^2}=2^{\alpha_{\{p,q\}}}-2^{\alpha_{\{p\}}}-2^{\alpha_{\{q\}}}+2^{\alpha_\varnothing}=2^{p^2q^2}-2^{p^2q}-2^{pq^2}+2^{pq}\;.$$ Você provavelmente consegue provar isto por indução usando $(0)$, mas é mais fácil ver que é verdade por um raciocínio de inclusão-exclusão. Em vez de formalizar isto, irei ilustrar com um exemplo e deixar a formalização para você. Repare que $(0)$ implica que $$\sum_{d\mid n}a_d=2^n\;,$$ onde, como habitual, a soma é tomada sobre os divisores positivos. Considere $n=60=2^2\cdot3\cdot5$: $$a_{60}=2^{60}-(a_1+a_2+a_3+a_4+a_5+a_6+a_{10}+a_{12}+a_{15}+a_{20}+a_{30})\;.$$ Os divisores próprios maximais de $60$ são $30,20$ e $12$, portanto qualquer divisor de $60$ é um divisor de um destes três números e, como primeira aproximação $a_{60}$ é $2^{60}-2^{30}-2^{20}-2^{12}$. Contudo, se $d$ é um divisor comum a $30$ e $20$, por exemplo, então $a_d$ foi subtraída duas vezes de $2^{60}$, uma em $2^{30}$ e outra em $2^{20}$, por isso tem que se adicionar de volta. Em particular, isso é verdade para qualquer divisor de $\gcd(30,20)=10$, por isso devemos somar de volta $\sum_{d\mid 10}a_d=2^{10}$. O mesmo vale para os divisores de $\gcd(30,12)=6$ e de $\gcd(20,12)=4$, por isso uma melhor aproximação a $a_{60}$ é $$2^{60}-2^{30}-2^{20}-2^{12}+2^{10}+2^6+2^4\;.$$ No entanto, se $d\mid\gcd(30,20,12)=2$, então $a_d$ foi subtraída três vezes e adicionada de volta três vezes, por isso temos que subtrair $2^2$ para obter o resultado correcto: $$a_{60}=2^{60}-2^{30}-2^{20}-2^{12}+2^{10}+2^6+2^4-2^2\;.$$ Uma ligeira reflexão permite concluir que $(2)$ fornece sempre o mesmo resultado que o argumento de inclusão-exclusão.

$\endgroup$
  • $\begingroup$ Would you ask someone to translate to Portuguese? Using the google translator I still can not make a good read. Please. $\endgroup$ – marcelolpjunior Nov 20 '13 at 11:15
6
$\begingroup$

Maybe we can recapitulate the above in more compact form. Let $a_n$ be the number of aperiodic sequences. By definition we have that $$\sum_{d|n} a_d = 2^n.$$ By the Möbius Inversion Formula we thus have $$a_n = \sum_{d|n} 2^d \mu(n/d).$$ This gives for $n = p^k$ a power of a prime the result $$a_n = 2^{p^k}\mu(1) + 2^{p^{k-1}}\mu(p) = 2^{p^k}-2^{p^{k-1}}.$$ Here the MIF encapsulates inclusion-exclusion.

The sequence of the $a_n$ starts like this: $$2, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730,\ldots$$ which points us to OEIS A027375.


Portuguese version

Talvez seja possível recapitular a resposta acima de forma mais compacta. Seja $a_n$ o número de sequências aperiódicas. Por definição, $$\sum_{d|n} a_d = 2^n.$$ Pela fórmula de inversão de Möbius, então, $$a_n = \sum_{d|n} 2^d \mu(n/d).$$

Para $n=p^k$ uma potência de um primo, temos $$a_n = 2^{p^k}\mu(1) + 2^{p^{k-1}}\mu(p) = 2^{p^k}-2^{p^{k-1}}.$$

A inversão de Möbius, neste caso, expressa o princípio da inclusão-exclusão.

A sequência $(a_n)_n$ tem valores $$2, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730,\ldots$$ que apontam para a sequência OEIS A027375.

$\endgroup$
  • $\begingroup$ I'm having trouble understanding what is this "argument of inclusion-exclusion" $\endgroup$ – marcelolpjunior Nov 20 '13 at 10:02
  • 1
    $\begingroup$ Note that "above" and "below" varies here! If someone orders answers differently (like me), your question is actually the first to be read, so it is better just to give a concrete reference of what "above" is! =) $\endgroup$ – Pedro Tamaroff Nov 20 '13 at 15:19
  • $\begingroup$ Marko, I edited your answer so I could add a Portuguese version, I hope you don't mind. $\endgroup$ – Ian Mateus Nov 22 '13 at 15:21
  • $\begingroup$ @marcelolpjunior inclusion-exclusion principle is what you probably know as princípio da inclusão-exclusão. $\endgroup$ – Ian Mateus Nov 22 '13 at 15:23
  • $\begingroup$ Nice: the MIF does make it very easy. $\endgroup$ – Brian M. Scott Nov 30 '13 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.