Викия

Математика

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

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

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

ПримерыПравить

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

Число разбиенийПравить

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

\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \left(\frac {1}{1-x^k} \right).

ПримерыПравить

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

  • p(1) = 1
  • p(2) = 2
  • p(3) = 3
  • p(4) = 5
  • p(5) = 7
  • p(6) = 11
  • p(7) = 15
  • p(8) = 22
  • p(9) = 30
  • p(10) = 42
  • p(100) = 190 569 292
  • p(1000) = 24 061 467 864 032 622 473 692 149 727 991 ( ≈2.4 × 1031)

Асимптотические формулыПравить

Асимпототическое выражение для количества разбиений было получено Харди и Рамануджаном и впоследствии уточнено Радемахером. Оригинальное выражение Харди — Рамануджана

p(n) \sim \frac {\exp \left( \pi \sqrt {2n/3}\right) } {4n\sqrt{3}}  при  n\rightarrow \infty

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

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)

где

A_k(n) = \sum_{0\le m < k \; ; \; (m,k)=1}\exp \left( 
\pi i s(m,k) - 2\pi inm/k \right).

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

КонгруэнтностиПравить

Диаграммы ЮнгаПравить

Файл:Young diagram 541 French.png
Разбиения удобно представлять в виде наглядных геометрических объектов, называемых диаграммами Юнга, в честь английского математика Альфреда Юнга. Диаграмма Юнга разбиения (k_1, k_2,\dots,k_m) — подмножество первого квадранта плоскости, разбитое на ячейки, каждая из которых представляет собой единичный квадрат. Ячейки рамещаются в строки, первая строка имеет длину k_1, над ней расположена строка длиной k_2, и т.д. до m-ой строки длины k_m. Строки выровнены по левому краю.

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

x,y> 0 и y< \sum_{j=[x]}^{m} k_j,

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

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

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

ПрименениеПравить

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

Смотрите такжеПравить

ЛитератураПравить

  • Эндрюс Г. Теория разбиений. — М.: Наука, 1982. — 255 с.
  • Макдональд И. Симметрические функции и многочлены Холла. — М.: Мир, 1985. — 224 с.
  • 9 число бога


he:פונקציית החלוקה (תורת המספרים)

sv:Partitionsfunktionen

Викия-сеть

Случайная вики