Scientific journal

Modern problems of science and education

ISSN 2070-7428

"Перечень" ВАК

ИФ РИНЦ = 1,006

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

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

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

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

и значит, q_i являются делителями числа N+1. Таким образом, упорядоченный набор чисел  полностью определяет данное разбиение, при этом каждый сомножитель q_i больше 1. Следовательно, справедлива следующая:

Теорема 1 [8, 2, 9]. Количество совершенных разбиений натурального числа N совпадает с количеством упорядоченных факторизаций числа N+1 без единичных множителей.

Различными разложениями на множители числа 10 служат 10,  и . Они соответствуют указанным выше совершенным разбиениям 1⁹, 2⁴1 и 1⁴5 числа N=9. В задаче Турнира Городов правильными наборами гирь будут ,  и , соответствующие упорядоченным факторизациям ,  и  числа .

Пусть . Обозначим количество нетривиальных упорядоченных факторизаций числа  через .

Теорема 2. Для функции  справедлива рекуррентная формула:

сумма берётся по всем наборам, в которых    и , причем .

Доказательство. Пусть  - произвольный делитель числа N, отличный от N, то есть  и . Тогда всякая факторизация числа N, у которой первый множитель равен m, получается из соответствующей факторизации числа d, причём число последних, очевидно, равно . Отсюда следует равенство (1).

Добавив к обеим частям равенства (1) слагаемое , можно записать его в виде:

В частности, если число N имеет лишь один простой множитель, то есть s=1 и , из (1) имеем:

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

Случай двух делителей. Воспользуемся равенством (1), определяющим функцию , для получения более простых рекуррентных соотношений. Во-первых, запишем его в виде:

Заменяя n₁ на n₁-1 и вычитая полученное равенство из предыдущего, получим:

Формула (3) остаётся верной и при нулевых значениях параметров n₁, n₂ (кроме случая ), при этом значения функции T с отрицательными аргументами нужно считать равными нулю, а  .

 Пример  1.  Пусть . С помощью рекуррентной формулы (3) находим:

Поскольку , получаем . Другими словами, число , где  - простые числа, имеет ровно три упорядоченные факторизации, а именно: N,  и .

 Пример  2.  Пусть . Тогда:

Опираясь на равенство (3), несложно найти явный вид производящей функции для последовательности . Пусть  - производящая функция для T, то есть:

Слагаемое  в этом равенстве выделено особо для того, чтобы в основной сумме можно было использовать рекуррентное соотношение (3) для . Имеем:

Заменяя соответствующие индексы суммирования в каждой из трёх последних сумм, получим уравнение:

из которого находим:

Теорема 3 [8, p. 860], [4]. Для количества упорядоченных факторизаций числа  справедливы формулы:

где n =n₁+n₂.

Доказательство. Докажем первое из этих равенств. Для этого разложим функцию  из равенства (4) в ряд Тейлора в окрестности точки (0,0):

Коэффициент при x₂ ⁿ² равен:

Раскладывая выражения  и  в степенные ряды, мы получим:

Коэффициент при  в правой части находится из условия . Подставляя вместо l число  и выделяя коэффициент при , получаем равенство:

(Для симметричности формулы в последней сумме верхняя граница n₂ заменена на n=n₁+n₂. Конечно, равенство при этом не нарушается, поскольку биномиальные коэффициенты, у которых верхний индекс больше нижнего, равны нулю.) Равенство (5) доказано. Равенство (6) доказывается аналогично с той лишь разницей, что коэффициент при x₂ ⁿ² представляется в виде:  Раскладывая теперь выражения  и  в степенные ряды и выделяя коэффициент при , приходим к равенству (6).

В следующей теореме мы установим связь специальных функций с функцией T(n₁,n₂).

Теорема 4. Количество упорядоченных факторизаций числа N=pⁿ¹pⁿ² равно:

где   - многочлен Якоби степени n.

Доказательство.  Воспользуемся известным представлением многочлена Якоби через биномиальные суммы (см. [3] при n=n₁) :

Подставив  и , несложными преобразованиям приходим к требуемой формуле.

Следствие.  Количество упорядоченных факторизаций числа  равно:

где  - многочлен Лежандра степени .

Для суммы в правой части равенства (5) можно привести более простое рекуррентное соотношение (ср. [1]).

Теорема 5.  Для функции T(n₁,n₂) справедливо:

Общий случай. Теперь можно перечислить преобразования, которые необходимы для получения основного рекуррентного соотношения типа (3). Последовательно заменим в (2) каждый из параметров n_i на n_i -1, каждую пару параметров n_i и n_j на  и , и так далее, наконец, заменим все s параметров  на . Из полученных равенств составим выражение, аналогичное формуле включений - исключений:

(В этой формуле для краткости записи слагаемое  обозначено через . Аналогичным образом обозначены остальные слагаемые, входящие в эту сумму). Первая сумма содержит  слагаемых, вторая -  слагаемых, и так далее, наконец, последняя  -  слагаемых. Значит, каждое слагаемое   , кроме , входит в это выражение ровно один раз, поскольку:

Отсюда следует, что выражение в точности равно . Таким образом, доказано рекуррентное соотношение:

Формула (7) остаётся верной и при нулевых значениях параметров (кроме случая, когда все n_i равны 0), при этом значения функции T с отрицательными аргументами по-прежнему считаем равными нулю, а .

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

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

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

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

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

Рецензенты:

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