Учебное пособие: Дискретная мат-ка_УП
76
Производная
первого
порядка
i
x
f
∂
∂
от
булевой
функции
f
по
переменной
x
i
(
)
(
)
n
i
n
i
i
x
x
x
x
f
x
x
x
x
f
x
f
,...,
0
,
,...,
,
,...,
1
,
,...,
,
1
2
1
1
2
1
−
−
⊕
=
∂
∂
,
где f (x
1
, x
2
, …, x
i–
1
, 1, …, x
n
) – единичная остаточная функция;
f (x
1
, x
2
, …, x
i–
1
, 0, …, x
n
) – нулевая остаточная функция;
⊕ – сло-
жение по модулю два.
В общем случае:
(
)
,
...
...
,...,
,
,
,
,
,
3
;
,
2
12
1
2
1
∑
∑
∑
≠
≠
≠
≠
∂
∂
∂
∂
⊕
⊕
∂
∂
∂
∂
⊕
∂
∂
∂
⊕
∂
∂
=
∂
∂
s
j
s
i
j
i
s
j
i
i
i
i
k
s
j
i
i
j
i
j
i
j
i
i
i
i
i
k
k
k
x
x
x
f
x
x
x
f
x
x
f
x
f
x
x
x
f
i, j, s, …= i
1
,i
2
, …,i
k
.
77
7
КОМБИНАТОРИКА
Введение
Комбинаторика является разделом дискретной математики,
в котором рассматриваются исследование дискретных конечных
математических структур. Задачи обычно оцениваются с точки
зрения
размера
, то есть общего количества различных вариантов,
среди которых нужно найти решение, а алгоритмы оцениваются с
точки зрения
сложности
. При этом различают
сложность
по
времени
(или
временную
сложность
), то есть количество необхо-
димых шагов алгоритма, и
сложность
по
памяти
(или
емкост
-
ную
сложность
), то есть объем памяти, необходимый для работы
алгоритма.
Во многих случаях возникает необходимость подсчитать
количество возможных комбинаций объектов, удовлетворяющих
определенным условиям. Такие задачи называют
комбинатор
-
ными
. Разнообразие комбинаторных задач не поддается исчерпы-
вающему описанию, но среди них есть целый ряд особенно часто
встречающихся, для которых известны способы подсчета.
Прежде всего, необходимо ввести понятие факториала, оп-
ределенного на множестве целых положительных чисел.
n!=1
⋅2⋅3⋅ … (n–1) ⋅n=n⋅(n–1) ⋅… 2⋅1
или зададим рекурсивно:
⎪
⎩
⎪
⎨
⎧
−
⋅
=
=
=
).
1
(
)
(
,
1
)
1
(
,
1
)
0
(
x
f
x
x
f
f
f
Для формулировки и решения комбинаторных задач исполь-
зуются различные модели
комбинаторных конфигураций
. Рас-
смотрим следующие две наиболее популярные.
1.
Дано
n
предметов. Их нужно разместить по
m
ящикам так,
чтобы выполнялись заданные ограничения. Сколькими способа-
ми это можно сделать?
2.
Рассмотрим множество функций
F
:
X
→
Y
, где
⎟X⎟
=
n
,
⎟Y⎟
=
m
,
X
={1,2, …,
n
}
Не ограничивая общности, можно считать, что
78
Y
={1,2, …,
m
},
F
= <
F
(1),
F
(2), …,
F
(
n
)>, 1
≤
F
(
i
)
≤
m.
Сколько существует функций
F
, удовлетворяющим задан-
ным ограничениям?
Размещения
Число всех функций (при отсутствии ограничений), или
число всех возможных способов разместить
n
предметов по
m
ящикам, называется
числом размещений
и обозначается
U
(
m
,
n
)
U
(
m
,
n
) =
m
n
.
Размещения без повторений
Число инъективных функций, или число всех возможных
способов разместить
n
предметов по
m
ящикам, не более чем по
одному в ящик, называется
числом размещений без повторений
и
обозначается
A
(
m
,
n
) или [
m
]
n
, или (
m
)
n
.
)!
(
!
)
,
(
n
m
m
n
m
A
−
=
Перестановки
Число
взаимнооднозначных
функций
,
или
число перестано-
вок n
предметов
,
обозначается
P(n).
P(n) = n!
Сочетания
Число
строго
монотонных
функций
,
или
число
размещений
n
неразличимых
предметов
по
m
ящикам
,
не
более
чем
по
одному
в
ящик
,
то
есть
число
способов
выбрать
из
m
ящиков
n
ящиков
с
предметами
,
называется
числом сочетаний
и
обозначается
C(m,
n)
или
n
m
C
или
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
m
n
)!
(
!
!
)
,
(
n
m
n
m
n
m
C
−
=
.
79
Сочетания с повторениями
Число
монотонных
функций
,
или
число
размещений
n
не
-
различимых
предметов
по
n
ящикам
,
называется
числом сочета-
ний с повторениями
и
обозначается
V(m, n).
V(m, n)= C(n + m – 1, n).
Подстановки
Подстановки
и
перестановки
являются
равнообъемными
по
-
нятиями
.
Для
вычисления
перестановок
установлена
очень
про
-
стая
формула
: P(n) = n!
При
решении
практических
задач
не
сле
-
дует
забывать
,
что
факториал
–
это
очень
быстро
растущая
функ
-
ция
,
в
частности
,
факториал
растет
быстрее
экспоненты
.
Дейст
-
вительно
,
используя
известную
формулу Стирлинга
n
n
e
n
n
n
−
≈
π
2
!
,
или
более
точно
)
12
/(
1
2
!
2
n
n
n
n
n
e
n
n
n
e
n
n
+
−
−
<
<
π
π
,
нетрудно
показать
,
что
+∞
=
+∞
→
n
n
n
2
!
lim
.
Группа подстановок
Взаимнооднозначная
функция
f: X
→ X
называется
подста-
новкой
на
X.
Замечание
.
Если
множество
X
конечно
(
|X|=n),
то
,
не
огра
-
ничивая
общности
,
можно
считать
,
что
X=1.. n.
В
этом
случае
подстановку
f: 1.. n
→ 1.. n
удобно
задавать
таблицей
из
двух
строк
.
В
первой
строке
–
значения
аргументов
,
во
второй
–
соот
-
ветствующие
значения
функции
.
Пример
3
4
1
2
5
5
4
3
2
1
=
f
,
5
3
2
1
4
5
4
3
2
1
=
g
.
80
Произведением
подстановок
f
и
g
называется
их
суперпози
-
ция
f
◦
g.
Пример
2
3
4
1
5
5
4
3
2
1
=
g
f
.
Тождественная
подстановка
–
это
подстановка
e
такая
,
что
e(x)= x.
Пример
5
4
3
2
1
5
4
3
2
1
=
e
.
Обратная подстановка –
это
обратная
функция
,
которая
всегда
существует
,
поскольку
подстановка
является
биекцией
.
Таблицу
обратной
подстановки
можно
получить
,
если
просто
по
-
менять
местами
строки
таблицы
исходной
подстановки
.
Пример
3
4
1
2
5
5
4
3
2
1
=
f
,
1
4
5
2
3
5
4
3
2
1
5
4
3
2
1
3
4
1
2
5
1
=
=
−
f
.
Таким
образом
,
множество
подстановок
образует
группу
относительно
операции
суперпозиции
.
Эта
группа
называется
симметрической
степени
n.
Циклы
Цикл –
это
такая
последовательность
элементов
x
0
, x
1
, …, x
k
такая
,
что
⎩
⎨
⎧
=
≤
≤
=
+
.
,
,
,
)
(
0
1
k
i
x
k
i
o
x
x
f
i
i
Цикл
длины
2
называется
транспозицией.