ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5528
Скачиваний: 27
61
∑
∞
=
=
=
+
+
+
0
2
.
!
...)
!
2
!
1
1
(
r
r
r
nt
n
r
e
n
e
t
t
При дополнительном условии, что каждый элемент входит в
перестановку не менее одного раза, производящая функция примет
вид
.
)
1
(
...)
!
2
!
1
(
2
n
t
n
e
t
t
−
=
+
+
Понятия производящих функций двух видов для сочетаний и
перестановок можно уточнить с помощью следующих определений.
1.
Обычной производящей функцией для последовательно-
сти
,...
,
1
0
a
a
называется сумма
...
...
)
(
2
2
1
0
+
+
+
+
+
=
n
n
t
a
t
a
t
a
a
t
A
2.
Экспоненциальной производящей функцией для той же
последовательности называется сумма
...
!
...
!
2
)
(
2
2
1
0
+
+
+
+
+
=
n
t
a
t
a
t
a
a
t
E
n
n
.
В этих определениях элементы
,...
,
1
0
a
a
должны быть упо-
рядочены, но не обязательно различны. На переменную
t
никаких
ограничений не накладывается.
Производящие функции были введены в комбинаторный ана-
лиз в качестве средства, позволяющего с большой общностью под-
ходить к комбинаторным задачам перечисленного типа. Однако
производящие функции, построенные для разных выборок, оказа-
лись в большинстве случаев довольно громоздкими. Для более
удобной записи производящих функций имеется много средств. Это
специальные операторы (сдвига, разности, усреднения), символиче-
ские исчисления, специальные числа и специальные функции.
3.7
Комбинаторно
-
логический
аппарат
Рассмотрим некоторые логические приемы, составляющие ос-
нову многих комбинаторных доказательств
62
3.7.1
Метод
включений
и
исключений
Метод называют также методом решета, логическим методом,
принципом перекрестной классификации, символическим методом.
Пусть дано
n
-множество
S
некоторых элементов и
N
- мно-
жество свойств
N
P
P
P
,...,
,
2
1
которыми элементы множества могут
как обладать, так и не обладать. Требуется найти число элементов,
не обладающее ни одним из перечисленных свойств.
Выделим какую-либо
r
-выборку свойств
).
,...,
,
(
2
1
ir
i
i
P
P
P
Число элементов множества
S
, каждый из которых обладает всеми
выбранными свойствами, обозначим через
).
,...,
,
(
2
1
ir
i
i
P
P
P
n
От-
сутствие у элементов свойства
i
P
будем обозначать через
i
P
. Та-
ким образом
число элементов, обладающих, например, свойствами
5
3
1
,
,
P
P
P
и не обладающих свойствами
6
4
2
,
,
P
P
P
запишется как
).
,
,
,
,
,
(
6
5
4
3
2
1
P
P
P
P
P
P
n
Рассмотрим 2 простых случая:
а) имеется только
одно свойство
P
; тогда
)
(
)
(
P
n
n
P
n
−
=
,
б) имеется конечное число свойств
N
P
P
P
,...,
,
2
1
, несовмести-
мых друг с другом, тогда
∑
=
−
=
N
i
i
N
P
n
n
P
P
P
n
1
)
2
1
(
)
,...,
,
(
.
В более общей постановке вопроса элементы множества могут
обладать комбинацией совместимых свойств. В этом случае спра-
ведлива
Теорема 1.
Если даны
n
-множество элементов и
N
-множество свойств
,
,...,
2
,
1
,
N
i
P
i
=
то
63
).
...,
,
,
(
)
1
(
...
)
,
,
(
)
,
(
)
(
)
,...,
,
(
1
2
1
1
1
2
1
N
N
j
i
N
k
j
i
N
i
N
j
i
j
i
i
N
P
P
P
P
P
P
n
P
P
n
P
n
n
P
P
P
n
∑
∑
∑
≤
<
≤
=
≤
<
≤
−
+
+
−
−
+
−
=
(14)
Доказательство.
Чтобы получить элементы, не обладающие
ни одним из указанных свойств, необходимо из
n
-множества ис-
ключить элементы, обладающие свойством
1
P
, затем -
2
P
и т.д. то
есть
∑
i
i
P
n
)
(
элементов.
Однако при этом элементы, обладающие двумя свойствами,
например,
1
P
и
2
P
, оказались исключенными дважды (сначала –
как элементы, обладающие
1
P
, затем – как обладающие свойством
2
P
). Следовательно, нужно возвратить элементы, обладающие дву-
мя свойствами, т.е. добавить
∑
j
i
j
i
P
P
n
,
)
,
(
. Но при этом оказались
включенными элементы обладающие 3-мя свойствами, например,
свойствами
.
,
,
3
2
1
P
P
P
Рассуждая таким образом и далее, получим
алгоритм для вычисления
),
,...,
,
(
2
1
N
P
P
P
n
состоящий в попере-
менном отбрасывании и возвращении подмножеств. Отсюда и на-
звание метода.
Помимо этих простых рассуждений доказательство можно про-
вести индукцией по
N
. Теорема справедлива для
:
1
=
N
)
(
)
(
P
n
n
P
n
−
=
.
В соответствии с формулировкой теоремы мы можем записать
также
).
,
,
,
(
)
,...,
,
(
)
,...,
,
(
1
2
1
1
2
1
2
1
N
N
N
N
P
P
P
P
n
P
P
P
n
P
P
P
n
−
−
−
=
Пусть теорема верна для
1
−
N
свойств, т.е.
).
,...,
,
(
)
1
(
...
)
,
(
)
(
)
,...,
,
(
1
2
1
1
1
2
1
−
−
<
−
−
+
+
−
+
=
∑
∑
N
N
i
j
i
j
i
i
N
P
P
P
n
P
P
n
P
n
n
P
P
P
n
64
Перейдем к ситуации, когда имеется
N
свойств и применим
полученное соотношение для числа
:
)
,
,...,
,
(
1
2
1
N
N
P
P
P
P
n
−
).
,...,
,
(
)
1
(
...
)
,
(
)
(
)
,
,...,
,
(
2
1
1
2
1
N
N
i
N
i
N
N
N
P
P
P
n
P
P
n
P
n
P
P
P
P
n
−
+
+
+
−
=
∑
−
Вычитая это равенство из предыдущего, получим утверждение
теоремы.
Характер доказательства таков, что его можно применить для
любой комбинации свойств. В левой части доказанного равенства
может стоять, например,
).
,
,
,
(
4
3
2
1
P
P
P
P
n
При этом теорема фор-
мируется относительно совокупности свойств
2
P
и
4
P
с обязатель-
ным выполнением свойств
1
P
и
3
P
следующим образом
).
,
,
,
(
)
,
,
(
)
,
,
(
)
,
(
)
,
,
,
(
4
3
2
1
4
3
1
2
3
1
3
1
4
2
3
1
P
P
P
P
n
P
P
P
n
P
P
P
n
P
P
n
P
P
P
P
n
+
+
−
−
−
=
Дальнейшие усложнения метода связаны с введением весов
элементов. Ограничений на понятие веса никаких не вводим. Для
нас веса – это числовые характеристики элементов множеств, опре-
деляемые условиями задачи.
Пусть задано
n
-множество
S
и каждому элементу
S
S
i
∈
,
,
,...,
2
,
1
n
i
=
приписан вес
).
(Si
V
Из
N
- множества свойств
N
P
P
P
,...,
,
2
1
возьмем
r
- выборку
ir
i
P
P ,...,
1
и обозначим сумму
весов элементов, обладающих всеми выбранными свойствами, через
).
,...,
,
(
2
1
ir
i
i
P
P
P
V
А сумму весов, распространенную на все воз-
можные
r
- выборки свойств, через
∑
=
).
(
)
,...,
(
1
r
V
P
P
V
ir
i
При
0
=
r
символ
)
0
(
V
есть сумма весов всех элементов
множества
S
.
Тогда предыдущая теорема переформулируется следующим
образом.
65
Теорема 2. Если даны
n
-множество
S
, каждый элемент ко-
торого имеет вес, и
N
- множество свойств, то сумма
)
0
(
N
V
весов всех элементов, не обладающих ни одним из заданных
свойств, определяется по формуле
).
(
)
1
(
...
)
2
(
)
1
(
)
0
(
)
0
(
N
V
V
V
V
V
N
N
−
+
−
+
−
=
Теорема 2 обобщает теорему 1. Если все элементы
S
S
i
∈
имеют единичный вес, то сумма весов равна числу слагаемых в
сумме. В этом случае
N
V
=
)
0
(
, а
)
0
(
N
V
равно числу элементов
множества
S
, не обладающих ни одним из
N
свойств; при этом
получим формулу (14).
Теорема 2 в свою очередь может быть
обобщена.
Теорема 3. Сумма весов элементов, обладающих в точности
r
-свойствами из свойств
,
,...,
,
2
1
N
P
P
P
находится по формуле
),
(
)
1
(
...
)
2
(
)
1
(
)
(
)
(
2
2
1
1
N
V
C
r
V
C
r
V
C
r
V
r
V
r
N
N
r
N
r
r
N
−
−
+
+
−
+
+
−
+
+
+
−
=
или, что то же самое
).
(
)
1
(
...
)
2
(
)
1
(
)
(
)
(
2
1
N
V
C
r
V
C
r
V
C
r
V
r
V
r
N
r
N
r
r
r
r
N
−
+
+
−
+
+
−
+
+
+
−
=
Теоремы 2 и 3 доказываются аналогично теореме 1.
В качестве примера рассмотрим так называемую
задачу о бес-
порядках (задачу о встречах). Пусть имеется конечное упорядочен-
ное множество чисел
.
,...,
3
,
2
,
1
n
Для них могут быть образованы
перестановки
.
,...,
,
2
1
n
a
a
a
Число всех перестановок равно
!.
n
Сре-
ди этих перестановок есть такие, где ни один элемент не сохранил
своего первоначального места:
n
i
i
a
i
,...,
2
,
1
,
=
≠
. Такие переста-
новки называются беспорядками. Сколько существует беспорядков?
Множество
n
элементов будем рассматривать по отношению к
множеству свойств элементов оставаться на своем месте:
}.
,...,
2
,
1
\
{
~
n
i
i
a
P
i
i
=
=
Очевидно, что если
s
элементов за-