Разбиение числа

Разбие́ние числа́ n — это представление n в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается (в отличие от композиций), то есть разбиения, отличающиеся только порядком частей, считаются равными. В канонической записи разбиения части перечисляются в невозрастающем порядке.

Число разбиений <math>p(n)</math> натурального числа n является одним из фундаментальных объектов изучения в теории чисел.

Примеры

Например, {3,1,1} или {3,2} — разбиения числа 5, поскольку 5 = 3 + 1 + 1 = 3 + 2. Всего существует p(5) = 7 разбиений числа 5: {1,1,1,1,1}, {2,1,1,1}, {2,2,1}, {3,1,1}, {3,2}, {4,1}, {5}.

Некоторые значения числа разбиений p(n) приведены в следующей таблице^[1]:

n	p(n)	Разбиения
1	1	{1}
2	2	{1,1}, {2}
3	3	{1,1,1}, {2,1}, {3}
4	5	{1,1,1,1}, {2,1,1}, {2,2}, {3,1}, {4}
5	7	{1,1,1,1,1}, {2,1,1,1}, {2,2,1}, {3,1,1}, {3,2}, {4,1}, {5}
6	11
7	15
8	22
9	30
10	42
20	627
50	204 226
100	190 569 292
1000	24 061 467 864 032 622 473 692 149 727 991

Число разбиений

Производящая функция

Последовательность числа разбиений <math>p(n)</math> имеет следующую производящую функцию:

<math>\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \frac {1}{1-x^k}.</math>

Эта формула была открыта Эйлером в 1740 году.

Пентагональная теорема Эйлера

Изучая производящую функцию последовательности <math>p(n)</math>, Эйлер сосредоточил внимание на её знаменателе, то есть, на произведении <math>(1-x)(1-x^2)(1-x^3)\ldots</math>. Это бесконечное произведение при раскрытии скобок приобретает следующий вид:

Показатели степеней x в правой части — это пятиугольные числа, то есть, числа вида <math>(3q^2 + q)/2,</math> где q — целое число, а знак при <math>x^{(3q^2 + q)/2}</math> равен <math>(-1)^q</math>.

Согласно этому наблюдению Эйлер предположил, что должна быть верна Пентагональная теорема:

<math> \prod_{k=1}^\infty \left(1-x^k \right) = \sum_{q=-\infty}^\infty (-1)^q x^{(3q^2+q)/2}</math> .

Впоследствии эта теорема была Эйлером доказана. Она позволяет вычислять числа разбиений при помощи деления формальных степенны́х рядов.

Асимптотические формулы

Асимптотическое выражение для количества разбиений было получено Харди и Рамануджаном и впоследствии уточнено Радемахером. Оригинальное выражение Харди — РамануджанаК:Википедия:Статьи без источников (тип: не указан)^{[источник не указан 4201 день]}

<math>p(n) \sim \frac {\exp \left( \pi \sqrt {\frac {2}{3}} \sqrt {n-\frac{1}{24}}\right) } {4n\sqrt{3}} </math> при <math> n\rightarrow \infty</math>

дает, например, <math>p(1000)\approx 2.44\times 10^{31}</math>. Уточнение Радемахера представляет число разбиений в виде сходящегося ряда

<math>p(n)=\frac{1}{\pi \sqrt{2}} \sum_{k=1}^\infty A_k(n)\;

\sqrt{k} \; \frac{d}{dn} \left( \frac {\sinh \left( \frac{\pi}{k} \sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}\right) } {\sqrt{n-\frac{1}{24}}}\right) </math> где

<math>A_k(n) = \sum_{0\le m < k \; ; \; (m,k)=1}\exp \left(

\pi i s(m,k) - 2\pi inm/k \right).</math>

Здесь суммирование ведется по <math>m</math>, взаимно простым с <math>k</math>, а <math>s(m,k)</math> — сумма Дедекинда. Ряд сходится очень быстро.

Рекуррентные формулы

Количество разбиений числа n на слагаемые, не превышающие k, удовлетворяет рекуррентной формуле:

<math>P(n, k) = \begin{cases}

P(n, k - 1) + P(n - k, k), & k \leqslant n,\\ P(n, n), & k > n, \end{cases}</math> с начальными значениями:

При этом количество всевозможных разбиений числа n равно <math>P(n, n)</math>.

Количество разбиений натурального числа n на k слагаемых удовлетворяет рекуррентной формуле:

с начальными значениями:

<math>P(i, i) = 1\quad \forall i \in \mathbb{N},</math>

<math>P(i, 1) = 1\quad \forall i \in \mathbb{N},</math>

<math>P(i, j) = 0\quad \forall j>i.</math>

Диаграммы Юнга

Основная статья: Диаграмма Юнга

Разбиения удобно представлять в виде наглядных геометрических объектов, называемых диаграммами Юнга, в честь английского математика Альфреда Юнга^[en]. Диаграмма Юнга разбиения <math>(k_1, k_2,\dots,k_m)</math> — подмножество первого квадранта плоскости, разбитое на ячейки, каждая из которых представляет собой единичный квадрат. Ячейки размещаются в строки, первая строка имеет длину <math>k_1</math>, над ней расположена строка длиной <math>k_2</math>, и т. д. до <math>m</math>-ой строки длины <math>k_m</math>. Строки выровнены по левому краю.

Более формально, диаграмма Юнга — это замыкание множества точек <math>(x,y)</math> таких, что

где <math>[x]</math> обозначает целую часть <math>x</math>.

В англоязычной литературе диаграммы Юнга часто изображают отражёнными относительно оси абсцисс.

Схожий объект, называемый диаграммой Феррерса, отличается тем, что

вместо ячеек изображаются точки;
диаграмма транспонируется: ряды и столбцы меняются местами.

Применение

Разбиения естественным образом возникают в ряде математических задач. Наиболее значимой из них является теория представлений симметрической группы, где разбиения естественно параметризуют все неприводимые представления. Суммы по всем разбиениям часто встречаются в математическом анализе.

См. также

Напишите отзыв о статье "Разбиение числа"

Примечания

↑ Последовательность A000041 в OEIS

Литература

Эндрюс Г. Теория разбиений. — М.: Наука, 1982. — 255 с.
Макдональд И. Симметрические функции и многочлены Холла. — М.: Мир, 1985. — 224 с.
Вайнштейн Ф. В. [kvant.mccme.ru/1988/11/razbienie_chisel.htm Разбиение чисел] // Квант. — 1988. — № 11. — С. 19-25.
Фукс Д. [kvant.mccme.ru/1981/08/o_raskrytii_skobok_ob_ejlere_g.htm О раскрытии скобок, об Эйлере, Гауссе, Макдональде и об упущенных возможностях] // Квант. — 1981. — № 8. — С. 12-20.
Бурман Ю. М. [www.mccme.ru/dubna/2004/material.htm Разбиения и перестановки] // Летняя школа «Современная математика». — 2004.
[esciencecommons.blogspot.com/2011/01/new-theories-reveal-nature-of-numbers.html Новая теория доказывает природу цифр]

Отрывок, характеризующий Разбиение числа

– Qu'est ce que c'est que [Что такое] божьи люди? – спросил Пьер
– А вот увидишь.
Княжна Марья действительно сконфузилась и покраснела пятнами, когда вошли к ней. В ее уютной комнате с лампадами перед киотами, на диване, за самоваром сидел рядом с ней молодой мальчик с длинным носом и длинными волосами, и в монашеской рясе.
На кресле, подле, сидела сморщенная, худая старушка с кротким выражением детского лица.
– Andre, pourquoi ne pas m'avoir prevenu? [Андрей, почему не предупредили меня?] – сказала она с кротким упреком, становясь перед своими странниками, как наседка перед цыплятами.
– Charmee de vous voir. Je suis tres contente de vous voir, [Очень рада вас видеть. Я так довольна, что вижу вас,] – сказала она Пьеру, в то время, как он целовал ее руку. Она знала его ребенком, и теперь дружба его с Андреем, его несчастие с женой, а главное, его доброе, простое лицо расположили ее к нему. Она смотрела на него своими прекрасными, лучистыми глазами и, казалось, говорила: «я вас очень люблю, но пожалуйста не смейтесь над моими ». Обменявшись первыми фразами приветствия, они сели.
– А, и Иванушка тут, – сказал князь Андрей, указывая улыбкой на молодого странника.
– Andre! – умоляюще сказала княжна Марья.
– Il faut que vous sachiez que c'est une femme, [Знай, что это женщина,] – сказал Андрей Пьеру.
– Andre, au nom de Dieu! [Андрей, ради Бога!] – повторила княжна Марья.
Видно было, что насмешливое отношение князя Андрея к странникам и бесполезное заступничество за них княжны Марьи были привычные, установившиеся между ними отношения.
– Mais, ma bonne amie, – сказал князь Андрей, – vous devriez au contraire m'etre reconaissante de ce que j'explique a Pierre votre intimite avec ce jeune homme… [Но, мой друг, ты должна бы быть мне благодарна, что я объясняю Пьеру твою близость к этому молодому человеку.]
– Vraiment? [Правда?] – сказал Пьер любопытно и серьезно (за что особенно ему благодарна была княжна Марья) вглядываясь через очки в лицо Иванушки, который, поняв, что речь шла о нем, хитрыми глазами оглядывал всех.
Княжна Марья совершенно напрасно смутилась за своих. Они нисколько не робели. Старушка, опустив глаза, но искоса поглядывая на вошедших, опрокинув чашку вверх дном на блюдечко и положив подле обкусанный кусочек сахара, спокойно и неподвижно сидела на своем кресле, ожидая, чтобы ей предложили еще чаю. Иванушка, попивая из блюдечка, исподлобья лукавыми, женскими глазами смотрел на молодых людей.
– Где, в Киеве была? – спросил старуху князь Андрей.
– Была, отец, – отвечала словоохотливо старуха, – на самое Рожество удостоилась у угодников сообщиться святых, небесных тайн. А теперь из Колязина, отец, благодать великая открылась…
– Что ж, Иванушка с тобой?
– Я сам по себе иду, кормилец, – стараясь говорить басом, сказал Иванушка. – Только в Юхнове с Пелагеюшкой сошлись…
Пелагеюшка перебила своего товарища; ей видно хотелось рассказать то, что она видела.
– В Колязине, отец, великая благодать открылась.
– Что ж, мощи новые? – спросил князь Андрей.
– Полно, Андрей, – сказала княжна Марья. – Не рассказывай, Пелагеюшка.
– Ни… что ты, мать, отчего не рассказывать? Я его люблю. Он добрый, Богом взысканный, он мне, благодетель, рублей дал, я помню. Как была я в Киеве и говорит мне Кирюша юродивый – истинно Божий человек, зиму и лето босой ходит. Что ходишь, говорит, не по своему месту, в Колязин иди, там икона чудотворная, матушка пресвятая Богородица открылась. Я с тех слов простилась с угодниками и пошла…
Все молчали, одна странница говорила мерным голосом, втягивая в себя воздух.
– Пришла, отец мой, мне народ и говорит: благодать великая открылась, у матушки пресвятой Богородицы миро из щечки каплет…
– Ну хорошо, хорошо, после расскажешь, – краснея сказала княжна Марья.
– Позвольте у нее спросить, – сказал Пьер. – Ты сама видела? – спросил он.
– Как же, отец, сама удостоилась. Сияние такое на лике то, как свет небесный, а из щечки у матушки так и каплет, так и каплет…
– Да ведь это обман, – наивно сказал Пьер, внимательно слушавший странницу.
– Ах, отец, что говоришь! – с ужасом сказала Пелагеюшка, за защитой обращаясь к княжне Марье.
– Это обманывают народ, – повторил он.
– Господи Иисусе Христе! – крестясь сказала странница. – Ох, не говори, отец. Так то один анарал не верил, сказал: «монахи обманывают», да как сказал, так и ослеп. И приснилось ему, что приходит к нему матушка Печерская и говорит: «уверуй мне, я тебя исцелю». Вот и стал проситься: повези да повези меня к ней. Это я тебе истинную правду говорю, сама видела. Привезли его слепого прямо к ней, подошел, упал, говорит: «исцели! отдам тебе, говорит, в чем царь жаловал». Сама видела, отец, звезда в ней так и вделана. Что ж, – прозрел! Грех говорить так. Бог накажет, – поучительно обратилась она к Пьеру.
– Как же звезда то в образе очутилась? – спросил Пьер.
– В генералы и матушку произвели? – сказал князь Aндрей улыбаясь.
Пелагеюшка вдруг побледнела и всплеснула руками.
– Отец, отец, грех тебе, у тебя сын! – заговорила она, из бледности вдруг переходя в яркую краску.
– Отец, что ты сказал такое, Бог тебя прости. – Она перекрестилась. – Господи, прости его. Матушка, что ж это?… – обратилась она к княжне Марье. Она встала и чуть не плача стала собирать свою сумочку. Ей, видно, было и страшно, и стыдно, что она пользовалась благодеяниями в доме, где могли говорить это, и жалко, что надо было теперь лишиться благодеяний этого дома.
– Ну что вам за охота? – сказала княжна Марья. – Зачем вы пришли ко мне?…
– Нет, ведь я шучу, Пелагеюшка, – сказал Пьер. – Princesse, ma parole, je n'ai pas voulu l'offenser, [Княжна, я право, не хотел обидеть ее,] я так только. Ты не думай, я пошутил, – говорил он, робко улыбаясь и желая загладить свою вину. – Ведь это я, а он так, пошутил только.

[1] Последовательность A000041 в OEIS

[1]