Сетевое издание
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,940

О СОВЕРШЕННЫХ РАЗБИЕНИЯХ НАТУРАЛЬНЫХ ЧИСЕЛ

Киндер М.И. 1
1 Казанский (Приволжский) федеральный университет
Разбиение натурального числа называют совершенным, если каждое меньшее число можно единственным образом представить в виде суммы некоторых частей этого разбиения. В статье предлагается простое доказательство вычислительных рекуррентных формул, связанных с подсчётом количества совершенных разбиений натурального числа. Применение аппарата производящих функций позволяет сократить объем необходимых преобразований, благодаря этому удается получить еще одно доказательство явной формулы МакМагона для подсчёта упорядоченных факторизаций натуральных чисел, а также некоторые новые рекуррентные соотношения в случае, когда эти числа имеют только два простых множителя. Для таких натуральных чисел доказана связь количества упорядоченных факторизаций с многочленами Якоби и Лежандра.
упорядоченная факторизация
совершенное разбиение числа
1. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. - М.: Мир, 1998. - 703 с. (Задача 101, с. 284.)
2. Гульден Я., Джексон Д. Перечислительная Комбинаторика. - М.: Наука, 1990. - 504 c. (Задача 2.5.12, с. 99.).
3. Прудников А. П., Брычков Ю. А., Маричев О. И. Интегралы и ряды: В 3 т. Т. 1. Элементарные функции. - М.: Физматлит, 2002. - 632 с. (4.2.7.30.).
4. Chor B., Lemke P., Mador Z. On the number of ordered factorizations of natural numbers // Discrete Mathematics. - 2000. Vol. 214. - P. 123-133.
5. Hill E. A problem in "Factorisatio Numerorum" // Acta Arithmetica. - 1936. Vol. 2. - P. 134-144.
6. Kühnel U. Über die Anzahl der Produktdarstellungen der positiven ganzen Zahlen // Archiv der Mathematik. - 1950. Vol. 2. № 3. - S. 216-219.
7. MacMahon P. A. Certain special partitions of numbers // Quarterly Journal of pure and applied Mathematics. - 1886. Vol. 21. - P. 367-373.
8. MacMahon P. A. Memoir on the Theory of the Compositions of Numbers // Philosophical Transactions of the Royal Society of London (A). - 1893. Vol. 184. - P. 835-901.
9. O'Shea E. Bachet's Problem: as few weights to weigh them all. URL: http: // arxiv.org/abs/1010.5486 (дата обращения 26.10.2010).
Введение. Разбиения чисел являются классическим и достаточно хорошо изученным комбинаторным объектом. Понятие совершенного разбиения числа в 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].

Рецензенты:

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

Библиографическая ссылка

Киндер М.И. О СОВЕРШЕННЫХ РАЗБИЕНИЯХ НАТУРАЛЬНЫХ ЧИСЕЛ // Современные проблемы науки и образования. – 2012. – № 5. ;
URL: https://science-education.ru/ru/article/view?id=6986 (дата обращения: 21.09.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074