🗊Презентация Элементы комбинаторики

Теорема 1. Правило умножения: если из некоторого конечного множества первый объект (элемент а) можно выбрать n1 способами, а второй объект (элемент b) – n2 способами, то оба объекта (а и b) в указанном порядке можно выбрать n1∙n2 способами. Теорема 1. Правило умножения: если из некоторого конечного множества первый объект (элемент а) можно выбрать n1 способами, а второй объект (элемент b) – n2 способами, то оба объекта (а и b) в указанном порядке можно выбрать n1∙n2 способами. Теорема 2. Правило сложения: если некоторый объект а можно выбрать п1 способами, а объект b можно выбрать n2 способами, причем первые и вторые способы не пересекаются, то любой из объектов (а или b) можно выбрать n1 + n2 способами.

Схема выбора без возвращений Схема выбора без возвращений Размещения из n элементов по k элементов (0 ≤ k ≤ n) где n! = 1 ∙ 2 ∙ 3 ∙ … ∙ n, причем 1! = 1, 0! = 1 Перестановки из n элементов

Схема выбора с возвращением Схема выбора с возвращением Размещения с повторениями

Задача 1. Сколько различных трехзначных чисел можно составить из цифр 0, 2, 3, 5, 7 если: Задача 1. Сколько различных трехзначных чисел можно составить из цифр 0, 2, 3, 5, 7 если: а) цифры не повторяются; б) цифры могут повторяться? Решение: а) Первую цифру можно выбрать четырьмя способами (числа вида 025, 073, … не считаем трехзначными). Выбрав первую цифру (например, цифру 5) вторую цифру можно также выбрать четырьмя способами . Третью цифру, очевидно, можно выбрать тремя способами. Следовательно, согласно правилу умножения имеется 4 ∙ 4 ∙ 3 = 48 способов расстановки цифр, т.е. искомых трехзначных чисел будет 48 . б) Если цифры могут повторяться, то трехзначные числа можно составить 4 ∙ 5 ∙ 5 = 100 способами .

Задача 2. Составить различные размещения по два элемента из элементов множества А ={3, 4, 5} и подсчитать их число. Задача 2. Составить различные размещения по два элемента из элементов множества А ={3, 4, 5} и подсчитать их число. Решение: Из трех элементов можно образовать следующие размещения по два элемента: (3,4); (4,3); (3,5); (5,3); (4,5); (5,4). Таким образом, всего их 6. Однако число размещений можно посчитать по формуле: или

Задача 3. Сколькими способами 3 награды (за I, II, III места) могут быть распределены между 10 участниками соревнований? Задача 3. Сколькими способами 3 награды (за I, II, III места) могут быть распределены между 10 участниками соревнований? Решение: Будем считать, что каждый участник соревнований может получить не более одной награды. Выбрать 3-х участников из 10 можно следующим образом, так как «призовые тройки» отличаются друг от друга либо составом участников, либо порядком их следования. Этот же результат можно получить, применяя правило умножения: претендентов на главную награду (I место) 10, на вторую – 9, на третью – 8; число различных способов распределения наград равно 10∙9∙8=720.

Задача 4. В вазе стоят 9 красных и 7 розовых гвоздик. Сколькими способами можно выбрать из нее: Задача 4. В вазе стоят 9 красных и 7 розовых гвоздик. Сколькими способами можно выбрать из нее: а) 3 гвоздики; б) 6 гвоздик одного цвета; в) 4 красных и 3 розовые гвоздики? Решение: а) Так как порядок выбора цветов не имеет значение, то выбрать 3 гвоздики из вазы, в которой стоят 16 гвоздик, можно б) Выбрать 6 гвоздик красного цвета можно

а 6 гвоздик розового цвета а 6 гвоздик розового цвета одного цвета (красных или розовых) можно способом. в) Выбрать 4 красных гвоздики из 9 имеющихся можно способами, а 3 розовых из 7 имеющихся можно способами. Поэтому букет из 4 красных и 3 розовых гвоздик можно составить по правилу умножения способами.

Задача 5. На диск сейфа нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова? Задача 5. На диск сейфа нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова? Решение: Общее число комбинаций можно вычислить по формуле Значит, неудачных попыток может быть 248831. Впрочем, обычно делают сейфы так, что после первой же неудачной попытки открыть их раздается сигнал тревоги.