2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 К чему приведет удаление единицы?
Сообщение09.11.2022, 10:20 
Аватара пользователя


22/11/13
02/04/25
549
Пусть $q(n)$ - это A007814, число конечных нулей в двоичной записи $n$. Здесь
$$q(2n+1)=0, q(2n)=q(n)+1$$
Пусть также $a(n)$ - это A329369. Здесь
$$a(2n+1)=a(n), a(2n)=a(n)+a(n-2^{q(n)})+a(2n-2^{q(n)}), a(0)=1$$
Другие формулы можно брать на страничке A329369 и еще одна лежит вот тут.

Теперь возьмем какое-нибудь красивое и одновременно простенькое число в двоичной, например вот такое:
$$\underbrace{1\cdots1}_{n}\underbrace{0\cdots0}_{m}$$
Записать его мы можем через $2^{m}(2^n-1)$. Тогда имеет место равенство
$$a(2^{m}(2^n-1))=\sum\limits_{i=1}^{n+1} i!i^m S(n+1,i)(-1)^{n-i+1}$$
Здесь $S(n,k)$ это числа Стирлинга второго рода, с дополнительным условием: если $k<0$, то $S(n,k)=0$. Здесь мы с этим пока не сталкиваемся, но в дальнейшем это нам пригодится.

Теперь предположим, что некий коварный хитрец (или упрямый глупец) вопрошает: что будет, если из двоичной записи $2^{m}(2^n-1)$ убрать $p$-тую справа единицу ($1<p<n$)? Т.е. какое значение мы получим, подставив получившееся число в $a(n)$?

Удивительно, но аналогичный ответ существует:
$$a(2^{m}(2^n-2^{p-1}-1))=A-B+C$$
Здесь
$$A=\sum\limits_{i=1}^{n} i!i^m (i-p+2)S(n,i) (-1)^{n-i}$$$$B=\sum\limits_{i=1}^{n} i!i^m S(n-p+1,i-p+1) (-1)^{n-i}$$$$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$$
Я разбил все выражение на части, поскольку формула полностью не отображалась. Здесь также необходимо условиться, что при $p=2$ будем иметь $C=0$.

Докажите равенство для $a(2^{m}(2^n-2^{p-1}-1))$. По возможности желательно что-нибудь упростить.

Открытый вопрос номер один: что если мы удаляем не одну единицу, а несколько единиц подряд, так, что справа остается $p-1$ единиц? Вопрос легко разрешим для $p=2$ и $p=3$, а дальше начинаются некрасивые загогулины.

Открытый вопрос номер два: что если мы удаляем любое количество единиц в любых местах (кроме крайних)?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group