Содержание
-
Элементы комбинаторики
-
Основные понятия комбинаторики
Теорема 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 элементов Сочетания из n элементов по k элементов (0 ≤ k ≤ n)
-
Схема выбора с возвращением Размещения с повторениями Сочетанияс повторениями Перестановки с повторениями (n1 + n2 +nk = n)
-
Итоговая сводка формул
(1-я строка – без повторений, 2-я строка – с повторениями)
-
Задачи
Задача 1. Сколько различных трехзначных чисел можно составить из цифр 0, 2, 3, 5, 7 если: а) цифры не повторяются; б) цифры могут повторяться? Решение: а) Первую цифру можно выбрать четырьмя способами (числа вида 025, 073, … не считаем трехзначными). Выбрав первую цифру (например, цифру 5) вторую цифру можно также выбрать четырьмя способами . Третью цифру, очевидно, можно выбрать тремя способами. Следовательно, согласно правилу умножения имеется 4 ∙ 4 ∙ 3 = 48 способов расстановки цифр, т.е. искомых трехзначных чисел будет 48 . б) Если цифры могут повторяться, то трехзначные числа можно составить 4 ∙ 5 ∙ 5 = 100 способами .
-
Задача 2. Составить различные размещения по два элемента из элементов множества А ={3, 4, 5} и подсчитать их число. Решение: Из трех элементов можно образовать следующие размещения по два элемента: (3,4); (4,3); (3,5); (5,3); (4,5); (5,4). Таким образом, всего их 6. Однако число размещений можно посчитать по формуле: или
-
Задача 3. Сколькими способами 3 награды (за I, II, III места) могут быть распределены между 10 участниками соревнований? Решение: Будем считать, что каждый участник соревнований может получить не более одной награды. Выбрать 3-х участников из 10 можно следующим образом, так как «призовые тройки» отличаются друг от друга либо составом участников, либо порядком их следования. Этот же результат можно получить, применяя правило умножения: претендентов на главную награду (I место) 10, на вторую – 9, на третью – 8; число различных способов распределения наград равно 10∙9∙8=720.
-
Задача 4. В вазе стоят 9 красных и 7 розовых гвоздик. Сколькими способами можно выбрать из нее: а) 3 гвоздики; б) 6 гвоздик одного цвета; в) 4 красных и 3 розовые гвоздики? Решение: а) Так как порядок выбора цветов не имеет значение, то выбрать 3 гвоздики из вазы, в которой стоят 16 гвоздик, можно б) Выбрать 6 гвоздик красного цвета можно
-
а 6 гвоздик розового цвета одного цвета (красных или розовых) можно способом. в) Выбрать 4 красных гвоздики из 9 имеющихся можно способами, а 3 розовых из 7 имеющихся можно способами. Поэтому букет из 4 красных и 3 розовых гвоздик можно составить по правилу умножения способами.
-
Задача 5. На диск сейфа нанесены 12 букв, а секретное слово состоит из 5 букв. Сколько неудачных попыток может быть сделано человеком, не знающим секретного слова? Решение: Общее число комбинаций можно вычислить по формуле Значит, неудачных попыток может быть 248831. Впрочем, обычно делают сейфы так, что после первой же неудачной попытки открыть их раздается сигнал тревоги.
-
Задача 6.Пять человек вошли в лифт на 1-м этаже девятиэтажного дома. Сколькими способами пассажиры могут выйти из лифта на нужных этажах? Решение: Каждый из 5 пассажиров может выйти на любом из восьми этажей со 2-го по 9-ый включительно. Возможными вариантами их выхода являются, например, 2-3-5-5-5 (это значит, что на 2-ом этаже вышел один пассажир, на 3-ем – один, а трое вышли на 5-ом этаже) или 9-9-9-9-9, или 4-5-6-7-9 и т.д. Общее число выходов пассажиров, по формуле равно Этот же результат можно получить, используя правило умножения: для 1-го пассажира имеется 8 вариантов выхода на этаже, для 2-го тоже 8, и для 3-го тоже 8, и для 4-го – 8, и для 5-го – 8. Всего получается 8∙8∙8∙8∙8=85 вариантов для выхода 5-ти пассажиров.
-
Задача 7. Сколько различных «слов» (под «словом» понимается любая комбинация букв) можно составить, переставляя буквы в слове АГА? MISSISSIPPI? Решение: Из трех букв можно составить Р3=3!=6 различных трехбуквенных «слов». В слове АГА буква А повторяется, а перестановка одинаковых букв не меняет «слова». Поэтому число перестановок с повторениями меньше числа перестановок без повторений во столько раз, сколько можно переставлять повторяющиеся буквы. В данном слове две буквы (1-ая и 3-я) повторяются; поэтому различных трехбуквенных «слов» из букв АГА можно составить столько: Впрочем, ответ можно получить и проще: каждое слово из букв А, Г и А однозначно определяется положением буквы Г; их всего три, поэтому и различных слов будет тоже три. .
-
Результат можно получить другой формулой: По этой же формуле найдем число одиннадцатибуквенных «слов» при перестановке букв в слове MISSISSIPPI. Здесь п=11, п1=1, п2=4 (4 буквы S), п3=4 (4 буквы I), п4=2 (2 буквы Р), поэтому
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.