Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

ON PERFECT PARTITIONS OF INTEGERS

Kinder M.I. 1
1 Kazan (Volga region) Federal University
A perfect partition of a natural number is one which contains one, and only one, partition of every lower number. The purpose of the research is to prove computing recurrence relations that count the number of perfect partitions of a natural number. Using the method of generating functions, we give a simple proof of an explicit formula MacMahon’s for calculating ordered factorizations of natural numbers, and some new recurrence relations when these numbers have only two prime factors. For such natural numbers we found the relationship between the number of ordered factorizations and Jacobi polynomials and Legendre polynomials.
ordered factorization
perfect partitions
Введение. Разбиения чисел являются классическим и достаточно хорошо изученным комбинаторным объектом. Понятие совершенного разбиения числа в 1886 году ввёл МакМагон [7]. Совершенным разбиением числа N называется такое разбиение, в котором содержится лишь одно разбиение каждого числа, меньшего N, при условии, что равные части считаются неразличимыми. Например, набор  из N единиц является одним из совершенных разбиений для каждого натурального N. Для  разбиения ,  и  и только они являются совершенными.

Если все части разбиения рассматривать как разновесы для весов, то совершенные разбиения оказываются решениями проблемы определения такого набора гирь, с помощью которого (при условии размещения гирь на одной чаше весов) можно взвесить единственным способом любой предмет, вес которого выражается целым числом. Именно в такой формулировке на одной из математических олимпиад школьников встретилась задача (11-й Турнир Городов, 1990, автор - Д. Фомин).

Рассматривается набор гирь, каждая из которых весит целое число граммов, а общий вес всех гирь равен 500 граммов. Такой набор называется правильным, если любой груз, у которого вес выражается целым числом граммов от 1 до 500, может быть уравновешен некоторым количеством гирь набора, и притом единственным образом. Груз кладется на одну чашку весов, гири - на другую. Два способа уравновешивания, отличающиеся лишь заменой некоторых гирь на другие того же веса, считаются одинаковыми. Сколько существует различных правильных наборов? (Два набора различны, если некоторая гиря участвует в этих наборах не одинаковое число раз).

Таким образом, в этой задаче требуется найти количество совершенных разбиений числа . В каждом совершенном разбиении, очевидно, должна содержаться по крайней мере одна часть, равная 1. Предположим, что в нём содержится  частей, равных единице. Тогда все числа, меньшие , обладают только одним разбиением, и значит, число  будет следующей частью совершенного разбиения. Пусть теперь в разбиении содержится  частей, равных q1, тогда все числа от 1 до  единственным способом выражаются с помощью 1 и q1. Продолжая рассуждения аналогичным образом, приходим к совершенному разбиению вида:

Сумма всех составных частей этого разбиения равна N, поэтому:

и значит, qi являются делителями числа N+1. Таким образом, упорядоченный набор чисел  полностью определяет данное разбиение, при этом каждый сомножитель qбольше 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) остаётся верной и при нулевых значениях параметров (кроме случая, когда все nравны 0), при этом значения функции T с отрицательными аргументами по-прежнему считаем равными нулю, а .

Используя те же манипуляции, как и в случае , получаем явный вид производящей функции от  переменных:

(8)

Как и ожидалось, производящая функция  обладает симметрией и не меняется при любой перестановке чисел .

Опираясь на равенство (8), МакМагон доказал явную формулу для значений  в виде двойной суммы слагаемых, каждое из которых представляет произведение биномиальных коэффициентов.

Теорема 6 [8, p. 843] Пусть . Тогда  при  

Замечания. Равенство (7) было доказано также в статье [5] с помощью формулы обращения Мёбиуса. Более сложное соотношение для функции  приведено в [6]. Комбинаторное доказательство формулы (5), основанное на графической иллюстрации упорядоченной факторизации числа с двумя простыми делителями, дано в [8].

Рецензенты:

  • Елизаров А. М., доктор физико-математических наук, профессор, зам. директора по научной деятельности, Казанский (Приволжский) федеральный университет, г. Казань.
  • Игнатьев Ю. Г., доктор физико-математических наук, профессор, зав. кафедрой высшей математики и математического моделирования, Казанский (Приволжский) федеральный университет, г. Казань.