Пусть
![$q(n)$ $q(n)$](https://dxdy-04.korotkov.co.uk/f/f/f/d/ffd8ab005bdc917a8052c2b77cf46cfa82.png)
- это
A007814, число конечных нулей в двоичной записи
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
. Здесь
![$$q(2n+1)=0, q(2n)=q(n)+1$$ $$q(2n+1)=0, q(2n)=q(n)+1$$](https://dxdy-01.korotkov.co.uk/f/8/8/5/885393801bc820601d3337a412e8451a82.png)
Пусть также
![$a(n)$ $a(n)$](https://dxdy-03.korotkov.co.uk/f/e/b/1/eb1e4d26da404d5c7d56055c19d365a082.png)
- это
A329369. Здесь
![$$a(2n+1)=a(n), a(2n)=a(n)+a(n-2^{q(n)})+a(2n-2^{q(n)}), a(0)=1$$ $$a(2n+1)=a(n), a(2n)=a(n)+a(n-2^{q(n)})+a(2n-2^{q(n)}), a(0)=1$$](https://dxdy-04.korotkov.co.uk/f/b/6/a/b6a2f14d0660eec785a06dc529cf6cf882.png)
Другие формулы можно брать на страничке
A329369 и еще одна лежит
вот тут.
Теперь возьмем какое-нибудь красивое и одновременно простенькое число в двоичной, например вот такое:
![$$\underbrace{1\cdots1}_{n}\underbrace{0\cdots0}_{m}$$ $$\underbrace{1\cdots1}_{n}\underbrace{0\cdots0}_{m}$$](https://dxdy-03.korotkov.co.uk/f/e/2/9/e296dc2a327ce1adfc5755e2fd3fe9e682.png)
Записать его мы можем через
![$2^{m}(2^n-1)$ $2^{m}(2^n-1)$](https://dxdy-04.korotkov.co.uk/f/3/3/8/3382a982dd3a942ee7441ecf8a3ae1f582.png)
. Тогда имеет место равенство
![$$a(2^{m}(2^n-1))=\sum\limits_{i=1}^{n+1} i!i^m S(n+1,i)(-1)^{n-i+1}$$ $$a(2^{m}(2^n-1))=\sum\limits_{i=1}^{n+1} i!i^m S(n+1,i)(-1)^{n-i+1}$$](https://dxdy-03.korotkov.co.uk/f/e/6/b/e6b98094bd933725cb64b5531b50b08282.png)
Здесь
![$S(n,k)$ $S(n,k)$](https://dxdy-03.korotkov.co.uk/f/e/8/4/e8407d4326d9773f34393b4a73730fe182.png)
это числа Стирлинга второго рода, с дополнительным условием: если
![$k<0$ $k<0$](https://dxdy-01.korotkov.co.uk/f/c/c/9/cc9701213d4f87a319965a4a1e281a4482.png)
, то
![$S(n,k)=0$ $S(n,k)=0$](https://dxdy-02.korotkov.co.uk/f/9/4/b/94b8cb3e0b1d103de95908bdf922aed582.png)
. Здесь мы с этим пока не сталкиваемся, но в дальнейшем это нам пригодится.
Теперь предположим, что некий коварный хитрец (или упрямый глупец) вопрошает: что будет, если из двоичной записи
![$2^{m}(2^n-1)$ $2^{m}(2^n-1)$](https://dxdy-04.korotkov.co.uk/f/3/3/8/3382a982dd3a942ee7441ecf8a3ae1f582.png)
убрать
![$p$ $p$](https://dxdy-03.korotkov.co.uk/f/2/e/c/2ec6e630f199f589a2402fdf3e0289d582.png)
-тую справа единицу (
![$1<p<n$ $1<p<n$](https://dxdy-01.korotkov.co.uk/f/c/2/c/c2c17646c6532e3bdc5c13b0be94e1cb82.png)
)? Т.е. какое значение мы получим, подставив получившееся число в
![$a(n)$ $a(n)$](https://dxdy-03.korotkov.co.uk/f/e/b/1/eb1e4d26da404d5c7d56055c19d365a082.png)
?
Удивительно, но аналогичный ответ существует:
![$$a(2^{m}(2^n-2^{p-1}-1))=A-B+C$$ $$a(2^{m}(2^n-2^{p-1}-1))=A-B+C$$](https://dxdy-04.korotkov.co.uk/f/f/2/f/f2f57e9805adc545f33169fb6760582282.png)
Здесь
![$$A=\sum\limits_{i=1}^{n} i!i^m (i-p+2)S(n,i) (-1)^{n-i}$$ $$A=\sum\limits_{i=1}^{n} i!i^m (i-p+2)S(n,i) (-1)^{n-i}$$](https://dxdy-01.korotkov.co.uk/f/0/9/7/097d854c6b42416fc0484b0d36f3ae6882.png)
![$$B=\sum\limits_{i=1}^{n} i!i^m S(n-p+1,i-p+1) (-1)^{n-i}$$ $$B=\sum\limits_{i=1}^{n} i!i^m S(n-p+1,i-p+1) (-1)^{n-i}$$](https://dxdy-01.korotkov.co.uk/f/c/2/b/c2b2f2183ec91e52062c5d8dfb9d2ccd82.png)
![$$C=\sum\limits_{i=1}^{n} i!i^m (-1)^{n-i} \sum\limits_{j=0}^{p-3} \frac{p-j-2}{j!}S(n-p+1,i-j)\sum\limits_{k=0}^{j} (i-k)^{p-1}\binom{j}{k}(-1)^k$$ $$C=\sum\limits_{i=1}^{n} i!i^m (-1)^{n-i} \sum\limits_{j=0}^{p-3} \frac{p-j-2}{j!}S(n-p+1,i-j)\sum\limits_{k=0}^{j} (i-k)^{p-1}\binom{j}{k}(-1)^k$$](https://dxdy-03.korotkov.co.uk/f/6/6/7/667235de2469ab0dc9488713ae6e90cf82.png)
Я разбил все выражение на части, поскольку формула полностью не отображалась. Здесь также необходимо условиться, что при
![$p=2$ $p=2$](https://dxdy-02.korotkov.co.uk/f/9/0/2/90264925fb137831c8f410cd14c75cff82.png)
будем иметь
![$C=0$ $C=0$](https://dxdy-04.korotkov.co.uk/f/b/1/6/b16f5cc5be180c41902395e595876db282.png)
.
Докажите равенство для
![$a(2^{m}(2^n-2^{p-1}-1))$ $a(2^{m}(2^n-2^{p-1}-1))$](https://dxdy-01.korotkov.co.uk/f/0/a/b/0abf57bfb293b22775e5d85713d0197982.png)
. По возможности желательно что-нибудь упростить.
Открытый вопрос номер один: что если мы удаляем не одну единицу, а несколько единиц подряд, так, что справа остается
![$p-1$ $p-1$](https://dxdy-02.korotkov.co.uk/f/5/8/5/585cf0d6605a58bb5df9e272ae37244a82.png)
единиц? Вопрос легко разрешим для
![$p=2$ $p=2$](https://dxdy-02.korotkov.co.uk/f/9/0/2/90264925fb137831c8f410cd14c75cff82.png)
и
![$p=3$ $p=3$](https://dxdy-04.korotkov.co.uk/f/3/9/c/39cd1e5f222b0b87f4a26f8b97296bd282.png)
, а дальше начинаются некрасивые загогулины.
Открытый вопрос номер два: что если мы удаляем любое количество единиц в любых местах (кроме крайних)?