Правило симметричных потоков Н.А. Тенетко

Правило симметричных потоков Н.А. Тенетко

исправлено и дополнено LaTEX

Н.А. Тенетко

Правило

Для бинарной последовательности (X) длины (n\ge1) партнёр (P(X)) определяется как:

[ P(X)= \begin{cases} R(X), & X\neq R(X),\[4pt] I(X), & X=R(X), \end{cases} ]

где:

1. (R(X)) — зеркальное отражение (reverse),
2. (I(X)) — побитовая инверсия (invert).

Свойства

1. Инволютивность:

[ P(P(X))=X. ]

1. Отсутствие неподвижных точек:

[ P(X)\neq X. ]

1. Полное разбиение: множество

[ {0,1}^n ]

разбивается на

[ 2^{n-1} ]

непересекающихся пар.

Примеры

(n=3) (4 пары):

[ 000\leftrightarrow111, \qquad 001\leftrightarrow100, \qquad 010\leftrightarrow101, \qquad 110\leftrightarrow011. ]

(n=4) (8 пар):

[ 0000\leftrightarrow1111, \qquad 0001\leftrightarrow1000, \qquad 0010\leftrightarrow0100, \qquad 0011\leftrightarrow1100, ]

[ 0101\leftrightarrow1010, \qquad 1001\leftrightarrow0110, \qquad 1011\leftrightarrow1101, \qquad 0111\leftrightarrow1110. ]

Комбинаторная структура

1. Общее число пар:

[ 2^{n-1}. ]

1. Число статичных пар (неподвижных относительно инверсии на уровне пары):

[ S(n)=2^{\lfloor n/2\rfloor}. ]

1. Число переходящих R-пар (при инверсии переходят в другую R-пару):

[ 2^{n-1}-2^{\lfloor n/2\rfloor}. ]

1. Число мета-пар (пар из двух переходящих R-пар):

[ \frac{2^{n-1}-2^{\lfloor n/2\rfloor}}{2}. ]

1. Для соседних длин:

[ S(2k)=S(2k+1)=2^k. ]

Второй уровень

Для первичной пары

[ \pi={X,P(X)} ]

операция инверсии определяется как:

[ I(\pi)={I(X),I(P(X))}. ]

1. I-static (палиндромы, соединённые инверсией) и R-static (непалиндромы, соединённые отражением, но неподвижные при инверсии пары) не образуют мета-пар и остаются на месте.
2. Переходящие R-пары при инверсии переходят в другую R-пару, образуя мета-пару.

Граница операции:

[ I\bigl({\pi,I(\pi)}\bigr) = {\pi,I(\pi)}. ]

Повторное применение инверсии на этом уровне не создаёт нового объекта.