2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Бесконечное семейство перестановок натуральных чисел
Сообщение20.06.2022, 15:08 
Аватара пользователя


22/11/13
496
Для начала нам нужны несколько бинарных функций.

Пусть
$$\ell(n)=\left\lfloor\log_{2}(n)\right\rfloor$$

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

Кроме того, $\operatorname{val}(n)$ - это A007814, максимальная степень двойки на которую делится $n$.

А теперь пусть $\left\lbrace a(n,m)\right\rbrace$ это последовательность чисел $k$, таких, что

$$\ell(k)-\operatorname{wt}(k)=\ell(\frac{k}{2^{\operatorname{val}(k)}}+2m)$$.

Пусть также $$b(n,m)=\left\lfloor\frac{a(n,m)}{2^{\operatorname{val}(a(n,m))+1}}\right\rfloor+1$$

Докажите, что для любого $m\geqslant0$ (имеется ввиду что $m$ - это некоторое целое неотрицательное число) последовательность $\left\lbrace b(n,m)\right\rbrace$ является перестановкой натуральных чисел.

 Профиль  
                  
 
 Re: Бесконечное семейство перестановок натуральных чисел
Сообщение21.06.2022, 14:07 


02/04/18
240
Немного сумбурно, потому что решал буквально в окне ответа темы, но вроде бы так...

Очевидно, что любое натуральное число можно записать в виде $k=(2p+1)2^r$, где $p, r$ - целые неотрицательные числа. Сразу можно записать $val(k)=r$.
Заметим, что логарифм округляется вниз, поэтому из нечетного аргумента можно свободно вычесть единицу и далее получить:
$\left\lfloor\log_2{(2p+1)}\right\rfloor=\left\lfloor\log_2{2p}\right\rfloor=\left\lfloor1+\log_2{p}\right\rfloor=\left\lfloor\log_2{p}\right\rfloor+1$
А тогда:
$\l(k)=\left\lfloor\log_2{(2p+1)}\right\rfloor+r=\left\lfloor\log_2{p}\right\rfloor+r+1$
В правой же части вычисляется величина $\l(2p+1+2m)=\left\lfloor\log_2{(p+m)}\right\rfloor+1$.

Наконец, $wt(a)=wt(2p+1)=wt(p)+1$: нули в конце двоичной записи можем просто отбросить, после чего выделить особо единицу в первом разряде.

Тогда равенство, определяющее подходящие $k$, выглядит следующим образом:
$$\left\lfloor\log_2{p}\right\rfloor+r - wt(p) = \left\lfloor\log_2{(p+m)}\right\rfloor+1$$

Задавшись каким-то значением $m$, мы получаем функцию
$$r(p)=\left\lfloor\log_2{(p+m)}\right\rfloor-\left\lfloor\log_2{p}\right\rfloor+wt(p)+1$$
Разность логарифмов, конечно, неотрицательна, как и $wt(p)$ - поэтому правая часть строго положительна, причем определена для любого $p\ge0$. Значение этой функции определяет количество двоичных нулей, которое надо приписать к $2p+1$, чтобы получить какое-то значение элемента последовательности $a$.

Поскольку любое натуральное число $n$ можно определить через уникальную пару $(p,r)$ и наоборот, каждой паре неотрицательных чисел соответствует какое-то натуральное число, а для любого $p$ мы можем единственным образом определить $r_p=r(p)$, то, как мы видим, можно определить все элементы последовательности $a(n,m)$. Тогда $val(n,m)=r_p+1$, и формула
$$\left\lfloor\frac{2p+1}{2}\right\rfloor+1=p+1$$
определяет элементы последовательности $b(n,m)$ в некотором порядке. Благодаря тому, что добавлена единица, $p+1$ - натуральные числа и встречаются ровно по разу. Но это и есть определение перестановки натурального ряда.
ЧТД.

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

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



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

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


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

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