ВУЗ:
Составители:
Рубрика:
8
КОМБИНАТОРИКА
1.
ЗАДАЧИ
КОМБИНАТОРИКИ
Комбинаторика
решает
для
конечных
множеств
задачи
следующего
типа
:
а
)
выяснить
,
сколько
существует
элементов
,
обладающих
заданным
свойством
;
б
)
составить
алгоритм
,
перечисляющий
все
элементы
с
заданным
свойством
;
в
)
отобрать
наилучший
по
некоторому
признаку
среди
перечисленных
элементов
.
Мы
будем
заниматься
только
задачами
первого
типа
.
При
этом
будет
идти
речь
об
отборе
m
элементов
с
заданным
свойством
из
конечного
множества
X
,
состоящего
из
n
элементов
.
Результат
такого
отбора
будем
называть
выборкой
.
Нас
будет
интересовать
вопрос
о
количестве
выборок
заданного
типа
.
2.
ТИПЫ
ВЫБОРОК
Выборки
делятся
на
типы
по
двум
признакам
:
а
)
важен
ли
порядок
отбора
элементов
;
б
)
есть
ли
среди
отобранных
элементов
одинаковые
.
Будем
обозначать
n
−
количество
элементов
в
исходном
множестве
X
,
m
−
количество
элементов
в
выборке
.
Упорядоченный
набор
элементов
,
среди
которых
нет
повторяющихся
,
называется
размещением
из
n
элементов
по
m
.
Количество
размещений
обозначается
m
n
A
(
табл
.2.1).
Таблица
1
Типы выборок
Повторений
элементов
нет
Повторения
элементов
есть
Порядок
важен
m
n
A
m
n
A
размещения
с
повторениями
Порядок
не
важен
m
n
C
m
n
C
Сочетания
с
повторениями
Пример
.
Определяя
трех
победителей
олимпиады
среди
20
участников
,
мы
составляем
размещения
из
20
элементов
по
3 ,
т
.
к
.
Страницы
- « первая
- ‹ предыдущая
- …
- 6
- 7
- 8
- 9
- 10
- …
- следующая ›
- последняя »
