Комбинаторика

Комбинаторика Комбинаторика – раздел математики, посвященный подсчету количеств разных комбинаций элементов некоторого, обычно конечного, множества Задачи: 1) Сколькими способами 6 разных папок с документами можно расставить на полке? 2) При расследовании хищения установлено, что у преступника шестизначный номер, в котором все цифры различны и нет нулей. Следователь, полагая, что перебор этих номеров достаточно будет одного - двух часов, доложил о раскрытии преступления. Прав ли он? 3) Анкета по изучению общественного мнения содержит 10 вопросов, на каждый из которых возможен один из трех ответов: «да»,»нет», «не знаю».Найти число всех возможных способов заполнения анкеты.

Принципы комбинаторики Принцип сложения Основные принципы комбинаторики: Принцип сложения. Принцип умножения. Принцип сложения Задача 1: В группе 7 девушек и 8 юношей. Сколькими способами можно выбрать 1 человека для работы у доски? Решение: 7+8=15 Задача 2: В группе 7 человек имеют «5» по математике, 9 человек – «5» по философии. В сессии 2 экзамена. Известно, что 4 человека сдали сессию отлично. Сколько человек имеют хотя бы одну пятерку в сессии? Решение: 7+9-4=12

Принцип сложения Принцип сложения: Если объект a можно получить n способами, объект b – m способами, то объект «a или b» можно получить n+m-k способами, где k – это количество повторяющихся способов. Теоретико-множественная формулировка

Принцип умножения Задача: Плохо разбирающийся в компьютерном обеспечении студент пытается подобрать к 5 принтерам соответствующий драйвер из имеющихся 7. Сколько комбинаций «принтер- драйвер» он может составить? Решение: 57=35. Принцип умножения: если объект a можно получить n способами, объект b – m способами, то объект «a и b» можно получить mn способами. Теоретико-множественная формулировка

Размещение без повторений Определение 1 k -размещением без повторений элементов множества А называется упорядоченный набор длины k попарно различных элементов множества А. Пример: - 2 размещения: Число k- размещений n элементного множества обозначается и вычисляется по формуле: Задача: В олимпиаде по математике участвуют 12 команд. Сколькими способами они могут занять призовые места?

Определение 2 Перестановкой n элементного множества называется упорядоченный набор неповторяющихся элементов этого множества длины n. Пример: перестановки: Число размещений n – элементного множества обозначают P n и вычисляется по формуле: Задача: Сколькими способами можно осуществить сортировку 6 файлов в данном каталоге? Перестановки без повторений

Размещения с повторениями Определение 3 k – размещением с повторениями n–элементного множества называется упорядоченный набор длины k элементов данного множества. Пример 2- размещения с повторениями: Число k – размещений с повторениями вычисляется по формуле: Задача: Сколько существует номеров машин?

Перестановки с повторениями Определение 4 Число перестановок n – элементов, в котором элементов i –того типа ( ) вычисляется по формуле Задача: Сколько слов можно составить, переставив буквы в слове «экзамен», а в слове «математика»? Решение:

Задачи 1)Сколькими способами можно составить список из 7 студентов? 2)Сколькими способами можно составить список 7 студентов, так, чтобы два указанных студента располагались рядом? 3) Сколькими способами можно вызвать по очереди к доске 4 студентов из 7?