Дискретная математика. Ерош И.Л - 63 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

63
4. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ
Комбинаторика является разделом дискретной математики, ориен
тированным на решение задач выбора и расположения элементов не
которого множества в соответствии с заданными правилами и ограни
чениями. Каждое такое правило определяет способ построения неко
торой комбинаторной конфигурации, поэтому комбинаторный анализ
(комбинаторика) занимается изучением свойств комбинаторных кон
фигураций, условиями их существования, алгоритмами построения и
оптимизацией этих алгоритмов.
Этот раздел математики тесно связан с рядом других разделов дис
кретной математики: теорией вероятностей, теорией графов, теорией
чисел, теорией групп и т. д.
Первые подразделы посвящены элементам классической комбина
торики: размещениям, перестановкам, сочетаниям. Далее рассматри
ваются некоторые классы наиболее часто встречающихся задач: ком
бинаторные задачи с ограничениями, комбинаторные задачи раскла
док и разбиений; комбинаторные задачи, решаемые с помощью рекур
рентных соотношений.
Порядок изложения материала и многие примеры заимствованы из
книг известного российского математика и прекрасного популяриза
тора математических идей Н. Я. Виленкина.
4.1. Основные понятия и теоремы комбинаторики
Рассмотрим сначала основные понятия комбинаторики: размеще
ния, перестановки и сочетания, главная теорема,– что часто называ
ют классическим разделом комбинаторики. Затем рассмотрим несколь
ко классов комбинаторных задач.
4.1.1. Размещения с повторениями
Рассмотрим следующую задачу: сколько различных пятиразрядных
чисел можно составить с помощью 10 цифр?
Пронумеруем разряды:
12345
В первый разряд можно поставить одну из 10 цифр. Независимо от
того, какая цифра поставлена, во второй разряд можно также поста
вить одну из 10 цифр и т. д. Всего получается 10
5
различных чисел.

Страницы