стр. 1
(общее количество: 3)

ОГЛАВЛЕНИЕ

След. стр. >>

Библиотека
<Математическое просвещение>
Выпуск 26




К. П. Кохась


ЛАДЕЙНЫЕ ЧИСЛА
И МНОГОЧЛЕНЫ




Издательство Московского центра
непрерывного математического образования
Москва • 2003
УДК 519.113/.118
ББК 22.19
К75


Аннотация
В брошюре рассказано о популярном и очень наглядном ком-
бинаторном объекте: ладейных числах и ладейных многочленах.
Рассмотрены всевозможные неравенства между ладейными числа-
ми. Отталкиваясь от комбинаторных наблюдений, доказана основ-
ная теорема о том, что ладейный многочлен любой доски имеет
только вещественные корни. Это позволяет вывести много новых,
неожиданных с точки зрения комбинаторики неравенств. Вместе
с тем, некоторые комбинаторные неравенства ещё ждут своих ана-
литических доказательств. Текст брошюры может рассматривать-
ся как обзор элементарных результатов о ладейных многочленах.
Текст брошюры представляет собой дополненную обработку
записи лекции для школьников 9—11 классов, прочитанной ав-
тором на Малом мехмате МГУ 21 декабря 2002 года.
Брошюра рассчитана на широкий круг читателей, интересу-
ющихся математикой: школьников старших классов, студентов,
учителей.

Работа автора над брошюрой поддержана Рос-
Р И сийским фондом фундаментальных исследова-
ний (грант № 02—01—00093).
Издание осуществлено при поддержке Московского департамен-
та образования и Московской городской Думы.



ISBN 5-94057-114-X © К. П. Кохась, 2003.
© МЦНМО, 2003.


Константин Петрович Кохась.
Ладейные числа и многочлены.
(Серия: <Библиотека ,,Математическое просвещение“>. Вып. 26).
М.: МЦНМО, 2003. — 20 с.: ил.
Редактор Ю. Л. Притыкин. Техн. редактор М. Ю. Панов.

Лицензия ИД № 01335 от 24/III 2000 года. Подписано в печать 8/VIII 2003 года.
Формат бумаги 60?88 116 . Бумага офсетная № 1. Печать офсетная. Физ. печ. л. 1,25.
/
Усл. печ. л. 1,22. Уч.-изд. л. 1,24. Тираж 3000 экз. Заказ 3040.

Издательство Московского центра непрерывного математического образования.
119002, Москва, Г-2, Бол. Власьевский пер., 11. Тел. 241 05 00.

Отпечатано с готовых диапозитивов
в ФГУП <Производственно-издательский комбинат ВИНИТИ>.
140010, г. Люберцы Московской обл., Октябрьский пр-т, 403. Тел. 554 21 86.
§ 1. ЛАДЕЙНЫЕ ЧИСЛА.
ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ
Рассмотрим обычную шахматную доску и обычную шахмат-
ную фигуру — ладью. Сколькими способами можно поставить на
шахматную доску две ладьи так, чтобы они не били друг друга?
Какое наибольшее число ладей можно поставить на доску так, что-
бы каждая ладья била не более двух других? Можно задать много
подобных вопросов, наверняка читатель встречал такого рода зада-
чи на олимпиадах или в книжках по развлекательной математике
(см., например, книгу [1]).
Вопросы, о которых пойдёт речь в этой брошюре, являются
естественными обобщениями задач о расстановке ладей. Мы рас-
смотрим произвольные доски и обсудим многочисленные свойства
ладейных чисел. Для начала несколько определений.
Пусть дана бесконечная клетчатая плоскость. Доской будем
называть произвольный конечный набор клеток этой плоскости.
Ладья — это фигура, которая держит под боем все
клетки плоскости, находящиеся с ней на одной
горизонтали или на одной вертикали.
Таким образом, для досок сложной формы ла-
дья может держать под боем клетки, отделённые Рис. 1
от неё клетками, не принадлежащими доске. Так,
на рис. 1 изображена несвязная доска из пяти клеток, ладья и клет-
ки, находящиеся под боем этой ладьи (отмечены крестиками).
Зафиксируем произвольную доску B и для каждого натураль-
ного n вычислим количество различных способов поставить на эту
доску n не бьющих друг друга ладей. Обозначим это количество rn
или rn (B), если нужно указать, о какой именно доске идёт речь.
Положим по определению r0 =1. Числа r0 , r1 , r2 , ... называются
ладейными числами доски B.
Очевидно, что r1 (B)=S, где S — площадь (количество клеток)
доски B.
Если же мы хотим разместить на доске слишком много ла-
дей — больше S — у нас ничего не получится: все ладьи не поме-
стятся на нашу доску. Таким образом, для любой доски ладейные
числа с большими номерами равны нулю.
В таблице на рис. 2 приведены примеры досок, состоящих
из пяти клеток, и все их ненулевые ладейные числа. Заметим, что
доски разной формы могут иметь одинаковые наборы ладейных
чисел.
1. Проверьте данные таблицы на рис. 2 *).
Для вычисления ладейных чисел часто хватает несложных
комбинаторных соображений. Найдём, например, чему равно
*) Двумя чертами слева выделены упражнения для самостоятельного решения.
3
Доски Доски
r0 r1 r2 r3 r0 r1 r2 r3

1 5
1 5 5

1 5 3




1 5 5 1




1 5 4


1 5 6 1




Рис. 2

число r3 для обычной шахматной доски 8?8. Трёх ладей на дос-
ке 3?3 можно расставить 3! способами. Чтобы расставить трёх
ладей на доске 8?8, достаточно сначала выбрать три вертикали
и три горизонтали — это можно сделать (C3 )2 способами, а потом
8
на образовавшейся доске 3?3 взять одну из шести расстановок.
Итак, для шахматной доски r3 =6·72 ·82 .
Приведём ещё один пример.
Лемма I. Пусть имеется доска B и c?B — произвольная клет-
ка. Пусть Крест(c) — это множество клеток доски B, лежащих
на той же горизонтали или в той же вертикали, что и клетка c.
Тогда
rk (B)=rk(B\c)+rk?1 (B\Крест(с)). (1)
(Здесь мы используем обычные обозначения: B\c — это доска,
полученная из B удалением клетки c.)
Д о к а з а т е л ь с т в о очевидно: поставить k ладей на доску B
можно либо разместив их так, чтобы клетка c осталась свободной
(это можно сделать rk (B\c) способами), либо поставив одну ладью
в клетку c, тогда остальные придётся ставить вне креста клетки c
(это можно сделать как раз rk?1 (B\Крест(с)) способами).
Заметим, что утверждение леммы I показывает, как можно
вычислить ладейные числа какой-нибудь доски, если известны
ладейные числа меньших досок. Таким образом, на самом деле
4
равенство (1) — это рекуррентная формула, с помощью которой
мы можем вычислять ладейные числа любой доски B (лучше
на компьютере), не пользуясь никакими комбинаторными идеями.
Правда, придётся накопить довольно много информации о ладей-
ных числах досок, которые содержатся в B. Примеры других
рекуррентных формул мы встретим в § 3.
Теперь, когда мы убедились, что вычисление ладейных чи-
сел — задача в принципе решаемая, введём ещё одно понятие.
Две доски назовём эквивалентными, если наборы ладейных чисел
у этих досок совпадают. Примеры эквивалентных досок можно
видеть в таблице на рис. 2.
Изучая ладейные числа различных досок, хотелось бы научить-
ся для каждой доски подбирать эквивалентную доску <достаточ-
но простой> формы. Естественный и простой способ преобразовать
доску так, чтобы её ладейные числа не изменились, состоит в пере-
становке вертикальных или горизонтальных рядов клеток, соста-
вляющих эту доску. Так, для доски на рис. 1, переставляя верти-
кальный ряд клеток, содержащий изолированную клетку, <побли-
же> к <основной части> доски, мы можем получить связную доску

,

что, по-видимому, можно рассматривать как <упрощение> формы.
Другими естественными операциями над досками, сохраняющими
ладейные числа, являются поворот на ±90? или 180? и отражения
доски относительно вертикали, горизонтали или диагонали.
Хотя эти операции и позволяют изменять форму доски, до-
биться <совсем простой> формы, пользуясь этими или ещё каки-
ми-нибудь операциями, видимо, не удастся, что видно уже на при-
мере всё тех же пятиклеточных досок. Но всё же мы будем рас-
сматривать достаточно богатый
класс досок относительно про-
стой формы. Это так называе-
мые диаграммы Юнга.
Диаграмма Юнга со стро-
ками b1 , b2 , ..., bm (0<b1 ?
?b2 ?...?bm) — это доска, го-
а) б)
ризонтали которой выравнены
по левому краю и содержат со- Рис. 3
ответственно b1 , b2 , ..., bm кле-
ток (снизу вверх). Иногда мы будем считать, что диаграмма Юнга
может иметь нулевые строки. На рис. 3 изображены две диаграм-
мы Юнга: квадрат 4?4 (а) и диаграмма Юнга со строками 1, 3,
5, 7 (б).
5
В заключение этого параграфа приведём нетривиальный при-
мер двух эквивалентных досок.
2. Докажите, что доски, изображённые на рис. 3, а, б, эквива-
лентны!

***
Теорема I. Квадратная доска n?n эквивалентна доске Yn
в форме диаграммы Юнга с длинами строк 1, 3, 5, ..., 2n?1.
Д о к а з а т е л ь с т в о. Обозначим квадрат n?n через Kn . Мы
построим по индукции взаимно однозначное соответствие между
расстановками ладей в Kn и в Yn , следуя А. Левиту.
База индукции n=1 очевидна. Докажем индукционный пере-
ход. Разобьём квадрат Kn на две части: квадрат Kn?1 и <рамку>,
состоящую из 2n?1 клеток. Треугольную доску Yn тоже разобьём
на две части: доску Yn?1 и самую длинную горизонталь (тоже
из 2n?1 клеток). Допустим, что совпадение ладейных чисел ква-
драта Kn?1 и треугольника Yn?1 уже установлено. Тогда можно
считать, что построено соответствие между расстановками ладей
в квадрате n?n, в которых все ладьи находятся в выделенной
части (n?1)?(n?1), и расстановками ладей в Yn , в которых все
ладьи находятся в выделенной части Yn?1 . Осталось построить
соответствие между расстановками ладей в Yn , которые содержат
ладью на длинной горизонтали, и расстановками ладей в Kn ,
которые содержат ладьи в <рамке>. Рассмотрим все расстановки
k ладей в Yn , содержащие ладью в длинной строке, у которых
расстановка k?1 ладей в Yn?1 фиксирована, назовём её s, а со-
ответствующую ей расстановку в Kn?1 назовём t. Всего имеется
2n?k=n+(n?k) таких расстановок, поскольку в длинной строке
ровно столько подходящих для последней ладьи клеток. Пронуме-
руем как-нибудь эти клетки (рис. 4).
Если ладья стоит на клетке с номером l, 1?l?n, то поставим
ладью на l-ю клетку вертикальной стороны рамки в Kn , вычерк-
нем мысленно вертикаль и горизонталь, содержащие поставленную
ладью, и на оставшейся части доски (которая представляет
собой <раздвинутый> квадрат Kn?1 , очевидно, у него ладейные
числа такие же, как у Kn?1 ) реализуем расстановку t (рис. 5).


3 5 5
1 2 4 4
3

2

1

Рис. 4
6
5
1 2 4




Рис. 5


Если же ладья стоит на клетке с номером l>n (таких номеров
имеется n?k), то реализуем расстановку t в стандартном квадрате
Kn?1 . Заметим, что среди n?1 клеток <рамки>, расположенных
над Kn?1 , есть ровно n?k мест, куда можно было бы поставить
ладью. Ну так и поставим ладью на (l?n)-е из этих мест (рис. 6).
Построенное соответствие является взаимно однозначным.
Действительно, нетрудно предъявить обратное отображение. Если
в <рамке> квадрата Kn не стоит ни одной ладьи, следует восполь-
зоваться взаимно однозначным отображением, которое существует
по индукционному предположению. Если имеется ладья, стоящая
в первом столбце, следует вычеркнуть её вместе с вертикалью
и горизонталью, которые она занимает, и для оставшейся фигу-
ры (<раздвинутый> квадрат Kn?1 ) опять воспользоваться индук-
ционным предположением. Если же в первом столбце ладьи нет,
но есть ладья в первой строке, следует мысленно удалить рам-
ку, воспользовавшись индукционным отображением, расположить
ладей в диаграмме Yn?1 ?Yn и добавить ладью в самую длинную
строчку диаграммы Yn на подходящее место.
З а м е ч а н и е. Как мы отмечали, число r1 (B) равно площади
доски B. Поэтому, доказав утверждение теоремы I, мы получили
также (не самое простое, зато о ч е н ь комбинаторное) доказатель-
ство равенства
1+3+5+...+(2n?1)=n2.
3. Разглядывая рис. 4—6, докажите, что
rk (Kn )=rk(Kn?1 )+(2n?k) rk?1 (Kn?1 ) .



3
1 2 4




Рис. 6
7
§ 2. КОМБИНАТОРНЫЕ НЕРАВЕНСТВА
С ЛАДЕЙНЫМИ ЧИСЛАМИ
Докажем несколько неравенств с ладейными числами. Будем
считать, что фиксирована произвольная доска B. Говоря о расста-
новке небьющих друг друга ладей, мы часто для краткости будем
опускать слова <друг друга>.
Неравенство 1. Ck rk+m ?rm rk .
k+m
Д о к а з а т е л ь с т в о. Число rm rk имеет ясный комбинатор-
ный смысл: это количество способов разместить на доске k белых
и m чёрных ладей так, чтобы белые ладьи не били белых, а чёр-
ные — чёрных; при этом на любую клетку разрешается ставить
две ладьи, если они разного цвета. Заметим, что из каждой
расстановки k+m небьющих ладей можно получить расстановку
из k белых небьющих ладей и m чёрных небьющих ладей — нужно
просто выбрать, какие ладьи будут белыми (это можно сделать
как раз Ckk+m способами), а остальные ладьи пусть будут чёрными.
Разным исходным расстановкам и разным способам выборки соот-
ветствуют разные пары наборов белых и чёрных ладей, итого —
Ck rk+m пар. Но, конечно же, таким способом мы можем полу-
k+m
чить далеко не все наборы белых и чёрных ладей, поскольку мы
заведомо не получим таких наборов, где имеются чёрная и белая
ладьи, стоящие на одной клетке.
4. Докажите неравенство 18 480r12 ?r9 (не будем скрывать
2

от читателя, что 18 480=C6 ·C3 ).
12 6


***
Неравенство 2. kk?2 rk ?Ck?1 при 1?k?n.
r 2

Д о к а з а т е л ь с т в о. Для любого множества A из k небьющих
ладей построим всевозможные такие наборы из k?1 пар небью-
щих ладей, что все ладьи в этих парах принадлежат A и каждая
ладья из A входит хотя бы в одну пару. Это можно сделать многи-
ми способами. Чтобы подсчитать это число способов, заметим, что
любые k небьющих ладей можно считать упорядоченными, напри-
мер, по расположению их горизонталей сверху вниз. Тогда каждо-
му способу выбора k?1 пар небьющих ладей можно сопоставить
граф, в котором имеется k помеченных вершин, соответствующих
ладьям, и k?1 рёбер, соответствующих выбираемым парам. Этот
граф будет, вообще говоря, несвязным; нетрудно видеть, что в нём
не может быть изолированных вершин. Пусть Nk — число графов,
состоящих из k неизолированных помеченных вершин и k?1 рёбер.
Далеко не всякий набор из k?1 пар ладей может быть получен
таким образом, хотя бы потому, что в н а ш и х наборах общее
8
число ладей равно k, а в произвольном наборе их количество
может быть и другим. Следовательно, мы получаем неравенство
Nk rk ?Ck?1 .
r 2

По-видимому, для чисел Nk нет хорошей формулы, подробности
(в том числе, описание производящей функции) можно прочи-
тать в статье [4]. Для завершения доказательства заметим, что
Nk ?kk?2 , так как последняя величина выражает количество
деревьев с k помеченными вершинами (это утверждение знамени-
той теоремы Кэли).

***
Неравенства, которые мы сейчас рассмотрели, — грубые, по-
скольку не используют <геометрию> доски. Действительно, при
доказательстве этих неравенств мы пользовались теоретико-мно-
жественными соображениями и никак не учитывали взаимораспо-
ложение ладей. Поэтому доказанные неравенства верны в следу-
ющей более общей ситуации. Пусть дано произвольное конечное
множество A. Пусть S — некоторое свойство подмножеств множе-
ства A, удовлетворяющее условию монотонности: если множество
B?A удовлетворяет свойству S, то и любое подмножество B ?B
также удовлетворяет свойству S.
Например, пусть A — произвольное множество натуральных
чисел, а S — свойство <произведение данных чисел нечётно> (или,
скажем, свободно от квадратов). В применении к ладейным числам,
A — это множество клеток доски, S — свойство <все клетки дан-
ного подмножества ладейно независимы> (т. е. каждая вертикаль
и горизонталь содержат не более одной клетки из множества S).
Пусть rk — количество k-элементных подмножеств множества A,
удовлетворяющих свойству S. Тогда величины rk удовлетворяют
неравенствам 1 и 2.
Следующее неравенство значительно тоньше.
Неравенство 3. rk?1 rk+1 ?rk . 2

Д о к а з а т е л ь с т в о. Опять воспользуемся комбинаторным
смыслом обеих частей неравенства: rk?1 rk+1 — это количество
способов поставить на доску k?1 чёрных небьющих ладей и k+1
белых небьющих ладей так, что ладьи разных цветов могут стоять
2
на одной клетке; rk — это количество аналогичных расстановок
k чёрных и k белых ладей.
Фиксируем произвольный набор C из 2k?m клеток доски,
0?m?k. Пусть pC — количество расстановок k?1 чёрных
и k+1 белых ладей, в которых все клетки из C заняты ладьями,
назовём эти расстановки расстановками первого типа, будем счи-
тать, что pС =0 при m=k; qС — количество расстановок k чёрных
9
E
"
"
"

стр. 1
(общее количество: 3)

ОГЛАВЛЕНИЕ

След. стр. >>