Объяснить мотивацию бином. трансформации по модулю 2

[kthxbye]

Если будет получен ответ на этот вопрос, то можно будет легко осуществить переход от результатов полученных здесь до результатов полученных вот тут.

Отвлечемся от определения с ладьей, которое, вероятно, вводит многих в заблуждение. Имеем набор элементов $\left\lbrace>, <, \triangle\right\rbrace$: стрелка направо, стрелка налево и треугольник. Стоя на стрелке направо мы можем двигаться исключительно вправо. Аналогично для стрелки налево. С треугольника же можно двигаться в обоих направлениях. Движение мы осуществляем в строке заполненной элементами из набора.

Выделим два типа строк:

• строки с элементами $\left\lbrace>, <\right\rbrace$
• строки с элементами $\left\lbrace\triangle, <\right\rbrace$

Сопоставим первому элементу в каждом из случаев $1$, а второму - $0$. Тогда если строка закодирована двоичным разложением $2n$ она имеет $a(n)$ решений в первом случае и $b(n)$ решений во втором.

Решением называется такая перестановка, которая описывает путь перемещения по стрелкам, при котором каждая посещается ровно один раз по правилам описанным выше:

Цитата:

Стоя на стрелке направо мы можем двигаться исключительно вправо. Аналогично для стрелки налево. С треугольника же можно двигаться в обоих направлениях.

Для строк из элементов $\left\lbrace>, <\right\rbrace$ мы считаем решения, оканчивающиеся на элементе $<$, а для строк из элементов $\left\lbrace\triangle, <\right\rbrace$ - на любом элементе. Тогда $a(n)$ это A329369 и $b(n)$ это A284005.

Что примечательно,

$$b(n)=\sum\limits_{j=0}^{n}a(j)\left(\binom{n}{j}\bmod2\right)$$

$$a(n)=\sum\limits_{j=0}^{n}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}b(j)\left(\binom{n}{j}\bmod2\right)$$

Цитата:

Пусть $\operatorname{wt}(n)$ это A000120, число единиц в двоичном разложении $n$ (или просто бинарный вес $n$). Здесь

$$\operatorname{wt}(n)=\operatorname{wt}\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n\bmod2, \operatorname{wt}(0)=0$$

По сюжету мы легко выводим рекуррентную формулу для $b(n)$ и если мы объясним мотивацию любой из приведенных выше биномиальных трансформаций по модулю $2$ (прямую либо обратную), то можно будет без труда вывести рекуррентную формулу для $a(n)$.

Кроме того, приведенные выше тождества можно заменить на

$$b(n)=\sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}a(T(n,j))$$

$$a(n)=\sum\limits_{j=0}^{2^{\operatorname{wt}(n)}-1}(-1)^{\operatorname{wt}(n)-\operatorname{wt}(j)}b(T(n,j))$$

Цитата:

Пусть $T(n,k)$ это A295989, $(k+1)$-ое неотрицательное число $m$, такое, что $n\operatorname{AND}m=m$. Другое определение - числа в порядке возрастания, получаемые в результате замены (всеми возможными способами) единиц на нули в двоичном разложении $n$. Еще одно определение - числа $m$, такие, что $\binom{n}{m}\bmod2=1$. Здесь

$$T(2n,k)=2T(n,k), T(2n+1,k)=2T\left(n,\left\lfloor\frac{k}{2}\right\rfloor\right)+k\bmod2, T(n,0)=0$$

Если мы выпишем решения, для, например, $>><<$, а также $<<<<$, $<><<$ и $><<<$ (замена всеми возможными способами единиц на нули), то получим все решения для $\triangle\triangle<<$.

Аналогично если мы выпишем решения для, например, $\triangle\triangle<<$ а также $<<<<$, $<\triangle<<$ и $\triangle<<<$ (замена всеми возможными способами единиц на нули) и удалим дубликаты, то мы получим все решения для $>><<$.

Но чем объяснить мотивацию?