Ладейные многочлены

К. П. Кохась

		+oo
R(x,C)	=	S	rnxn
		n=0

0.1. Докажите, что количество способов поставить на доску 100*100 максимально возможное число не бьющих друг друга слонов - точный квадрат.
Решение.

0.2. Докажите, что эквивалентные доски имеют одинаковые площади.
Решение.

0.3. Придумайте квадратный трехчлен с натуральными коэффициентами, не являющийся ладейным.

0.4. Сколькими способами можно расставить на доске 8*8 трех небьющих друг друга ладей?
Решение.

0.5. Сколькими способами можно расставить на доске 8*8 четырех небьющих друг друга ладей, ни одна из которых не стоит на главной диагонали?
Решение.

1.1. Если доска C представляет собой объединение двух не связанных ходом ладьи частей C₁ и C₂, то R(x,C)= R(x,C₁)R(x,C₂).
Решение.

1.2. Пусть c - произвольная клетка доски C, C₁=C \ {c}, C₂ - доска, полученная удалением из C всех клеток, находящихся в одной строке или одном столбце с клеткой c (включая клетку c). Докажите, что R(x, C)=R(x, C₁) + x*R(x, C₂).
Решение.

1.3. Найдите какую-нибудь связную относительно хода ладьи доску B, у которой r₅(B)=1998.
Решение.

1.4. Есть n замков и n ключей от этих замков. Чтобы узнать, подходит ли ключ к замку, достаточно вставить его в замочную скважину и повращать. Какое наименьшее число таких попыток нужно сделать, чтобы узнать, какой ключ от какого замка?
Решение.

1.5. Теорема Кёнига (D. K\"onig). Линией будем называть вертикальный или горизонтальный ряд клеток. Докажите, что наибольшее число не бьющих друг друга ладей, которые можно поставить на доску, равно n тогда и только тогда, когда наименьшее число линий, в объединении которых содержится эта доска, равно n.
Решение.

2.1. Придумайте пару эквивалентных десятиклеточных досок, не сводящихся друг к другу перестановкой строк или столбцов и поворотами.
Решение.

2.2. Пусть T_n - диаграмма Юнга со строками 1, 2, 3, ..., n-1. Докажите, что T_n не эквивалентна никакой другой диаграмме Юнга.
Решение.

2.3. Докажите, что квадратная доска n*n эквивалентна доске Y_n в форме диаграммы Юнга с длинами строк 1, 3, 5, ..., 2n-1.

 _ _ _ _ _ _ _
|_|_|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|
|_|

2.4. Если две доски эквивалентны, то эквивалентны и их дополнения на любой прямоугольной доске, в которой они обе помещаются.
Решение.

3.1. Докажите, что r_km < r_k^m.
Решение.

3.2. Докажите, что C^k_k+n r_k+n < r_kr_n .
Решение.

3.3. Докажите, что r₄+r₃ < (1/6)r₂(r₂-1) .

3.4. Докажите, что 18480*r₁₂ < (r₉)² .
Решение.

3.5. Докажите, что k^k-2r_k < C_r2^k-1 .
Решение.

3.6. Пусть степень многочлена R(x, B) равна n. Докажите, что при всех k < n/2     r_k < r_n-k .
Решение.

4.1. Пусть R_m,n(x) - ладейный многочлен прямоугольника m*n. Докажите, что

R_m,n(x) = R_m-1,n(x)+nxR_m-1,n-1(x) .

4.2. Пусть d_n - произвольная возрастающая последовательность натуральных чисел. Обозначим D_n - диаграмму Юнга со строками d₁, d₂, ... , d_n. Пусть q_n(x)= x^(d_n+1)e^xR(1/x, D_n) . Докажите, что q_n(x)= x^(d_n+1-d_n)q'_n-1(x) .
Решение.

4.3. Задача о слонах. Слон - это, при правильном взгляде на вещи, тоже ладья. Пусть B_n(x) - ладейный многочлен расстановок чернопольных слонов, W_n(x) - ладейный многочлен расстановок белопольных слонов на доске n*n (как всегда, клетка a1 черная). Докажите, что B_2n-1(x) = W_2n-1(x) + xB_{2n}(x).
Решение.

5.1. Пусть T_n - доска из задачи 2.2, T_n= {(i,j): 1<i<n, 1<j<i}. Докажите, что r_k(T_n) равно количеству способов разбить множество из n элементов на n-k подмножеств. (Эта величина обозначается S(n, n-k) и называется числом Стирлинга второго рода.)

Для произвольного графа Г с n пронумерованными вершинами обозначим q_k(Г) - количество способов раскрасить вершины этого графа в k цветов так, чтобы любые две вершины, соединенные ребром, были разного цвета. Раскраски, отличающиеся "перестановкой" цветов, считаются одинаковыми, иными словами, раскраска в k цветов - это такое разбиение множества вершин на k подмножеств, в котором концы каждого ребра лежат в разных подмножествах. Величины q_k(Г) называются хроматическими числами графа Г, а весь набор (q_n, q_n-1, ...) - хроматическим вектором (будем располагать его компоненты по убыванию числа цветов). В предыдущей задаче фактически требуется доказать, что ладейные числа графа T_n совпадают с хроматическими числами "пустого" графа Г_n с n вершинами и без ребер: r_k(T_n)= q_n-k(Г_n) .
Решение.

5.2. Найдите граф с n вершинами, хроматические числа которого совпадают с ладейными числами доски T^~_n= {(i,j): 1 < i < n, 1 < j < i-1}.
Ответ.

6.1. Пусть B - диаграмма Юнга со строками b₁, b₂,..., b_m   (0 < b₁ < b₂ <...< b_m). Для всякого целого p > m докажите, что

m
S	rk(B)p!/((p-m+k)!)=(p+b1)(p+b2-1)(p+b3-2)...(p+bm-m+1)
k=0

7.1. Для каждого n среди всех связных относительно хода ладьи досок, состоящих из n клеток, найдите такую, на которую можно поставить несколько (не фиксированное количество) не бьющих друг друга ладей наибольшим числом способов. Чему равно это число способов?
Решение.

8.1. Докажите, что ВСЕ корни ладейного многочлена любой диаграммы Юнга - действительные отрицательные.
Решение.

Промежуточный финиш

2.5. Теорема Капланского (I. Kaplansky). Рассмотрим прямоугольник m*(n+p), который для удобства будем считать состоящим из двух частей: части C - прямоугольника m*n и оставшейся части D - прямоугольника m*p. Пусть A и B - эквивалентные доски, расположенные внутри части D. Тогда доски AUC и BUC тоже эквивалентны.
Решение.

2.6. Докажите эквивалентность досок:

 _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|
|_|_|

 _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|
|_|_|_|_|_|
|_|_|_|_|
|_|
|_|

3.7. Многочлен f степени n называется возвратным, если f(x)=xⁿf(1/x). Докажите, что при всех n>9 существует связная относительно хода ладьи доска из n клеток с возвратным ладейным многочленом.

5.3. Пусть B - произвольная доска. Докажите, что существует граф Г_B, хроматические числа которого совпадают с ладейными числами доски B.
Решение.

5.4. Верно ли, что всякий хроматический вектор является ладейным?
Ответ.

5.5. Найдите два графа, у которых совпадают хроматические вектора.
Решение.

6.2. С каждой диаграммой Юнга B с m строками b₁, b₂, ..., b_m   (0<b₁<b₂ <...<b_m ; разрешаются нулевые строки) свяжем (неупорядоченный) набор чисел

S(B) = (b₁, b₂-1, b₃-2,..., b_m-m+1) .

6.3. Сколько существует диаграмм Юнга, эквивалентных квадрату n*n ?
Ответ.

6.4. Теорема Фоата-Шютценберже (D. Foata - M. P. Sch\"utzenberger) Докажите, что для каждой диаграммы Юнга найдется ровно одна эквивалентная диаграмма Юнга с различными ненулевыми строками.
Решение.

7.2. Проверьте, что при всех n выражение sin((n+1)j)/(sin j) является многочленом степени n относительно cos j. Этот многочлен обозначается U_n(x) и называется многочленом Чебышева второго рода.
Решение.

7.3. Пусть L_n - ладейный многочлен доски из задачи 7.1. Докажите, что
Решение.

L_2k-1(x)= (-1)^kx^kU_2k(-1/(4x))^1/2 .

Будем говорить, что многочлен g разделяет корни многочлена f, если
1) deg g = deg f или deg g = deg f - 1;
2) Все корни многочленов f и g - вещественные отрицательные, f(0)>0, g(0)>0.
3) Если 0>x₁>x₂>... - корни многочлена f, 0>y₁>y₂... - корни многочлена g, то 0>x₁>y₁>x₂>y₂>... .

8.2. Докажите, что если многочлены g_i(x), i=1, 2, ..., k разделяют корни многочлена f(x), то f(x) разделяет корни

	k
f(x)+x	S	gi(x)
	i=1

Решение.

8.3. Докажите, что все корни ладейного многочлена любой доски B - вещественные отрицательные.
Решение.

8.4. Докажите, что для любой доски B    r_k-1r_k+1<(r_k)² .
Решение.

8.5. Верно ли, что (r_k-1+r_k+1)/2 < r_k ?
Решение.

8.6. Докажите, что для любой монотонной диаграммы Юнга с n строками

r_n-1/C_n^n-1 > (r_n-2/C_n^n-2)^1/2 > (r_n-3/C_n^n-3)^1/3 > ... > (r₀/C_n⁰} )^1/n