ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5530
Скачиваний: 27
51
такой выбор сделан, остаются
)
1
(
−
n
возможностей для выбора
второго элемента, затем
)
2
(
−
n
возможностей для выбора третьего
и т.д. Для выбора
r
-го элемента будет
)
1
(
+
− r
n
возможностей.
Применяя правило произведения, получим
).
1
)...(
1
(
)
,
(
+
−
−
=
=
r
n
n
n
r
n
P
Отсюда, в частности, следует, что
!
)
,
(
n
n
n
P
=
, т.е.
n
различ-
ных предметов, расположенных в
n
различных местах, можно
представить
n
! способами. Для полноты результата полагают
1
!
0
)
0
,
(
=
=
n
P
Подсчитаем теперь число
P
возможных
r
-перестановок с
повторениями. В этом случае после выбора любого элемента
r
-
перестановки остаются все те же
n
возможностей для выбора сле-
дующего элемента. Таким образом, число
r
-перестановок с повто-
рениями из
n
-множества равно
.
r
n
P
=
Приведенные рассуждения хорошо иллюстрируются урновой
схемой широко используемой в теории вероятностей: из урны, в
которую помещены
n
шаров, поочередно вынимают
r
шаров, при
этом вынутый шар либо возвращают (выбор с возвращениями), либо
не возвращают (выбор без возвращений).
Определим число
)
,
(
r
n
C
r
-сочетаний (без повторений).
Так как
r
-сочетания - это неупорядоченные
r
-выборки, а число
способов упорядочения
r
-выборки равно
r
!, то
)
,
(
r
n
C
будет в
r
! раз меньше, чем число
r
-перестановок из элементов
n
-множества. Следовательно,
)!
(
!
!
!
)
1
)...(
1
(
!
)
,
(
)
,
(
r
n
r
n
r
r
n
n
n
r
r
n
P
r
n
C
−
=
+
−
−
=
=
Отсюда следует, что
.
1
)
0
,
(
)
,
(
),
,
(
)
,
(
=
=
=
−
n
C
n
n
C
r
n
C
r
n
n
C
Найдем число
)
,
(
r
n
H
r
- сочетаний с повторениями. Что-
бы глубже понять специфику комбинаторных рассуждений, рас-
52
смотрим три способа определения этого числа.
1.
Пусть множество
S
находится во взаимно однозначном
соответствии с множеством первых
n
натуральных чисел. Тогда
вместо
r
-выборок из
S
можно рассматривать соответствующие им
r
- выборки из
}.
,...,
2
,
1
{
n
T
=
Любая
r
-выборка с повторениями
из
T
может быть представлена как
),
,...,
,
(
2
1
r
a
a
a
a
=
где
.
...
2
1
r
a
a
a
≤
≤
≤
Поставим ей в соответствие выборку
),
1
,...,
1
,
0
(
2
1
−
+
+
+
=
′
r
a
a
a
a
r
в которой все элементы различ-
ны. Так как число всех возможных выборок типа
a
из множества
T
равно числу всех возможных выборок типа
a′
из множества
},
1
,...,
1
,
,...,
2
,
1
{
−
+
+
=
′
r
n
n
n
T
то
искомое
число
).
,
1
(
)
,
(
r
r
n
C
r
n
H
−
+
=
2.
К
r
-сочетанию с повторениями из множества
S
припи-
шем все элементы множества
S
и полученные
r
n
+
элементов
разделим
)
1
(
−
n
черточкой, так как промежутков между
n
различ-
ными элементами имеется
1
−
n
. Таким образом, задача сводится к
отысканию числа способов, которыми можно расположить
)
1
(
−
n
черточку в
)
1
(
−
+ r
n
промежутке между
r
n
+
элементами. Это
число
равно
)
,
1
(
)
1
,
1
(
r
r
n
C
n
r
n
C
−
+
=
−
−
+
,
откуда
).
,
1
(
)
,
(
r
r
n
C
r
n
H
−
+
=
3.
Получим реккурентную последовательность для
)
,
( r
n
H
.
Очевидно, что
.
1
)
,
1
(
,
)
1
,
(
=
=
r
H
n
n
H
Зафиксируем в множестве
S
некоторый элемент. Тогда каж-
дое
r
-сочетание либо содержит этот элемент, либо нет. В первом
случае остальные
)
1
(
−
r
элементы этого
r
-сочетания можно вы-
брать
)
1
,
(
−
r
n
H
способами. Во втором случае
r
-сочетания выби-
раются из
)
1
(
−
n
элемента, поэтому число таких сочетаний равно
).
,
1
(
r
n
H
−
Используя правило суммы, получим
).
,
1
(
)
1
,
(
)
,
(
r
n
H
r
n
H
r
n
H
−
+
−
=
Теперь последовательно находим
53
),
2
,
1
(
2
)
1
(
1
...
)
2
(
)
1
(
)
2
,
2
(
)
1
,
1
(
)
1
,
(
)
2
,
1
(
)
1
,
(
)
2
,
(
+
=
=
+
=
+
+
−
+
−
+
=
−
+
+
−
+
=
−
+
=
n
C
n
n
n
n
n
n
H
n
H
n
H
n
H
n
H
n
H
)
3
,
2
(
3
2
)
1
)(
2
(
1
...
2
)
1
(
2
)
1
(
1
...
)
2
,
(
)
2
,
1
(
)
3
,
1
(
...
)
2
,
2
(
)
2
,
1
(
)
2
,
(
)
3
,
2
(
)
2
,
1
(
)
2
,
(
)
3
,
1
(
)
2
,
(
)
3
,
(
+
=
⋅
+
+
=
+
+
−
+
+
+
=
+
+
+
+
=
+
+
−
+
−
+
=
−
+
+
−
+
=
−
+
=
n
C
n
n
n
n
n
n
n
n
C
n
C
H
n
H
n
H
n
H
n
H
n
H
n
H
n
H
n
H
n
H
Легко убедиться, что
).
,
1
(
)
,
(
r
r
n
C
r
n
H
−
+
=
3.4.
Разложение
на
циклы
Рассмотрим еще одно понятие, связанное с операцией упорядо-
чения – перестановку. Она может рассматриваться с двух позиций:
1)
как упорядоченная совокупность элементов данного мно-
жества;
2)
как нарушение стандартного порядка, называемого обычно
естественным (например, алфавитным или цифровым).
Первый случай приводит к уже рассмотренным
r
-
перестановкам, где
.
n
r
≤
Второй случай приводит к
n
-перестановкам, называемым
просто перестановками или подстановками.
Пусть, например, имеется перестановка
P
= (4 3 7 5 6 9 2 8 1 12 11 10),
являющаяся нарушением естественного порядка первых две-
надцати чисел натурального ряда. Эта запись показывает, что при
перестановке
P
элемент 1 перешел в 4, 2 – в 3, 3 – в 7 и т.д. Пере-
становку
P
можно записать иначе:
P
= (1 4 5 6 9) (2 3 7) (10 12) (8) (11),
(11)
54
где каждая скобка есть перестановка, действующая только на
элементы, заключенные в ней.
Представление перестановки в виде (11) называется разло-
жением на циклы. Любая перестановка может быть разложена на
циклы.
Если циклические перестановки внутри циклов считать
тождественными, как например, (2 3 7) (3 7 2) (7 2 3), то разложе-
ние будет единственным.
Пусть некоторая перестановка содержит
1
K
циклов, состоя-
щих из одного элемента, или 1-циклов, затем
2
K
2-циклов,
3
K
3-
циклов и т.д. Тогда она может быть записана как
)
,...,
,
(
2
1
n
K
K
K
-
перестановка, или
.
...
3
2
1
3
2
1
r
K
K
K
K
r
⋅
⋅
(12)
Очевидно, что
∑
=
=
⋅
r
i
i
n
k
i
1
.
Теорема. Число перестановок вида (12) равно
.
!
!...
2
!
1
!
)
,...,
,
(
2
1
2
1
2
1
r
K
K
K
r
K
r
K
K
n
K
K
K
P
r
⋅
=
Доказательство. Среди всех возможных
!
n
перестановок из
n
элементов имеются тождественные перестановки типа (12).
При этом возможны две ситуации:
1)
перестановки содержат все циклы с одними и теми же
элементами в одном и том же циклическом порядке;
2)
перестановки отличаются лишь относительным располо-
жением циклов, что несущественно.
Так как
r
-цикл может начинаться с любого из
r
элементов, то
можно получить
r
дубликатов цикла, соответствующего первой
ситуации. Общее число дубликатов составит
.
...
3
2
1
3
2
1
r
K
K
K
K
r
⋅
⋅
Далее, если число
r
-циклов равно
r
K
, то их можно предста-
вить
r
K
! способами, поэтому дубликатов, соответствующих второй
ситуации, окажется
55
!
!...
!
2
1
r
K
K
K
Следовательно,
r
K
K
K
r
K
r
K
K
n
K
K
K
P
r
!...
2
!
1
!
)
,...,
,
(
2
1
2
1
2
1
=
.
3.5.
Размещения
и
заполнения
Во многих задачах требуется некоторую совокупность элемен-
тов (зерен, болтов и т.д.) распределить на некоторое множество яче-
ек (коробок, ящиков и т.п.). Фактически это задачи о разбиении не-
которой совокупности элементов на множество классов. Оба поня-
тия (размещение и заполнение) используются для обозначения как
операций, так и их результата – полученной ситуации.
Задачи этого класса существуют с давних пор и имеют разрабо-
танную методику решения. Постановки их различны: разбиения
множеств, рассечения графов, группировки станков и т.д.
Задачей на размещение будем называть задачу о числе раз-
мещений элементов по ячейкам.
Задачей на заполнение будем называть задачу на размещение,
в которой существенны число элементов либо порядок их в задан-
ных или произвольно выбранных ячейках.
Для подсчета числа размещений важно знать, являются ли эле-
менты данного множества и ячейки различными. В соответствии с
этим признаком выделяют четыре класса задач.
1.
Элементы множества и ячейки различимы между собой.
2.
Элементы множества неразличимы, ячейки различимы.
3.
Элементы множества различимы, ячейки неразличимы.
4.
Как элементы множества, так и ячейки неразличимы между
собой.
Внутри каждого из этих классов задачи могут различаться ви-
дом отображений, задаваемых конкретными условиями. Рассмотрим
задачи, относящиеся к первым двум классам.
Число способов размещения
n
различных объектов по
различным ячейкам. Эквивалентами являются: образование слов
длины
r
из алфавита, содержащего
n
букв; последовательный вы-
бор
r
шаров с немедленным из возвращением; образование
r
- пе-
рестановок с повторениями из
n
элементов. Очевидно, что число