2014 dxdy logo

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

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




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


22/11/13
508
Пусть $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 сообщение ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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