Xreferat.com » Рефераты по математике » Разбиение чисел

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

±2, ... — номер точки на этой параболе.

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

Рис. 3.

Поскольку условия задачи симметричны относительно перестановки координат векторов, достаточно доказать все утверждения для таких векторов (x, y), что x ≥ y, т.е. для векторов вида (3) с q ≥ 0.

Докажем достаточность условия в пункте а) задачи. По формуле суммы арифметической прогрессии

1 + 2 + ... + (q–1) + m + q = m +

q(q + 1)

2

;
0 + 1 + ... + (q–2) + m + (q–1) = m +

q(q – 1)

2

.

Поэтому формулы

(x, y) = (1, 0) + (2, 1) + ... + (q–1, q–2) + (m+q, m+q–1) при q>0

и

(m, m) = (1, 0) + (m–1, m) при q=0, m>0

дают представления (x, y) в виде суммы различных образующих.

Доказать необходимость условия тоже несложно. Пусть

(x, y) = (r1, r1–1) + ... + (ra, ra–1) + (s1, s1+1) + ... + (sb, sb+1)

— представление вектора (x, y) с x ≥ y в виде суммы различных образующих, где

r1 > r2 > ... > ra > 0,

s1 > s2 > ... > sb ≥ 0.

(4)

Для такого вектора

x = r1 + ... + ra + s1 + ... + sb,

y = r1 + ... + ra – a + s1 + ... + sb + b,

поэтому x–y = a–b. Положим q = x–y и

m = (r1–q) + (r2–(q–1)) + ... + (rq–1) + rq+1 + ... + ra + s1 + ... + sb =

= x –

q(q + 1)

2

=

x + y

2

+

x – y

2

–

q(q + 1)

2

=

x + y

2

–

q²

2

(здесь мы снова воспользовались формулой суммы арифметической прогрессии). Из неравенств (4) следует, что rq ≥ ra ≥ 1, rq–1 ≥ 2, rq–2 ≥ 3, ... и вообще rk ≥ q–k+1. Поэтому m ≥ 0, т.е. (x, y) — вектор вида (3), что и требовалось доказать.

В геометрических терминах утверждение б) означает, что число N(x, y) зависит лишь от номера m параболы и не зависит от номера q точки на параболе.

Пусть T(m, q) — множество представлений вектора (3) в виде суммы различных образующих и t(m, q) — число таких представлений. Задача будет решена, если мы докажем, что для любого целого q имеет место равенство t(m, q) = t(m, q–1) (это и значит, что t(m, q), а вместе с ним N(x, y), не зависит от q). Мы отождествили выше множество T(m, q) с множеством таких пар последовательностей, удовлетворяющих неравенствам (4), что

r1 + ... + ra + s1 + ... + sb = m +

q(q + 1)

2

при q = a–b.

Такую пару мы будем записывать в виде (r1, ..., ra | s1, ..., sb).

Рассмотрим отображение φ множества T(m, q) в множество T(m, q–1), заданной формулой

φ(r1, ..., ra | s1, ..., sb) =
(r1–1, ..., ra–1 | s1+1, ..., sb+1, 0), если ra > 1,
(r1–1, ..., ra–1–1 | s1+1, ..., sb+1), если ra = 1.

Упражнение 6. Проверьте, что φ(r1, ..., ra | s1, ..., sb)  T(m, q–1).

Чтобы доказать, что φ — взаимно однозначное отображение, построим обратное отображение ψ: T(m, q–1) → T(m, q), прочитав правило, задающее φ, слева направо:

ψ(r1, ..., ra | s1, ..., sb) =
(r1+1, ..., ra+1, 1 | s1–1, ..., sb–1), если sb > 0,
(r1+1, ..., ra+1 | s1–1, ..., sb–1–1), если sb = 0.

Построенные отображения взаимно обратны, поэтому φ — взаимно однозначное соответствие. Значит, t(m, q) = t(m, q–1), что и утверждалось.

Чтобы научиться вычислять значения N(x, y), установим связь между числами t(m, q) и p(m).

Утверждение: t(m, q) = p(m).

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

Рис. 4.

Мы уже знаем, что t(m, q) = t(m, 0), поэтому достаточно доказать, что t(m, 0) = p(m). Воспользуемся простым и полезным графическим средством, называемым диаграммой Юнга разбиения. Рассмотрим, например, разбиение (6, 4, 4, 2, 1). Его диаграмма Юнга изображена на рис. 4 (в первой строчке стоят 6 точек, во второй — 4, в третьей — 4, в четвёртой — 2, в пятой — 1). Всякое разбиение можно изобразить в виде диаграммы Юнга и по всякой диаграмме Юнга — записать разбиение.

Проведём на диаграмме Юнга диагональ — чёрная линия на рис. 4. Пусть r1 — число точек в первой строке, лежащих на диагонали и справа от неё, r2 — число точек второй строки, лежащих на диагонали и справа от неё, и т.д.; s1 — число точек первого столбца под диагональю, s2 — число точек второго столбца под диагональю и т.д. Поставим в соответствие диаграмме Юнга, изображающей разбиение числа m, пару последовательностей

(r1, r2, ... | s1, s2, ...),

r1 + r2 + ... + s1 + s2 + ... = m,

т.е. элемент множества T(m, 0). Например, диаграмме на рис. 4 соответствует пара (6, 3, 2 | 4, 2, 0). Зная пару последовательностей, можно легко восстановить диаграмму Юнга. Следовательно, мы установили взаимно однозначное соответствие между множеством разбиений и множеством T(m, 0). Утверждение доказано.

Теперь ничего не стоит ответить и на последний вопрос задачи — о значении N(13, 18). Поскольку 13 = 3+5·4/2, 18 = 3+6·5/2, точка (13, 18) лежит на третьей параболе. Значит, N(13, 18) = t(3, 0) = p(3) = 3.

Следующие упражнения — на применение диаграмм Юнга.

Упражнения

7. Число разбиений n не более чем с k частями, равно числу разбиений n с частями, не превосходящими k. Подсказка: отразите диаграмму Юнга относительно диагонали.

8. Число разбиений n с различными нечётными частями равно числу разбиений n, диаграмма Юнга которых симметрична относительно диагонали. Подсказка: вспомните соответствие Сильвестра.

Формула Гаусса–Якоби

Решая задачу М1065, мы проделали большую работу. Нельзя ли снова воспользоваться производящими функциями и извлечь из равенства t(m, q) = p(m) какое-нибудь красивое тождество?

N(x, y) — это число способов, которыми можно представить вектор (x, y) как сумму различных образующих вида (k, k–1) и (k–1, k). Рассуждая так же, как при выводе формулы производящей функции числа разбиений с различными частями, мы запишем производящую функцию для N(x, y) (это ряд от двух переменных u и v):

∞ ∞
∏ (1 + uk–1 vk)(1 + uk vk–1) = ∑ N(x, y)ux vy.
k=1 x,y=0

Поскольку N(x, y) = t(m, q), где x = m + q(q+1)/2, y = m + q(q–1)/2, равенство можно продолжить:

∞ ∞
= ∑ ∑ t(m, q)um vm uq(q+1)/2 vq(q–1)/2.
q=–∞ m=0

Воспользуемся теперь тем, что t(m, q) = p(m) и продолжим равенство:

∞ ∞
= ∑ ∑ p(m)um vm uq(q+1)/2 vq(q–1)/2.
q=–∞ m=0

Ряд, стоящий в скобках, — производящая функция чисел разбиения p(m), которую мы знаем (формула (1)), поэтому продолжаем:

∞ ∞
= ∏ (1 – uk vk)–1 ∑ uq(q+1)/2 vq(q–1)/2.
k=1 q=–∞

Теперь приравняем левую часть первого и правую часть последнего равенства, умножив обе части на ∏ (1–uk vk). Получим окончательный результат:

∞ ∞
∏ (1 + uk–1 vk)(1 + uk vk–1)(1 – uk vk) = ∑ uq(q+1)/2 vq(q–1)/2.
k=1 q=–∞

Это тождество — цель наших преобразований. Оно называется формулой Гаусса–Якоби. Из этого замечательного тождества с двумя переменными можно получить много разных тождеств с одной переменной.

Упражнение 9. Подставьте в формулу Гаусса–Якоби u = –t, v = –t2 и получите пентагональную теорему Эйлера.

Теперь подставим в формулу Гаусса–Якоби u = v = – t. В левой части получится:

∞ ∞ ∞
∏ (1 – t2k–1)2 (1 – t2k) = ∏ (1 – t2k–1) ∏ (1 – tk).
k=1 k=1 k=1

Заменяя произведение ∏ (1 – t2k–1) на ∏ (1 + tk)–1 по формуле (2), мы преобразуем левую часть в

(1 – t)(1 – t2)(1 – t3) ...

(1 + t)(1 + t2)(1 + t3) ...

.

Правая часть формулы Гаусса–Якоби при подстановке u = v = – t превращается в

∞
∑ (–1)q² tq²,
q=–∞

и мы получаем следующую формулу:

(1 – t)(1 – t2)(1 – t3) ...

(1 + t)(1 + t2)(1 + t3) ...

= 1 – 2t + 2t4 – 2t9 + 2t16 – ...

Подстановка u = t, v = 1 в формулу Гаусса–Якоби аналогичным образом приводит к формуле:

(1 – t2)(1 – t4)(1 – t6) ...

(1 – t)(1 – t3)(1 – t5) ...

= 1 + t + t3 + t6 + t10 + ...

Эти две формулы получены Гауссом. Нечего и говорить, что это удивительно красивые формулы!

Тождества Роджерса–Рамануджана

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

Первое тождество. Число разбиений натурального числа п, в которых разность между любыми двумя частями превосходит единицу, равно числу разбиений числа п на части, дающие при делении на 5 остаток 1 или 4.

Второе тождество. Число разбиений натурального числа п, в которых разность между любыми двумя частями и каждая часть превосходят единицу, равно числу разбиений числа п на части, дающие при делении на 5 остаток 2 или 3.

Конечно, закономерность, утверждаемая этими тождествами, в высшей степени красива и нетривиальна, и неудивительно, что крупнейший английский математик начала XX века Г. Харди, узнавший о них из письма Рамануджана, датированного 16 января 1913 года, пришёл в восхищение. *)

При чтении этой статьи у вас, может быть,

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: