<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

"
"
"
"
"
"
%
"
" C1 : (u клеток)
"
"
"
"
"
"
"
A
E
"
"
"
"
"
"
" A
"
"
"
"
"
"
"
"
"
"
"
"
"
"
"
"
C2 : s компонент, из них
$
"
t ? нечётные <лестницы>, "
"
"
s?t ? все прочие "
"
"
"
" B
"
"
"
"
"
"
"
"
"
"
"
"
"
"
@
Рис. 7


и k белых небьющих ладей на C, в которых все клетки из C за-
няты ладьями — расстановки второго типа. Докажем, что pC ?qC
для каждого множества C из 2k?m клеток, 0?m?k. Из этого
утверждения сразу следует требуемое неравенство.
Пусть C=C1 ?C2 , где C1 — объединение всех одноклеточных
компонент связности (по отношению к ходу ладьи) множества C,
C2 =C\C1 . Пусть часть C1 содержит u клеток.
Для того чтобы на доске C можно было разместить хотя бы
одну расстановку первого или второго типа, необходимо, чтобы
в каждой вертикали и каждой горизонтали содержалось не более
двух клеток доски C. Это значит, что достаточно рассматривать
только такие доски C, в которых все неодноклеточные компоненты
связности имеют вид <лестничных диаграмм> или их <цикличе-
ских замыканий> (компоненты A и B на рис. 7), для остальных
досок C выполняется pC =qC =0. Пусть имеется s неодноклеточных
компонент связности, C2 =D1 ?D2 ?...?Ds — разбиение части C2
на компоненты связности, пусть t — количество лестничных
диаграмм с нечётным числом клеток среди них (см. рис. 7).
Рассмотрим расстановки первого типа, в которых все клетки
доски C заняты. Очевидно, что в m клетках доски C должны сто-
ять по две ладьи, а в остальных 2k?2m клетках — по одной. За-
метим, что все m клеток с двумя ладьями обязательно должны
располагаться в части C1 . Поэтому, чтобы построить произвольную
10
расстановку первого типа, мы сначала выберем m клеток среди
u клеток части C1 , а оставшиеся клетки доски C раскрасим в два
цвета так, чтобы ладьи, стоящие на клетках одного цвета, не били
друг друга. Заметим, что для каждой <циклической лестничной
диаграммы>, а также для лестничной диаграммы с чётным чи-
слом клеток существует ровно две такие раскраски, причём чёрных
и белых клеток в этих раскрасках поровну, а для лестничной
диаграммы с нечётным числом клеток (в том числе, одноклеточ-
ной) существуют также две раскраски, причём в одной из них
чёрных клеток будет на единицу больше, чем белых, сопоставим
такой диаграмме значение +1, а в другой — наоборот, белых
клеток будет больше чем чёрных, сопоставим такой диаграмме
значение ?1.
Выбор раскраски состоит теперь в том, что мы должны выбрать
одну из двух возможностей для каждой компоненты Di и каждой
из u?m невыбранных клеток части C1 , причём сумма значений
выбранных раскрасок для всех лестничных диаграмм с нечётным
числом клеток должна быть равна ?2 (чтобы чёрных клеток
получилось на две меньше, чем белых). Последнее, кстати, возмож-
но только в том случае когда число u?m+t чётно. Итак, коли-
чество расстановок первого типа, в которых все клетки доски C
заняты, равно
u?m+t
?1
2
m 2s?t C
pC =Cu .
u?m+t


Здесь Cm — это число способов выбрать m клеток из u клеток
u
части C1 , 2s?t — это количество способов выбрать раскраску
в компонентах вида <циклическая лестничная диаграмма>
u?m+t
?1
2
и <лестничная диаграмма с чётным числом клеток>, Cu?m+t —
количество способов выбрать расстановку знаков у набора
из u?m+t единиц так, чтобы сумма полученных чисел со знака-
ми была равна ?2.
По аналогичным соображениям число расстановок второго
типа для той же доски C равно
u?m+t
2
m 2s?t C
qC =Cu u?m+t ,

и мы видим, что оно не меньше числа расстановок первого типа.
Неравенство доказано.
Как видим, доказательство неравенства 3 громоздко, требуют-
ся заметные усилия, чтобы его понять. Замечательно, что позже
мы сумеем дать значительно более простое аналитическое доказа-
тельство этого неравенства и даже усилить его!
11
§ 3. ЛАДЕЙНЫЕ МНОГОЧЛЕНЫ
Выражение
?
+?
rn xn
R(x, B)=
n=0

называется ладейным многочленом доски B.
Говоря более серьёзным языком, ладейный многочлен — это
производящая функция последовательности ладейных чисел дан-
ной доски. Это и в самом деле многочлен, поскольку, как мы
уже отмечали, при больших n ладейные числа любой доски равны
нулю, и сумма в определении ладейного многочлена на самом
деле конечная. Так, например,
# A
!
!
!
! =3x2 +5x+1
!
!
R x, !
 

(это мы знаем из таблицы рис. 2).
В чём идея использования ладейных многочленов (или вооб-
ще производящих функций)? Отталкиваясь от комбинаторных раз-
мышлений о ладейных числах, мы сможем установить какие-то
свойства ладейных многочленов. Эти свойства уже будут выраже-
ны алгебраическим, а не комбинаторным языком. Это позволит
нам вывести новые алгебраические свойства и получить из них
новые, ранее неизвестные, свойства ладейных чисел.
Докажем несколько свойств ладейных многочленов.
Лемма II. Пусть имеется доска B и c — произвольная клетка
доски B. Пусть Крест(c) — это множество клеток доски B, лежа-
щих на той же горизонтали или в той же вертикали, что и клет-
ка c. Тогда
(2)
R(x, B)=R(x, B\c)+x R(x, B\Крест(с)).
Д о к а з а т е л ь с т в о. Многие равенства с производящи-
ми функциями доказываются сравнением коэффициентов в левой
и правой части при одинаковых степенях x. Так, коэффициент
при xk в левой части равен rk (B), а коэффициент при xk в правой
части равен rk (B\c)+rk?1 (B\Крест(с)). Таким образом, нам нужно
проверить равенство
rk (B)=rk(B\c)+rk?1 (B\Крест(с)). (3)
Это в точности рекуррентное соотношение, установленное в лемме I.
Лемма III. Пусть доска B представляет собой объединение двух
не связанных ходом ладьи частей B1 и B2 , тогда
R(x, B)=R(x, B1 ) R(x, B2 ). (4)
12
Д о к а з а т е л ь с т в о. Если нам нужно расставить n ладей, и мы
решили поставить k из них в часть B1 , а остальные — в часть B2 ,
то всего найдётся rk (B1 )rn?k (B2 ) таких расстановок. Значит,
?n
rn (B)= rk (B1 ) rn?k (B2 ). (5)
k=0

Осталось заметить, что коэффициент при xn многочлена R(x, B1 )?
?R(x, B2 ) равен той же самой сумме.
Доказанные два свойства ладейных многочленов выглядят со-
вершенно естественными — эти свойства отвечают на вопросы: как
изменится ладейный многочлен, если из доски удалить одну клет-
ку, и как выглядит ладейный многочлен для доски, состоящей из
двух <ладейно независимых> частей. Заметим, что рекуррентное
соотношение (2) для ладейных многочленов ничуть не сложнее,
чем эквивалентная ему формула (3), а соотношение (4) выглядит
даже проще чем соответствующая формула (5) для ладейных чисел.
5. Пусть Rm,n (x) — ладейный многочлен прямоугольника m?n.
Докажите, что
Rm,n (x)=Rm?1,n (x)+nx Rm?1,n?1 (x).
6. Пусть l — произвольная горизонталь доски B; c1 , c2 , ..., ck —
все клетки доски B, лежащие на этой горизонтали l; Bl — доска,
получающаяся из B вычёркиванием горизонтали l; Bi — доска,
получающаяся из B вычёркиванием горизонтали l и вертикали,
содержащей клетку ci . Тогда
?
k
R(x, B)=R(x, Bl )+x B(x, Bi ). (6)
i=1

Следующее свойство, которое мы хотим доказать, уже не столь
прозрачно. Впервые оно появилось в статье [5] и, судя по всему,
было придумано не как попытка дать ответ на какой-нибудь во-
прос о досках, а как попытка истолковать какое-либо несложное
комбинаторное соображение, вроде тех, что встречались в доказа-
тельствах предыдущих лемм, на языке дифференциальных соотно-
шений. Зачем? Об этом чуть позже.
Лемма IV. Пусть dn — произвольная возрастающая последова-
тельность натуральных чисел, Dn — диаграмма Юнга со строка-
ми d1 , d2 , ..., dn . Пусть
# A
!
e R  , Dn ! .
1 !
dn+1 x

qn (x)=x
x
Тогда
qn (x)=xdn+1 ?dn qn?1 (x), (7)
где qn?1 (x) — производная функции по переменной x.
13
З а м е ч а н и е. Определение функций qn не так уж страшно,
как кажется на первый взгляд. Рассмотрим, например, последова-
тельность d1 =1, d2 =4, d3 =6, ... Тогда D2 — это уже встречавша-
яся нам диаграмма

,

и
# A # A
! =x6 1+5· 1 +3· 3 ! =x4 (x2 +5x+3).
! !
1
x R  , D2 ! !
d3
  x2 
x x
# A
!
R  , Dn ! — это <ладейный много-
1 !
dn+1

Таким образом, функция x
x
член наоборот>: его коэффициенты — это всё те же ладейные чи-
сла, только расположенные не в порядке возрастания номеров,
а в порядке убывания.
Д о к а з а т е л ь с т в о л е м м ы IV. Приравнивая коэффициен-
ты при xdn+1 ?k в левой и правой части, получаем, что требуется
доказать равенство
rk (Dn )=rk (Dn?1 )+(dn ?k+1) rk?1 (Dn?1 ).
Это тождество выражает тот факт, что, расставляя k ладей на дос-
ке Dn , мы можем либо разместить их все в Dn?1 , либо разместить
k?1 ладью в Dn?1 , а последнюю ладью поставить в самой длин-
ной строчке на одно из dn ?k+1 допустимых мест.
Замечание, которое мы сделали после формулировки лем-
мы IV, наводит на мысль, что свобода в определении разных ма-
тематических объектов может и должна быть использована для
достижения различных целей. Рассмотрим, например, следующую
модификацию определения ладейного многочлена.
Пусть k — натуральное число. Введём обозначение
xk =x(x?1)(x?2)...(x?k+1).
Кроме того, положим x0 =1. Пусть степень обычного ладейного
многочлена доски B равна m. Модифицированный ладейный мно-
гочлен доски B определим как функцию
?
m
rk (B)xk .
R(x, B)=
k=0

Следующая теорема (которую мы почерпнули в книге [2]) даёт
явное описание модифицированного ладейного многочлена любой
диаграммы Юнга. Точнее говоря, в формулировке теоремы исполь-
зована функция чуть более общего вида, чем модифицированный
ладейный многочлен, поскольку при определении последнего мы
14
учитывали степень m ладейного многочлена, а в формулировке
теоремы в качестве m используется число, которое может быть
больше или равно этой степени.
Теорема II. Пусть B — диаграмма Юнга со строками b1 , b2 , ...
..., bm (0?b1 ?b2 ?...?bm; как видите, разрешены нулевые стро-
ки). Тогда
?
m
rk (B)xk =
R(x, B)=
k=0
=(x+b1 )(x+b2 ?1)(x+b3 ?2)...(x+bm ?m+1).
Д о к а з а т е л ь с т в о. Проверим, что доказываемое равенство
выполнено для всякого натурального x?m. Перепишем его в виде
?m
x!
=(x+b1 )(x+b2 ?1)(x+b3 ?2)...(x+bm ?m+1).
rk (B)
(x?m+k)!
k=0

На самом деле обе части этого равенства равны количеству расста-
новок m небьющих ладей на диаграмме Юнга со строками b1 +x,
b2 +x, ..., bm +x. Для правой части это так, поскольку мы мо-
жем выбрать место для ладьи в первой строке b1 +x способами,
после этого место для ладьи во второй строке b2 +x?1 способами
и т. д. Левая часть выражает другой способ подсчёта. Считая, что
доска представляет собой объединение прямоугольника x?m и ис-
ходной диаграммы B, поставим k небьющих ладей на часть B. Это
можно сделать rk (B) способами. Чтобы разместить остальных ла-
дей в прямоугольной части, мы выбираем место для первой ладьи
в первой свободной строке (x способов), затем выбираем место для
второй ладьи во второй свободной строке (x?1 способов) и т. д.,
x!
всего способов.
(x?m+k)!
Итак, левая и правая часть совпадают при бесконечно многих
значениях x. Поскольку обе части равенства являются многочле-
нами по переменной x, они совпадают тождественно.
Пользуясь теоремой II, мы можем ответить, например, на та-
кой <топологический> вопрос: ладейные числа некоторой доски B
равны r0 =1, r1 =9, r2 =17, r3 =8, r4 =1; можно ли утверждать,
что эта доска не имеет форму диаграммы Юнга? Да, мы можем
это утверждать, потому что модифицированный ладейный много-
член этой доски
R(x, B)=x(x?1)(x?2)(x?3)+9x(x?1)(x?2)+
+17x(x?1)+8x+1=1+3x+x2 +3x3 +x4
не имеет целых корней. Чуть позже, пользуясь неравенством 7
или теоремой IV, мы сможем доказать, что такой доски вообще
не существует.
15
Следствие II-А. Квадратная доска n?n эквивалентна доске Yn
в форме диаграммы Юнга с длинами строк 1, 3, 5, ..., 2n?1.
Следствие II-Б. Всякая диаграмма Юнга эквивалентна диа-
грамме Юнга с попарно различными строками.
Мы предлагаем читателю самому вывести эти следствия
из утверждения теоремы II. Отметим, что следствие II-А — это
в точности теорема I, а утверждение второго следствия нам ещё
не встречалось. Таким образом, пользуясь модифицированны-
ми ладейными многочленами, мы обнаружили что-то новенькое.
Кстати, для произвольных досок модифицированный ладейный
многочлен вообще может не иметь целых корней. Это видно
хотя бы на примере доски

B= .

Здесь R(x, B)=x2 +4x+5.
§ 4. АНАЛИТИЧЕСКИЕ НЕРАВЕНСТВА
С ЛАДЕЙНЫМИ ЧИСЛАМИ
Теперь наконец-то мы можем сформулировать основную теоре-
му о ладейных многочленах.
Теорема III. Ладейный многочлен диаграммы Юнга с n попар-
но различными строками имеет ровно n вещественных (отрица-
тельных) корней.
Д о к а з а т е л ь с т в о. Ладейный многочлен диаграммы Юнга
с n попарно различными строками имеет степень n. Поэтому до-
статочно проверить, что функция qn (x), определённая в лемме IV,
имеет n вещественных отрицательных корней. Это легко прове-
ряется по индукции. При n=1 имеем: R(x, B1 )=1+d1 x, q1 (x)=
=ex (xd2 +d1 xd2 ?1 ). Как видим, функция q1 имеет отрицательный
корень, обозначим его x0 , кроме того q(0)=q(??)=0. Это значит,
что функция q1 (x) имеет не менее двух отрицательных корней —
хотя бы один на промежутке (??, x0 ) и ещё один на промежутке
(x0 , 0) (это следует из теоремы Ролля). По формуле (7) отсюда следу-
ет, что функция q2 (x) имеет не менее двух отрицательных корней
(а больше двух, как следует из свойств R(x, D2 ), она иметь не мо-
жет, значит, их ровно два). Кроме того, опять q2 (0)=q2 (??)=0.
Значит, q3 имеет не менее трёх вещественных корней, и т. д.
Следствие III-А. Все корни ладейного многочлена произволь-
ной диаграммы Юнга — вещественные (отрицательные) числа.
Д о к а з а т е л ь с т в о. Действительно, благодаря следствию II-Б
мы знаем, что любая диаграмма Юнга эквивалентна диаграмме
Юнга с попарно различными строками. Тогда утверждение сразу
следует из теоремы III.
16
Технически чуть более сложным рассуждением в статье [6]
доказана совсем уж общая теорема.
Теорема IV. Все корни ладейного многочлена произвольной
доски — вещественные (отрицательные) числа.
Д о к а з а т е л ь с т в о. Будем говорить, что многочлен g разде-

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>