<< Пред. стр.

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

ОГЛАВЛЕНИЕ

ляет корни многочлена f, если
1) deg g=deg f или deg g=deg f?1;
2) все корни многочленов f и g — вещественные отрицатель-
ные, f(0)>0, g(0)>0;
3) если 0>x1 >x2 >... — корни многочлена f, 0>y1 >
>y2 >... — корни многочлена g, то 0>x1 >y1 >x2 >y2 >...
Лемма V. Проверим, что если многочлены gi (x), i=1, 2, ..., k,
разделяют корни многочлена f(x), то f(x) разделяет корни

?
k
gi (x).
f(x)+x
i=1

?
k
Обозначим F(x)=f(x)+x gi (x). Из свойств 2) и 3) разделе-
i=1
ния корней следует, что старшие коэффициенты многочленов f
и gi положительны и f(x)>0, gi (x)>0 при x>0. Значит, степень F
равна или на единицу больше степени f, и у F нет положитель-
ных корней. Далее, если 0>x1 >x2 >... — корни многочлена f,
то из свойства разделения корней следует, что F(x1 )<0, F(x2 )>0,
F(x3 )<0 и т. д. Следовательно, у многочлена F имеется корень
на каждом из промежутков (x1 , 0), (x2 , x1 ), (x3 , x2 ), ..., а если
deg F=deg f+1, то ещё и на промежутке (??, xdeg f ), причём
на каждом из упомянутых промежутков есть ровно один корень.
Значит, f разделяет корни F. Лемма доказана
Вернёмся к доказательству теоремы. Докажем индукцией
по площади доски B, что ладейный многочлен доски B , получен-
ной из B вычёркиванием строки или столбца, разделяет корни
ладейного многочлена доски B. Для доски, состоящей из одной
или двух клеток, это утверждение очевидно. Если для досок,
не превосходящих по площади n?1, утверждение задачи уже уста-
новлено, то, благодаря соотношению (6) и утверждению леммы V,
мы сразу получаем, что многочлен R(x, Bl ) разделяет корни мно-
гочлена R(x, B) (для столбцов аналогично).
Утверждение теоремы IV является частью доказанного ут-
верждения.
Итак, ладейный многочлен любой доски B имеет только веще-
ственные корни. Это означает, что ладейный многочлен — очень
специальное и редкое явление во множестве всех многочленов.
В частности, это значит, что ладейный многочлен любой доски
17
может быть разложен на линейные множители:
rn xn +rn?1 xn?1 +...+r0 =rn (x+a1 )(x+a2 )...(x+an ),
где все числа ai — вещественны. Раскрывая скобки и приравнивая
коэффициенты при xk , мы получаем, что
?
rk
= (8)
ai ai ...ai .
rn 1 2 k
1?i1 <i2 <...<ik ?n

Здесь в правой части написана сумма всевозможных произведений,
составленных из k сомножителей.
Что дают эти наблюдения для доказательства неравенств с ла-
дейными числами? Докажем ещё раз неравенство 3: rk?1 rk+1 ?rk 2

для любой доски B.
В т о р о е д о к а з а т е л ь с т в о н е р а в е н с т в а 3. Воспользу-
емся формулой (8). Поскольку доказываемое неравенство однород-
но, можно считать, что rn =1. Тогда выражение rk?1 rk+1 ?rk со- 2

стоит из слагаемых вида a2 a2 ...a2 aj , причём каждое такое
...aj
jj j
1 2 s s+1 k+s

слагаемое входит с коэффициентом C2s ?Cs <0.
s?1
2s
Для симметрических функций известно много других нера-
венств. Все они могут быть записаны как неравенства о ладейных
числах! Мы приведём несколько таких неравенств. Доказательства
и технические подробности можно прочитать в книге [3].
Неравенство 4.
rk+m rk rm
k+m ? .
Ck Cm
Cn nn

k
Так как Ck Cm ?Ck+m Ck+m , то это неравенство сильнее нера-
nn n
венства 1.
Неравенство 5 (неравенство Ньютона).
# A2
r! !
rk?1 rk+1
? k ! .
k!
k?1 k+1
Cn Cn
Cn

Это неравенство сильнее неравенства 3, поскольку его можно
записать в виде
# A# A
1! !
rk?1 rk+1 1+ ! 1+ ! ?r2 .
1
! !
 n?k  k
k
Неравенство 6 (неравенство о симметрических средних). Если
степень ладейного многочлена равна n, то при 0?m<k?n
# A1/k # A1/m
rk ! !
!
! ? rm !!
!  m! .
 k  Cn
Cn
18
§ 5. ЕЩЁ ОДНО НЕРАВЕНСТВО
В предыдущем параграфе мы обнаружили метод генерации
неравенств с ладейными числами. К сожалению, с его помощью
не удаётся доказать все неравенства с ладейными числами. При-
ведём напоследок пример комбинаторного неравенства, которое
не следует из результатов предыдущего параграфа.
Посмотрим ещё раз на неравенство 3. Запишем его в таком виде:
ln rk?1 +ln rk+1
?ln rk .
2
Последовательность xn , удовлетворяющая свойству
xk?1 +xk+1
?xk ,
2
называется выпуклой вверх или вогнутой. Её график — <выпуклое
множество> (правда, дискретное). Он состоит из возрастающего
участка за которым, быть может, следует убывающий. Таким
образом, график последовательности ладейных чисел представляет
собой <подъём> или <холмик>. Следующее неравенство показы-
вает, что этот холмик перекошен вправо.
Неравенство 7. Если степень ладейного многочлена доски B
равна n, то
rk ?rn?k , 0?k?n/2.
Д о к а з а т е л ь с т в о. Так как rn ?1, то rn ?r0 . Выберем
любую из расстановок n небьющих ладей на доске B. Переставив
при необходимости строки и столбцы, мы можем считать, что эти
ладьи расположены на одной диагонали D. Очевидно, эта диаго-
наль содержит ровно n клеток, принадлежащих доске B.
Зафиксируем k, 1?k<n/2. Возьмём произвольное k1 , 1?k1 ?
?k, и фиксируем любое расположение k1 небьющих ладей вне диа-
гонали D. Пусть эти ладьи бьют m клеток диагонали D, k1 +1?
?m?2k1 . Тогда количество расстановок k ладей, в которых вне
диагонали D стоит k1 ладей, причём в точности на выбранных
местах, равно Ck?k1 . А количество расстановок n?k ладей,
n?m
в которых вне диагонали D стоит k1 ладей, причём в точности
на выбранных местах, равно Cn?k?k1 .
n?m
Осталось заметить, что при выбранных значениях парамет-
ров k, k1 , m последний биномиальный коэффициент расположен
в (n?m)-й строке треугольника Паскаля ближе к центру, чем
предпоследний, поэтому
Cn?k?k1 ?Ck?k1 .
n?m n?m
Таким образом, количество всех расстановок n?k ладей не меньше
количества всех расстановок k ладей.
19
... ...




...




...
Рис. 8

Доказанное неравенство не следует из теоремы IV, поскольку,
как мы уже обсуждали, все корни <ладейного многочлена наоборот>
#A
n =xn R 1 !
!
x!
rn +rn?1 x+...+r0x
тоже вещественные отрицательные.
Нетрудно привести пример доски, для которой при всех k
в неравенстве 7 реализуется равенство. Действительно, равенства
будут иметь место, если в доказательстве неравенства 7 окажется
m=2k1 , т. е. если любые k1 небьющих ладей (k1 ?n/2), располо-
женных вне диагонали D, бьют ровно 2k1 клеток этой диагонали.
Примеры таких досок для чётного и нечётного n изображены
на рис. 8.
Аналогичными рассуждениями можно установить следующее
неравенство.
7. Если степень ладейного многочлена доски B равна n, то
n?k n?1
·r ?rn?k?1 , 0?k? .
k+1 k 2

ЛИТЕРАТУРА
[1] Е. Я. Г и к. Шахматы и математика. — M.: Наука, 1983. —
(Библиотечка <Квант>. Вып. 24).
[2] Р. С т е н л и. Перечислительная комбинаторика. — М.: Мир,
1990.
[3] Г. Г. Х а р д и, Д. Е. Л и т т л ь в у д, Г. П о л и а. Неравен-
ства. — М.: ИЛ, 1948.
[4] E. N. G i l b e r t. Enumeration of labelled graphs // Canad. J.
Math. V. 8. 1956. P. 405—411.
[5] J. L. G o l d m a n, J. T. J o i c h i, D. E. W h i t e. Rook theo-
ry III: rook polynomials and the chromatic structure of graphs //
Journal of Comb. Theory. Ser. B. V. 25. 1978. P. 135—142.
[6] A. N i j e n h u i s. On permanents and the zeros of rook polynomi-
als / Journal of Comb. Theory. Ser. A. V. 21. 1976. P. 240—244.
/
20

<< Пред. стр.

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

ОГЛАВЛЕНИЕ