из N единиц является одним из совершенных разбиений для каждого натурального N. Для 
разбиения 
, 
и 
и только они являются совершенными.
Если все части разбиения рассматривать как разновесы для весов, то совершенные разбиения оказываются решениями проблемы определения такого набора гирь, с помощью которого (при условии размещения гирь на одной чаше весов) можно взвесить единственным способом любой предмет, вес которого выражается целым числом. Именно в такой формулировке на одной из математических олимпиад школьников встретилась задача (11-й Турнир Городов, 1990, автор - Д. Фомин).
Рассматривается набор гирь, каждая из которых весит целое число граммов, а общий вес всех гирь равен 500 граммов. Такой набор называется правильным, если любой груз, у которого вес выражается целым числом граммов от 1 до 500, может быть уравновешен некоторым количеством гирь набора, и притом единственным образом. Груз кладется на одну чашку весов, гири - на другую. Два способа уравновешивания, отличающиеся лишь заменой некоторых гирь на другие того же веса, считаются одинаковыми. Сколько существует различных правильных наборов? (Два набора различны, если некоторая гиря участвует в этих наборах не одинаковое число раз).
Таким образом, в этой задаче требуется найти количество совершенных разбиений числа 
. В каждом совершенном разбиении, очевидно, должна содержаться по крайней мере одна часть, равная 1. Предположим, что в нём содержится 
частей, равных единице. Тогда все числа, меньшие , обладают только одним разбиением, и значит, число 
будет следующей частью совершенного разбиения. Пусть теперь в разбиении содержится 
частей, равных q1, тогда все числа от 1 до 
единственным способом выражаются с помощью 1 и q1. Продолжая рассуждения аналогичным образом, приходим к совершенному разбиению вида:
Сумма всех составных частей этого разбиения равна N, поэтому:
и значит, qi являются делителями числа N+1. Таким образом, упорядоченный набор чисел 
полностью определяет данное разбиение, при этом каждый сомножитель qi больше 1. Следовательно, справедлива следующая:
Теорема 1 [8, 2, 9]. Количество совершенных разбиений натурального числа N совпадает с количеством упорядоченных факторизаций числа N+1 без единичных множителей.
Различными разложениями на множители числа 10 служат 10, 
и 
. Они соответствуют указанным выше совершенным разбиениям 19, 241 и 145 числа N=9. В задаче Турнира Городов правильными наборами гирь будут 
, 
и 
, соответствующие упорядоченным факторизациям 
, 
и 
числа 
.
Пусть 
. Обозначим количество нетривиальных упорядоченных факторизаций числа 
через 
.
Теорема 2. Для функции справедлива рекуррентная формула:
|
|
(1) |
,
сумма берётся по всем наборам, в которых 
и 
, причем 
.
Доказательство. Пусть 
- произвольный делитель числа N, отличный от N, то есть 
и 
. Тогда всякая факторизация числа N, у которой первый множитель равен m, получается из соответствующей факторизации числа d, причём число последних, очевидно, равно 
. Отсюда следует равенство (1).
Добавив к обеим частям равенства (1) слагаемое , можно записать его в виде:
|
|
(2) |
В частности, если число N имеет лишь один простой множитель, то есть s=1 и 
, из (1) имеем:
Поскольку 
получаем 
Решение задачи для произвольного натурального s мы приведем в конце статьи, начнем же с простейшего случая, когда число N имеет два простых делителя.
Случай двух делителей. Воспользуемся равенством (1), определяющим функцию 
, для получения более простых рекуррентных соотношений. Во-первых, запишем его в виде:
Заменяя n1 на n1-1 и вычитая полученное равенство из предыдущего, получим:
|
|
(3) |
Формула (3) остаётся верной и при нулевых значениях параметров n1, n2 (кроме случая 
), при этом значения функции T с отрицательными аргументами нужно считать равными нулю, а 
.
Пример 1. Пусть . С помощью рекуррентной формулы (3) находим:
Поскольку 
, получаем 
. Другими словами, число 
, где 
- простые числа, имеет ровно три упорядоченные факторизации, а именно: N, 
и 
.
Пример 2. Пусть 
. Тогда:
Опираясь на равенство (3), несложно найти явный вид производящей функции для последовательности . Пусть 
- производящая функция для T, то есть:
Слагаемое 
в этом равенстве выделено особо для того, чтобы в основной сумме можно было использовать рекуррентное соотношение (3) для . Имеем:
Заменяя соответствующие индексы суммирования в каждой из трёх последних сумм, получим уравнение:
из которого находим:
|
|
(4) |
Теорема 3 [8, p. 860], [4]. Для количества упорядоченных факторизаций числа 
справедливы формулы:
|
|
(5) |
|
|
(6) |
где n =n1+n2.
Доказательство. Докажем первое из этих равенств. Для этого разложим функцию из равенства (4) в ряд Тейлора в окрестности точки (0,0):
Коэффициент при x2 n2 равен:
Раскладывая выражения 
и 
в степенные ряды, мы получим:
Коэффициент при 
в правой части находится из условия 
. Подставляя вместо l число 
и выделяя коэффициент при , получаем равенство:
(Для симметричности формулы в последней сумме верхняя граница n2 заменена на n=n1+n2. Конечно, равенство при этом не нарушается, поскольку биномиальные коэффициенты, у которых верхний индекс больше нижнего, равны нулю.) Равенство (5) доказано. Равенство (6) доказывается аналогично с той лишь разницей, что коэффициент при x2 n2 представляется в виде: 
Раскладывая теперь выражения 
и 
в степенные ряды и выделяя коэффициент при , приходим к равенству (6).
В следующей теореме мы установим связь специальных функций с функцией T(n1,n2).
Теорема 4. Количество упорядоченных факторизаций числа N=pn1pn2 равно:
где 
- многочлен Якоби степени n.
Доказательство. Воспользуемся известным представлением многочлена Якоби через биномиальные суммы (см. [3] при n=n1) :
Подставив 
и 
, несложными преобразованиям приходим к требуемой формуле.
Следствие. Количество упорядоченных факторизаций числа 
равно:
где 
- многочлен Лежандра степени .
Для суммы в правой части равенства (5) можно привести более простое рекуррентное соотношение (ср. [1]).
Теорема 5. Для функции T(n1,n2) справедливо:
Общий случай. Теперь можно перечислить преобразования, которые необходимы для получения основного рекуррентного соотношения типа (3). Последовательно заменим в (2) каждый из параметров ni на ni -1, каждую пару параметров ni и nj на 
и 
, и так далее, наконец, заменим все s параметров 
на 
. Из полученных равенств составим выражение, аналогичное формуле включений - исключений:
(В этой формуле для краткости записи слагаемое 
обозначено через 
. Аналогичным образом обозначены остальные слагаемые, входящие в эту сумму). Первая сумма содержит 
слагаемых, вторая - 
слагаемых, и так далее, наконец, последняя 
- слагаемых. Значит, каждое слагаемое 
, кроме , входит в это выражение ровно один раз, поскольку:
Отсюда следует, что выражение в точности равно . Таким образом, доказано рекуррентное соотношение:
|
|
(7) |
Формула (7) остаётся верной и при нулевых значениях параметров (кроме случая, когда все ni равны 0), при этом значения функции T с отрицательными аргументами по-прежнему считаем равными нулю, а 
.
Используя те же манипуляции, как и в случае 
, получаем явный вид производящей функции от переменных:
|
|
(8) |
Как и ожидалось, производящая функция 
обладает симметрией и не меняется при любой перестановке чисел 
.
Опираясь на равенство (8), МакМагон доказал явную формулу для значений в виде двойной суммы слагаемых, каждое из которых представляет произведение биномиальных коэффициентов.
Теорема 6 [8, p. 843]. Пусть 
. Тогда при 
Замечания. Равенство (7) было доказано также в статье [5] с помощью формулы обращения Мёбиуса. Более сложное соотношение для функции приведено в [6]. Комбинаторное доказательство формулы (5), основанное на графической иллюстрации упорядоченной факторизации числа с двумя простыми делителями, дано в [8].
Рецензенты:
- Елизаров А. М., доктор физико-математических наук, профессор, зам. директора по научной деятельности, Казанский (Приволжский) федеральный университет, г. Казань.
- Игнатьев Ю. Г., доктор физико-математических наук, профессор, зав. кафедрой высшей математики и математического моделирования, Казанский (Приволжский) федеральный университет, г. Казань.
Библиографическая ссылка
Киндер М.И. О СОВЕРШЕННЫХ РАЗБИЕНИЯХ НАТУРАЛЬНЫХ ЧИСЕЛ // Современные проблемы науки и образования. 2012. № 5. ;URL: https://science-education.ru/ru/article/view?id=6986 (дата обращения: 04.11.2025).