Математика · объяснение и практика

Нечётные и различные части: биекция через двоичные кратности

Строим взаимно обратимые преобразования разбиений с нечётными частями и с различными частями, доказываем отсутствие повторов через нечётное ядро и объясняем роль двоичной записи.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Число разбиений n на нечётные части равно числу разбиений n на различные части. Для каждой нечётной части q запишем её кратность в двоичной системе и заменим группы из 2ʲ одинаковых q одной частью 2ʲq. Обратно каждую часть разделим на её максимальную степень двойки и восстановим соответствующее число нечётных слагаемых.

Одинаковое количество объектов не означает одинаковые ограничения

В первом семействе все части нечётны, но повторения разрешены. Во втором повторения запрещены, зато чётные части допускаются. Например, 3+3+1 не принадлежит второму семейству, а 6+1 не принадлежит первому. Теорема сравнивает количества разбиений одного n, а не утверждает, что сами семейства совпадают.

Соберём равные нечётные части q и обозначим число их повторений через m. У m есть единственная двоичная запись как суммы различных степеней двойки. Если m=13, это 8+4+1. Вместо тринадцати копий q запишем три части 8q, 4q и q. Сумма не изменилась. Нулевой двоичный разряд не порождает части: список содержит только действительно выбранные степени.

Разные нечётные ядра не могут столкнуться

Внутри одной группы q выбранные степени двойки различны, поэтому полученные части различны. Для двух разных нечётных q столкновение тоже невозможно: равенство 2ʲq=2ᵏr сначала заставило бы совпасть j и k по наибольшей степени двойки, делящей число, а затем q=r. Таким образом, после обработки всех групп получается разбиение на различные части.

Обратно возьмём любое разбиение на различные части. Каждую положительную часть единственным образом запишем 2ʲq с нечётным q и заменим её 2ʲ копиями q. Получатся только нечётные части, их сумма сохранится. Если несколько исходных частей имели одно нечётное ядро, число их копий складывается. Различность исходных частей означает различность двоичных степеней внутри этого ядра, поэтому двоичная запись восстановит ровно прежние части.

Пример

Преобразуйте нечётное разбиение из семи троек и пяти единиц в разбиение на различные части. Сумма равна 26.

Кратность семи троек имеет запись 7=4+2+1 и даёт части 12, 6, 3. Пять единиц имеют запись 5=4+1 и дают 4, 1. После упорядочения получаем 12+6+4+3+1=26, все части различны. Обратно 12 возвращает четыре тройки, 6 две тройки, 3 одну тройку, 4 четыре единицы и 1 одну единицу: обе кратности восстановлены.

Проверяем оба возвращения, а не только сохранение суммы

При движении от нечётного разбиения к различному и обратно каждая группа m копий q восстанавливается из двоичных разрядов m. В обратном направлении разложение каждой различной части на степень двойки и нечётное ядро также единственно. Значит, ни два разбиения не склеиваются и ни одно целевое не пропущено. Это и доказывает равенство количеств для каждого n, включая пустое разбиение нуля.

Можно выполнять преобразование последовательно, сливая пары равных частей в их удвоение, пока повторы не исчезнут. Двоичные разряды объясняют, почему конечный результат однозначен. Но произвольное объединение любых двух слагаемых этим правилом не является: необходимо равенство сливаемых частей. Отражение диаграммы разбиения тоже не заменяет текущую биекцию, поскольку оно меняет строки и столбцы, а не кодирует кратности нечётных частей.

От чтения к действию

А теперь — вы

Различное разбиение содержит части 24, 12 и 3. Какую группу нечётных частей они дадут при обратном преобразовании?

Частые вопросы

Почему используется именно двоичная запись?

Она имеет цифры ноль или один, поэтому каждая часть данного нечётного ядра появляется не более одного раза. Это соответствует запрету повторов в целевом семействе.

Биекция сохраняет число частей?

Нет. Несколько одинаковых частей могут сливаться в одну большую. Сохраняется их общая сумма, а число частей обычно меняется.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться