Разбиение чисел (стр. 2 из 3)

а) Докажите, что рассматриваемый вектор (x, y) можно представить в виде суммы различных образующих (или он сам — образующий) тогда и только тогда, когда величина k(x, y) = x + y – (x–y)2 неотрицательна.

б) Докажите, что число N(x, y) различных (с точностью до порядка) представлений вектора (x, y) в виде суммы различных образующих зависит только от числа k = k(x, y). Найдите N(13, 18).

Решение задачи начнём с того, что найдём общий вид целочисленных решений неравенства k(x, y) ≥ 0. Числа x+y и x–y имеют одинаковую чётность, поэтому k(x, y) является чётным при любых целых x, y. Следовательно, для любого целого m≥0 достаточно найти целочисленные решения уравнения x + y – (x–y)2 = 2m. Положим x–y = q. Тогда x+y = 2m+q2. Из этих двух равенств немедленно получаем:

(3)

где q — любое целое число, а m ≥ 0.

Смысл чисел m и q станет более наглядным, если представлять себе векторы вида (3) при m=0 как точки с целыми координатами параболы k(x, y) = 0, лежащей в плоскости (x, y). (Вы понимаете, почему это парабола?) Тогда полученные нами целочисленные решения неравенства k(x, y) ≥ 0. показывают, что все точки с целыми координатами, лежащие на параболе k(x, y) = 0 и внутри неё, получаются сдвигами целых точек этой параболы на векторы (m, m) (рис. 3). Удобно считать, что число m (m=0, 1, 2, ...) — номер параболы, на которой лежит точка (x, y), a q = x–y = 0, ±1, ±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) =

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

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

Мы уже знаем, что 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, пару последовательностей

т.е. элемент множества 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):

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

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

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

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

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

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

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