ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5525
Скачиваний: 27
66
крепляются на своих местах, то число
)
(s
N
соответствующих пе-
рестановок равно
)!
(
s
n
−
Число беспорядков тогда находится с
помощью метода включений и исключений:
),
!
)
1
(
...
!
3
1
!
2
1
1
1
(
!
...
)!
(
)
1
(
...
)!
2
(
)!
1
(
!
)
0
(
2
1
n
n
s
n
C
n
C
n
C
n
N
n
S
n
S
n
n
−
+
+
−
+
−
=
+
+
−
−
+
−
−
+
−
−
=
что является целым числом, ближайшим к
.
!
1
−
e
n
Если речь идет не о беспорядках, а о числе перестановок, в ко-
торых остаются на своих местах
s
элементов, то
).
)!
(
1
)
1
(
...
!
3
1
!
2
1
1
1
(
!
!
)
(
s
n
s
n
s
N
s
n
−
−
+
+
−
+
−
−
−
Ход рассуждений очевиден: из
n
элементов выбирают
s
не-
подвижных элементов
S
n
C
способами, а затем умножают (по прави-
лу произведения) на число беспорядков среди оставшихся
)
(
s
n
−
элементов.
3.7.2
Системы
представителей
множеств
Рассмотрим один из комбинаторных подходов к характеристи-
ке структуры конечных множеств. Основной идеей здесь является
замена системы множеств собранием их представителей.
Постановка задач такого типа и методы их решения зависят от
того, каким требованиям должны удовлетворяют эти представители.
Системы различных представителей
Пусть имеется
n
-множество
S
и множество
)
(S
P
всех его
подмножеств. Пусть
)
,...,
,
(
2
1
m
S
S
S
M
=
- некоторая
m
выборка
из
)
(S
P
, а
)
,...,
,
(
2
1
m
a
a
a
a
=
- некоторая
m
выборка из
S
.
Если выборке
M
можно сопоставить (не обязательно одно-
значно) выборку
a
такую, что элементы
,
,...,
2
,
1
,
m
i
a
i
=
попарно
различны и при этом
,
,...,
12
,
m
i
S
a
i
i
=
∈
то говорят, что элемент
i
a
представляет множество
i
S
, а вся выборка
)
,...,
,
(
2
1
m
a
a
a
на-
67
зывается системой различных представителей (СРП) для
M
. Заме-
тим, что если
j
i
≠
, то
j
i
a
a
≠
даже если
j
i
S
S
=
. Если множест-
во появляется несколько раз, то всякий раз оно должно иметь пред-
ставителя отличного от других.
Оказывается, СРП может существовать не для всяких совокуп-
ностей множеств. Если в конечной системе множества не пусты и не
пересекаются, то СРП, очевидно, существует.
Возьмем более сложный случай. Например,
),
,
,
,
,
(
e
d
c
b
a
S
=
а
M
есть совокупность 4-х множеств:
).
,
(
);
,
,
(
);
,
,
,
(
4
3
2
1
e
b
S
S
e
b
a
S
d
c
b
a
S
=
=
=
=
Существует
две СРП:
)
,
,
,
(
e
b
a
c
и
).
,
,
,
(
b
e
a
d
Но стоит изменить лишь одно
из подмножеств, например, вместо
2
S
взять
),
,
(
'
2
e
b
S
=
то мы уже
не сможем получить ни одной СРП.
На вопрос о существовании СРП для заданного семейства мно-
жеств, отвечает теорема Ф.Холла (1935 г.).
Теорема Ф.Холла. Подмножества
m
S
S
S
,...,
,
2
1
имеют СРП
тогда и только тогда, когда объединение любых
k
из этих мно-
жеств содержит не менее
k
элементов. Иначе говоря, СРП для
m
S
S
S
,...,
,
2
1
существует тогда и только тогда, когда
iK
i
i
S
S
S
∪
∪
∪
...
2
1
состоит не менее чем из
k
элементов. При
этом
)
,...,
(
,
,...,
2
,
1
1
k
i
i
a
m
k
=
- любая
k
-выборка из
.
,...,
2
,
1
m
Доказательство
: Необходимость почти очевидна, т.к. суще-
ствование СРП обеспечивает необходимое количество элементов в
качестве различных представителей.
Для доказательства достаточности приведем другую формули-
ровку, дающую также нижнюю грань для числа самих СРП.
Теорема.
Пусть семейство
)
,...,
,
(
2
1
m
S
S
S
M
=
удовлетво-
ряет необходимому условию существования СРП и пусть каждое
из множеств состоит не менее чем из
t
элементов. Тогда:
а) если
,
m
t
≤
то
M
имеет не менее чем
!
t
СРП;
68
б) если
,
m
t
>
то
M
имеет не менее чем
)!
(
!
m
t
t
−
СРП.
Доказательство проведем по индукции относительно
m
. Для
1
=
m
(и даже для
2
=
m
) теорема очевидна. Докажем, что она
верна и для любого конечного
m
, исходя из ее справедливости для
.
m
m
<
′
Рассмотрим объединение некоторой
k
-выборки множеств:
iK
i
i
S
S
S
∪
∪
∪
...
2
1
Возможны два случая:
-
число элементов в объединении =
k
;
-
число элементов >
k
.
Начнем со второго
случая
. Здесь рассматриваемое объедине-
ние содержит не менее
1
+
k
элементов, каковы бы ни были
k
:
,
,...,
2
,
1
m
k
=
и набор
k
i
i
i
,...,
,
2
1
из чисел
.
,...,
2
,
1
m
Выберем какой-либо
из элементов
1
1
S
a
∈
и удалим его из
,
,...,
,
3
2
m
S
S
S
если он там встречается. Придем таким образом к
).
,...,
,
(
*
*
*
3
*
2
m
S
S
S
M
=
Эта
−
− )
1
(m
выборка удовлетворяет не-
обходимому условию существования СРП, т.к.
*
*
2
*
1
...
ik
i
i
S
S
S
∪
∪
∪
содержит не менее
k
элементов и, кроме того,
*
M
имеет не менее
)!
1
(
−
t
СРП, если
m
t
≤
(и значит,
1
1
−
≤
−
m
t
), либо не менее
)!
/(
)!
1
(
m
t
t
−
−
СРП, если
m
t
>
(и значит,
).
1
1
−
>
−
m
t
Иско-
мый результат достигается, если учесть, что в
1
S
имеется по мень-
шей мере
t
возможностей фиксировать элемент
1
a
и что этот эле-
мент вместе с СРП для
*
M
составляет СРП для
M
.
Теперь вернемся к первому случаю. Здесь проведенное дока-
зательство применить нельзя, т.к. существует некоторая
k
-выборка
ik
i
i
S
S
S
,...,
,
2
1
такая, что
ik
i
i
S
S
S
∪
∪
∪
...
2
1
содержит точно
k
элементов
).
1
1
(
−
≤
≤
m
k
Перенумеруем множества
m
S
S ,...,
1
следующим образом
69
.
...,
,
,
...,
...,
,
,
,
1
2
,
2
1
1
m
k
k
ik
i
i
S
S
S
S
S
S
S
S
+
↓
↓
↓
Поскольку
k
S
S
S
∪
∪
∪
...
2
1
содержит точно
k
элементов,
то
.
k
t
≤
Следовательно,
по
предположению
индукции
)
,...,
,
(
2
1
k
S
S
S
имеет не менее чем
!
t
СРП.
Рассмотрим одну из этих СРП:
)
,...,
,
(
2
1
k
a
a
a
, где
.
,...,
2
,
1
,
k
i
S
a
i
i
=
∈
Удалим
элементы
n
a
a ,...,
1
из
,
,...,
1
k
k
S
S
+
если они там встретятся. Получившаяся
)
(
k
m
−
-
выборка
)
,...,
(
*
*
*
1
m
k
S
S
M
+
=
удовлетворяет необходимому усло-
вию существования СРП.
Действительно, если это не так и если объединение какой-либо
k
*-выборки
*
*
1
*
...
k
k
k
S
S
+
+
∪
имеет меньше
k
* элементов, то объе-
динение
*
2
1
...
...
k
k
k
S
S
S
S
+
∪
∪
∪
∪
∪
имело бы менее чем
k
+
k
* элементов, что противоречит усло-
вию теоремы. Таким образом
*
M
имеет хотя бы одну СРП и, сле-
довательно,
M
имеет не меньше чем
!
t
СРП.
Алгоритм выбора СРП.
На практике бывает трудно прове-
рить, выполняются ли в конкретном случае условия теоремы Холла.
Кроме того, приведенное доказательство не дает указаний, как найти
СРП. (Это характерно, так как теоремы существования обычно и
появляются там, где трудно найти алгоритм решения).
Алгоритм, который позволяет для данного конечного набора
множеств подобрать СРП или показать что ее не существует, привел
М.Холл в качестве доказательства теоремы Ф.Холла о различных
представителях.
Пусть задано
n
множеств:
.
,...,
,
2
1
n
S
S
S
Требуется найти для
них СРП или показать, что такой системы не существует. Произ-
вольным образом выберем элемент первого множества
1
1
S
a
∈
в
качестве его представителя. Поочередно будем выбирать
70
,...,
,
3
3
2
2
S
a
S
a
∈
∈
заботясь только о том, чтобы они были раз-
личными. Если доведем процесс до
n
n
S
a
∈
включительно, то по-
лучим искомую СРП.
Возможно, что на
r
-м шаге мы дойдем до некоторого
t
-
множества
r
S
, все элементы которого
t
b
b
b
,...,
,
2
1
уже выбраны
представителями других множеств. Но это еще не означает, что СРП
не существует. Будем брать поочередно все те множества, предста-
вителями которых являются
t
b
b
b
,...,
,
2
1
, удалять из них все эле-
менты этой последовательности, а оставшиеся приписывать в ее
конец. Так будем поступать до тех пор, пока не случится одно из
двух:
1)
мы достигнем элемента
i
b
, который не может служить
представителем;
2)
последовательность
исчерпывается
элементами
s
b
b
b
,...,
,
2
1
как представителями множеств.
В случае 2) СРП не существует. В самом деле, элементы
s
b
b
b
,...,
,
2
1
являются представителями
s
множеств и по построе-
нию каждый элемент этих
s
множеств содержится в данной после-
довательности. Но тогда эти
s
множеств, а также множество
r
S
образуют
1
+
s
множеств, которые содержат только
s
различных
элементов, что противоречит условию теоремы.
Если же имеет место 1) то на некотором этапе мы находим
элемент
),
(
1
1
1
t
i
S
b
b
j
i
i
>
∈
=
не являющийся до сих пор предста-
вителем. Это означает, что представителем
1
j
S
уже был выбран
другой элемент
).
(
1
2
2
i
i
b
i
<
Если
t
i
>
2
, то значит
,
2
2
j
i
S
b
∈
представителем которого уже выбран
)
(
2
3
3
i
i
b
i
<
и т.д. Таким об-
разом, возникает последовательность
,
,
,...,
2
1
im
i
i
b
b
b
индексы которой
убывают
)
(
t
i
m
≤
, причем в этой последовательности каждый ее
член входит в множество, представителем которого является сле-
дующий член. Заменяем представителей, выбирая элементы:
1
i
b
для