- •Правило произведения Теоретико – множественная формулировка правила произведения
- •Комбинаторная формулировка правила произведения
- •Сложный выбор объектов
- •Соединения без повторений
- •Перестановки
- •Размещения из n элементов по m
- •Решение:
- •Сочетания
- •Основные понятия комбинаторики: соединения с повторениями
- •Размещения с повторениями
- •Сочетания с повторениями
- •Формулы пересчета для основных видов комбинаторных соединений
- •Принцип включения- исключения
- •Частные случаи формулы включений и исключений
- •Задача о беспорядках
- •Задача o встречах
- •Перестановки без фиксированных пар
- •Распределение объектов по ячейкам
- •Распределение одинаковых объектов
- •Вместимость ячеек задана
- •Распределение различных объектов по ячейкам с учётом их порядка в различных ячейках Вместимость ячеек неограниченна, ячейки могут быть пустыми
- •Вместимость ячеек неограниченна, ячейки не могут быть пустыми
- •Варианты к индивидуальному заданию по комбинаторике
- •Вариант №1.
- •Вариант №2.
- •Вариант №3.
- •Вариант №4.
- •Вариант №5.
- •Вариант №6.
- •Вариант №7.
- •Вариант №8.
- •Вариант №9.
- •Вариант №10.
- •Вариант №11.
- •Вариант №12.
- •Вариант №13.
- •Вариант №14.
- •Вариант №15.
- •Вариант №16.
- •Вариант №17.
- •Вариант №18.
- •Вариант №19.
- •Вариант №20.
- •Вариант №21.
- •Вариант №22.
- •Вариант №23.
- •Вариант №24.
- •Вариант №25.
- •Вариант №26.
- •Вариант №27.
- •Вариант №28.
- •Вариант №29.
- •Вариант №30.
- •Контрольные вопросы
Вариант №29.
1.Сколькими способами можно переставить буквы в слове параллелизм так, чтобы не изменялся порядок гласных?
2.Сколькими способами из колоды в 36 карт можно вытащить 5 карт, среди которых 5 с одинаковыми номерами?
3.Сколько можно сделать костей домино, используя числа 0, 1, … , r?
4.Сколько шестизначных чисел содержат ровно 3 различные цифры?
5.Используя метод включения и исключения, найти число способов размещения r различных предметов в n ящиках, причем не может быть пустых ящиков?
Вариант №30.
1. Пассажир оставил вещи в автоматической камере хранения, а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 26 и 37. Чтобы открыть камеру, нужно правильно выбрать пятизначный номер. Какое наибольшее количество номеров нужно перебрать, чтобы открыть камеру?
2.Сколькими способами из колоды в 37 карт (36 карт плюс джокер) можно вытащить 5 карт, среди которых 5 с одинаковыми номерами?
3.В почтовом отделении продаются открытки 10 сортов. Сколько существует способов купить 8 открыток? 8 различных открыток? 12 открыток?
4.Имеется 14 пар различных предметов. Найти полное число выборок из этих предметов, причем выборки должны отличаться только составом элементов, но не их порядком.
5.Используя метод включения и исключения, найти число способов размещения r различных предметов в n ящиках, причем ровно m ящиков являются пустыми?
Контрольные вопросы
1. Какие проблемы изучает комбинаторика?
2. Сформулировать основное правило комбинаторики: правило суммы в теоретико-множественной и комбинаторной формулировках.
3.Сформулировать основное правило комбинаторики: правило произведения в теоретико-множественной и комбинаторной формулировках.
4.Дать определения следующим понятиям: перестановка, размещение, сочетание.
5.Решить задачи пересчета для перестановок, размещений, сочетаний.
6. Сформулировать свойства числа сочетаний.
7. Дать определение перестановки с повторениями и вывести формулу пересчета.
8. Дать определение размещений с повторениями и вывести формулу пересчета.
9.Дать определение сочетаний с повторениями и вывести формулу пересчета.
10.Сформулировать принцип включений-исключений.
11.Частные случаи формулы включений-исключений.
12.Задача о беспорядках: формулировка и решение задачи пересчета.
13.Задача о встречах: формулировка и решение задачи пересчета.
14.Задача о перестановках без фиксированных пар: формулировка и решение задачи пересчета.
Литература
-
Виленкин Н.Я. Комбинаторика. – М.: Наука, 1969.
-
Липский В. Комбинаторика для программистов. – М.: Мир, 1988.
-
Холл М. Комбинаторика. – М.: Мир, 1970. – 424с.