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

Сопряжённое разбиение: меняем число частей и наибольшую часть

Строим столбцы диаграммы по длинам строк, доказываем обратимость сопряжения и переносим ограничения на число и размер частей, не смешивая их с условием различных слагаемых.

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

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

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

Если длины строк диаграммы разбиения равны λ₁≥λ₂≥…>0, длина j-го столбца равна числу строк длины хотя бы j. Эти столбцы образуют сопряжённое разбиение той же суммы. Повторное сопряжение возвращает исходное; число строк меняется местами с длиной самой длинной строки.

Считаем клетки в столбцах, а не переставляем слагаемые

Запишем разбиение как невозрастающий список положительных чисел. Для каждого числа нарисуем слева направо соответствующий ряд клеток, выравнивая все ряды по левому краю. Ряды не должны быть случайно сдвинуты: иначе высоты столбцов перестанут кодировать то же разбиение. Количество клеток равно сумме частей n.

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

Формула высот доказывает обратимость без картинки

Обозначим высоту столбца j через λ′ⱼ=#{i:λᵢ≥j}. При повторном преобразовании i-я часть равна числу j, для которых λ′ⱼ≥i. Так как исходные строки упорядочены, не менее i строк достигают столбца j ровно тогда, когда сама i-я строка достигает j. Число таких столбцов равно λᵢ. Поэтому (λ′)′=λ.

Ни площадь диаграммы, ни сумма частей не меняется: каждая клетка просто учитывается сначала по строке, потом по столбцу. Обратимость даёт биекцию, а не только совпадение нескольких примеров. Все разбиения n ровно на k частей переходят в разбиения n с наибольшей частью k, и каждое разбиение второго семейства имеет единственного предшественника. Эти семейства могут пересекаться; их непересечение для биекции не требуется.

Пример

Найдите сопряжённое к 5+3+3+1 и проверьте сумму, число частей и максимум.

Столбцы имеют высоты 4, затем 3, затем 3, затем 1 и 1: λ′=4+3+3+1+1. Сумма обеих записей равна 12. Исходные четыре части дали максимум 4, исходный максимум 5 дал пять частей. Повторный подсчёт столбцов для 4+3+3+1+1 возвращает 5+3+3+1; это проверяет весь объект, а не только две крайние характеристики.

Прямоугольные рамки переходят друг в друга

Если частей не больше r и каждая не больше s, диаграмма помещается в прямоугольник высоты r и ширины s. После сопряжения получим не больше s частей, каждая не больше r. Нули дописывать в само разбиение не нужно: рамка ограничивает возможные ряды, а список содержит только непустые. Такое соответствие переносит сразу два ограничения.

Сопряжение не сохраняет произвольные свойства слагаемых. Например, разные части 4+2 превращаются в 2+2+1+1, где повторы есть. Нечётность всех частей также не сохраняется автоматически. Равенство численностей семейств с нечётными частями и с различными частями требует другого преобразования. Разбиение может совпасть со своим сопряжённым, но равенство числа частей наибольшей части ещё не гарантирует этого: нужно совпадение всего списка высот со списком длин.

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

А теперь — вы

Разбиение имеет не больше трёх частей, каждая не превосходит семи. Какие ограничения обязательно имеет сопряжённое разбиение?

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

Обязательно ли сопряжённое разбиение отличается?

Нет. Некоторые диаграммы симметричны относительно главной диагонали и возвращают тот же список. Такие неподвижные объекты не мешают биекции.

Что случится с ограничением ровно k частей?

Оно станет условием наибольшая часть ровно k. Для ограничения не больше k получается максимум не больше k.

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

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

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