Комбинаторика Комбинаторика – раздел математики, посвященный подсчету количеств разных комбинаций элементов некоторого, обычно конечного, множества Задачи: - презентация

1

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

3 Принципы комбинаторики

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

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

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

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

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

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

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