ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 8771
Скачиваний: 13
16
Например
,
полукольцо
всех
целых
неотрицательных
чисел
относительно
обычных
операций
сложения
и
умножения
превра
-
щается
в
В
{0,1}
при
наложении
дополнительного
условия
2=1.
1.2
Простейшие
задачи
перечисления
Пусть
имеется
n-
множество
А
.
Некоторая
совокупность
r
элементов
этого
множества
(
а
1
,
а
2
,...,
а
r
),
где
а
i
∈
A, i=1,2,...,r; r
≤
n,
называется
r-
выборкой
.
В
r-
выборках
в
зависимости
от
условий
задачи
,
либо
учитывают
порядок
следования
элементов
,
либо
не
учитывают
.
Упорядоченные
r-
выборки
из
n-
множества
А
называются
r-
перестановками
,
если
все
r
элементов
различны
,
и
r-
переста
-
новками
с
повторениями
,
если
среди
r
элементов
имеются
одина
-
ковые
.
Неупорядоченные
r-
выборки
из
n-
множества
А
называются
r-
сочетаниями
,
если
все
r
элементов
различны
,
и
r-
сочетаниями
с
повторениями
при
наличии
одинаковых
элементов
.
Например
, 6-
выборки
(2,3,4,6,1,1), (1,3,4,1,6,2)
представляют
собой
равные
6-
сочетания
с
повторениями
и
различные
6-
перестановки
с
повто
-
рениями
из
множества
{1,2,3,4, 5,6}.
Число
всех
возможных
r-
перестановок
(
отображений
α
множества
А
на
себя
)
из
n-
множества
обозначим
через
Р
(n,r).
Ве
-
личина
Р
(n,r)
определяется
посредством
последовательного
при
-
менения
правила
произведения
.
Р
(r,n) = n(n–1)...(n–r+1),
откуда
следует
Р
(r,n) = n!.
Применяется
также
Р
(n,0) = 0! = 1.
Число
Р
возможных
r-
перестановок
с
повторениями
опреде
-
ляется
из
условия
,
что
после
выбора
элемента
r-
перестановки
ос
-
таются
все
те
же
n
возможностей
для
выбора
следующего
эле
-
мента
.
Следовательно
,
число
r-
перестановок
с
повторениями
рав
-
но
:
р
=n
r
.
Перестановка
может
рассматриваться
с
двух
позиций
:
а
)
как
упорядоченная
совокупность
элементов
данного
множества
или
б
)
как
нарушение
естественного
порядка
.
Случай
а
)
приводит
к
17
рассмотренным
выше
r-
перестановкам
, r
≤
n.
Случай
б
)
приводит
к
n-
перестановками
.
Например
,
перестановка
Р
= (4 3 7 5 6 9 2 8 1 12 11 10)
явля
-
ется
нарушением
естественного
порядка
первых
12
чисел
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
=
⋅
10
11
12
1
8
2
9
6
5
7
3
4
12
11
10
9
8
7
6
5
4
3
2
1
P
Учитывая переход элемента 1 в 4, 2 в 3, и т.д. перестановка
может быть записана иначе:
Р = (1 4 5 6 9) (2 3 7) (10 12) (8) (11), (*)
где каждая скобка есть перестановка, действующая только на
элементы, заключенные в данной скобке, и не затрагивающая
элементы, не заключенные в ней.
Представление перестановки в виде (*) называется разложе-
нием на циклы.
Представим перестановку в виде (к
1
,к
2
,к
3
,...,к
n
) или символи-
чески 1
к1
,2
к2
,3
к3
,...,n
кn
,
∑
=
=
n
i
i
n
Ik
1
, где k
i
число циклов, содержащих
i элементов. (**)
Теорема. Число перестановок типа (**) равно
(
)
!
*
!*...
*
2
!*
*
1
!
,...,
,
,
2
2
1
1
3
2
1
n
KN
K
K
n
K
n
K
K
n
K
K
K
K
P
=
.
Доказательство. Среди всех n! перестановок из n элемен-
тов тождественные перестановке: 1
к1
2
к2
3
к3
... n
kn
. Перестановки
считаются тождественными, если они содержат все циклы, со-
держащие одни и те же элементы в любом циклическом порядке.
Число перестановок циклов равно 1
к1
2
к2
3
к3
... n
kn
. Далее,
поскольку в каждом цикле К
i
имеет место К
i
! перестановок, то-
гда общее число перестановок по правилам произведения соста-
вит 1
к1
К
1
! 2
к2
К
2
!... n
kn
K
n
!
Подсчитаем теперь число r-сочетаний С(n,r) или просто (
n
r
).
Начнем со случая, когда все элементы в r-сочетаниях различны.
Легко видеть, что число r-сочетаний из n-множества в r! раз
меньше, чем число r-перестановок из элементов того же множе-
ства. Следовательно:
18
( )
)!
(
*
)!
(
!
!
!
)
1
)...(
1
(
!
)
,
(
r
n
r
n
r
n
r
r
n
n
n
r
r
n
P
n
r
−
−
=
+
−
−
=
=
Отсюда следует, что (
n
r
) = (
n
n–2
)r! .
Величину С(n,r) принято называть биномиальным коэффици-
ентом. Действительно, в произведении (x+y)
n
= (x+y)*(x+y) коэф-
фициент при члене x
r
y
n–r
− это не что иное, как число способов вы-
бора r множителей x+y, из которых берется х, при этом из остав-
шихся n–r множителей x+y берется y. Из соотношения
∑
=
=
+
n
r
r
n
r
n
x
x
0
)
(
)
1
(
(***)
могут быть получены ряд тождеств, включающих биномиальные
коэффициенты:
1)
∑
=
m
k 0
(
n
r
) = 2
n
;
2)
∑
=
n
r 0
(
−1)
r
(
n
r
) = 0;
3)
∑
=
n
r 1
r (
−1)
r
(
n
r
) = 0;
4)
∑
=
n
k
r
(–1)
r
(
r
k
) (
n
k
) = 0, n
≥ k.
Для получения соотношений (1) и (2) необходимо положить
х = 1, х =
−1 соответственно; для получения (3) продифференци-
руем (***) по х и затем возьмем х =
− 1; для получения (4) про-
дифференцируем к раз по х, разделим на к! и положим х =
− 1.
Заметим, что r-сочетания из n-множества являются его r-
подмножествами. Возникает задача о числе (r
1
,r
2
,...,r
k
)-разбиений
множества S, т.е. разбиений вида
S = T
1
∪T
2
∪...∪T
k
, T
i
∩T
j
=
∅, i≠j.
Очевидно,
∑
=
k
i 1
r
i
= n.
Для выбора r
1
-подмножества Т
1
из S имеется (
n
r
) возможно-
стей; после этого r
2
-подмножество Т
2
можно выбрать только из
остальных n-r
1
элементов, следовательно, имеется (
n–r
r2
) способов
19
для выбора Т
2
; r
k
-подмножество Т
k
можно выбрать (n –
∑
=
n
i 1
r
i
) спо-
собами.
Применяя обобщенное правило произведения, получим, что
искомое число (r
1
,r
2
,...,r
k
)-разбиений n-множества S равно (с уче-
том выражения для С(n,r))
!
!...
!
!
)
)...(
)(
(
2
1
1
2
1
k
r
n
r
r
n
r
n
r
r
r
r
n
R
i
k
=
∑
=
−
−
и
называется
полиномиальным
коэффициентом
.
Подсчитаем
,
наконец
,
число
r-
сочетаний
с
повторениями
из
n-
множества
S
и
обозначим
его
через
f(n,r).
Зафиксируем
в
S
не
-
который
элемент
,
тогда
каждое
r-
сочетание
либо
содержит
этот
элемент
,
либо
нет
.
Если
имеет
место
первый
случай
,
то
остальные
r
−1
элементов
этого
r-
сочетания
(
а
значит
r-
сочетаний
,
содержа
-
щих
фиксированный
элемент
)
можно
выбрать
f(n,r–1)
способами
.
Если
имеет
место
второй
случай
,
то
r-
сочетание
выбирается
из
n-
1
элементов
,
и
тогда
число
таких
r-
сочетаний
равно
f(n–1,r).
Используя
правило
суммы
,
получим
f(n,r) = f(n,r–1) + f(n–1,r).
Очевидно
,
что
f(n,1) = n
и
f(1,r) = 1,
тогда
f(n,0) = f(n,1) –
−f(n–1,1) = n–(n–1) = 1.
Теперь
последовательно
получаем
:
f(n,2) = f(n,1) + f(n–1,2) = f(n,1) + f(n–1,1) + f(n–2,2) =... =
= n +(n–1) + (n–2) +... + 1 = (n(n+1))/2 = (
n+1
2
).
F(n,3) = f(n,2) +
а
(n–1,2) +... + f(1,3) = (
n+2
2
) + (
n
2
) +... +1 = (
n+2
3
)
и
т
.
д
.
Легко
убедиться
,
что
f(n,r) = (
n+r–1
r
).
Например
,
10
3
2
1
2
1
5
4
3
2
1
!
3
!
2
!
5
)!
1
(
!
)!
1
(
)
2
,
4
(
=
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
=
=
+
−
−
+
=
r
n
r
r
n
f
.
1.3
Метод
производящих
функций
В
комбинаторном
анализе
большое
место
занимают
задачи
по
определению
количества
решений
.
Ниже
мы
рассмотрим
ме
-
тод
,
с
помощью
которого
подсчитывают
количество
решений
в
20
комбинаторных
задачах
.
Этот
метод
,
получивший
название
мето
-
да
производящих
функций
,
является
одним
из
самых
развитых
теоретически
методов
комбинаторного
анализа
и
одним
из
самых
сильных
приложений
.
Главные
идеи
этого
метода
были
впервые
высказаны
в
конце
18
века
в
работах
Лапласа
.
Пусть
дана
некоторая
последовательность
чисел
а
0
,
а
1
,...,
а
n
,
образуем
степенной
ряд
а
0
+
а
1
х
+... +
а
n
x
n
+...
Если
этот
ряд
сходится
в
какой
-
то
области
к
функции
f(x),
то
эту
функцию
называют
производящей
для
последовательности
чисел
а
0
,
а
1
,...,
а
n
...
Например
,
из
формулы
x
−
1
1
= 1 + x +... + x
n
+... вытекает,
что функция
x
−
1
1
является производящей для последовательно-
сти чисел 1,1,1,.... Интервал сходимости
1
<
x
. Для последова-
тельности 1,2,3,4,...,n,... производящей является функция
2
)
1
(
1
x
−
=
=1 + 2x + 3x
2
+... +(n+1)x
n
+...
Нас будут интересовать производящие функции для после-
довательностей а
0
,а
1
,...,а
n
..., связанных с комбинаторными зада-
чами. С помощью этих функций удается получать самые разные
свойства этих последовательностей. Кроме того, мы рассмотрим,
как связаны производящие функции с решением рекуррентных
соотношений.
Виды производящих функций и действия над ними
В комбинаторном анализе чаще всего используют три вида
производящих функций: обычные, экспоненциальные и функции
Дирихле.
Обычные производящие функции для последовательности
а = (а
1
,а
2
,...,а
n
) в общем виде могут быть записаны в следующем
виде:
f
a
(t) =
∑
=0
n
a
n
t
n
.