WikiSort.ru - Не сортированное

Симметрии

Как и любой фрактал, последовательность Морса — Туэ обладает рядом симметрий. Так, последовательность остаётся сама собой:

• При удалении всех элементов на чётных местах:

10 01  01 10  01 10  10 01  01 10  10 01  10 01  01 10...

1  0   0  1   0  1   1  0   0  1   1  0   1  0   0  1...

• При замене двух частей, из которых можно составить целое, другими двумя символами. Это означает, что последовательность нельзя заархивировать по алгоритму Хаффмана, так как последовательность, являющаяся «архивом» будет совпадать с самой последовательностью Морса — Туэ:

1001 0110 0110 1001  0110 1001  1001 0110...
1    0    0    1     0    1     1    0...

Другие свойства

• В последовательности никогда не встречаются три одинаковых подряд идущих части (невозможно встретить «A-A-A», где «A» — последовательностей нулей и единиц);
• Дискретное преобразование Фурье последовательности имеет одинаковые максимумы на частотах ⅓ и ⅔;
• Число, двоичной записью которого является последовательность Морса — Туэ, называется числом Пруэ-Туэ-Морса:

${\displaystyle \tau =\sum _{i=0}^{\infty }{\frac {t_{i}}{2^{i+1}}}=0.412454033640\ldots }$ (последовательность A014571 в OEIS),

где ${\displaystyle t_{i}}$ — элементы последовательности Морса-Туэ. Это число трансцендентно (доказано K. Mahler в 1929 году).

Обобщение на произвольный алфавит

Имея произвольный алфавит из n символов, можно составить ровно n разных циклических перестановок этого алфавита. Затем, заменяя каждую «букву» алфавита на соответствующую перестановку, можно получить последовательность Морса — Туэ. Так например из трёх символов «1», «2», «3» можно составить три циклических перестановки: «123», «231», «312»:

${\displaystyle 1\rightarrow 123}$

${\displaystyle 2\rightarrow 231}$

${\displaystyle 3\rightarrow 312}$

                              1
         1                    2                    3
  1      2      3      2      3      1      3      1      2
1 2 3  2 3 1  3 1 2  2 3 1  3 1 2  1 2 3  3 1 2  1 2 3  2 3 1...

Многомерное обобщение

Многомерная последовательность Морса — Туэ определяется подобным образом. Так например двумерная последовательность (матрица) является пределом последовательности, каждый следующий член которой получается из предыдущего при помощи преобразования

${\displaystyle 1\rightarrow {\begin{matrix}1&0\\0&1\end{matrix}}}$ ; ${\displaystyle 0\rightarrow {\begin{matrix}0&1\\1&0\end{matrix}}}$

${\displaystyle 10010110\cdots }$

${\displaystyle 01101001\cdots }$

${\displaystyle 01101001\cdots }$

${\displaystyle 10010110\cdots }$

${\displaystyle \vdots \quad \vdots \quad \vdots \quad \ddots }$

Также двумерную последовательность Морса-Туэ можно представить как совокупность одномерных.