- •Дискретная математика
- •Введение
- •Лабораторная работа №1
- •1. Теоретический раздел
- •2. Примеры решения задач с использованием множеств
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №2
- •1. Теоретический раздел
- •2. Примеры решения задач
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №3
- •1. Теоретический раздел
- •2. Примеры решения задач
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №4
- •1. Теоретический раздел
- •2. Описание алгоритма фронта волны
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №5
- •1. Теоретический раздел
- •2. Описание алгоритма построения минимального остовного дерева
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №6
- •1. Теоретический раздел
- •2. Описание алгоритмов нахождения кратчайшего пути
- •2.1. Алгоритм Дейкстры нахождения минимального пути
- •2.2. Алгоритм нахождения минимального пути Форда-Беллмана
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №7
- •1. Теоретический раздел
- •2. Описание алгоритма нахождения полного потока
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Лабораторная работа №8
- •1. Теоретический раздел
- •2. Описание алгоритма нахождения максимального потока
- •3. Контрольные вопросы
- •4. Задания для самостоятельного решения
- •Литература
- •Дискретная математика
Лабораторная работа №3
Тема лабораторной работы: Комбинаторные схемы.
Цели лабораторной работы:
освоить основные понятия комбинаторики;
изучить примеры алгоритмов работы с комбинаторными схемами;
закрепить практические навыки программирования;
провести вычислительный эксперимент и сравнить результаты решением вручную.
1. Теоретический раздел
Размещения без повторений.
Подсчитаем количество способов расположить n различных элементов по k различным позициям (k<n). Такие расположения называются размещениями, а их количество, от французского слова arrangement обозначается . В случае, если k=n количество предметов совпадает с количеством имеющихся мест, подобную задачу о числе перестановок мы рассматривали ранее.
Если из n объектов выбирают k штук, то число выборов последнего объекта есть n-k невыбранных объектов, что означает наличие возможности выбора последнего выбранного объекта. То же, другими словами: после выбора первых элемента остается выбрать элемент.
Теорема: число размещений n различных элементов по k различным позициям есть:
,
или, в терминах факториалов:
.
Пример 1. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?
Решение. Искомое число трехполосных флагов:
Примечание: заметим, что в случае, когда число мест, по которым размещают предметы, совпадает с количеством самих предметов, т. е. когда k=n, рассматриваемая задача становится задачей о числе перестановок. В нашем случае при этом мы получаем в знаменателе дроби ноль факториал, и для того, что бы разные формулы, соответствующие одной и той же задаче, приводили к одинаковым результатам, полагают, что .
Размещения с повторениями.
Пусть даны n различных видов предметов, которые можно разместить по k различным местам, причем выбирать предметы можно с повторениями (т.е. можно выбрать несколько предметов одного вида). Такие выборки называются размещениями с повторениями, а их количество вычисляется по формуле: .
Сочетания без повторений.
Подсчитаем количество способов, которыми можно выбрать k из n различных предметов. Такие выборки называются сочетаниями, а их количество обозначается .
При k<n, выбрать k предметов из n можно способами, переставляя их способами:
Рекуррентная формула:
Свойства сочетаний:
Сочетания с повторениями.
Пусть имеются предметы n различных видов, и из них составляются наборы, содержащие k элементов. Такие выборки называются сочетаниями с повторением. Их число обозначается .
Теорема: число сочетаний с повторениями может быть вычислено по формулам: .
Перестановки без повторений.
Перестановки в ряд.
Перестановкой из n элементов (или n-перестановкой) называется n-элементное упорядоченное множество, составленное из элементов n-элементного множества.
Иначе: Перестановкой из n элементов (или n-перестановкой) называется размещение из n элементов по n без повторений.
Число перестановок из n элементов без повторений обозначается от французского слова perturbation.
Теорема: число способов расположить в ряд n различных объектов есть
Замечание: Рекуррентная формула:
.
Пример 2. Сколько различных шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4,5, если цифры в числе не повторяются?
Решение:
1) Найдем количество всех перестановок из этих цифр: P6=6!=720.
2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P5=5!=120.
P6-P5=720-120=600
Перестановки симметричных объектов.
N различных предметов можно расположить по кругу способами, а если их можно еще и переворачивать, то различными способами.
Перестановки с повторениями.
Пусть даны элементов первого типа, — второго типа, ..., — -го типа, всего элементов. Способы разместить их по различным местам называются перестановками с повторениями. Их количество обозначается .
Теорема: число перестановок с повторениями:
.
Пример 3. Сколькими способами можно переставить буквы слова «ананас»?
Решение: всего букв 6. Из них одинаковы n1«а»=3, n2«н»=2, n3«с»=1. Следовательно, число различных перестановок равно P(3,2,1)