ВИДЕО УРОК
Традиционное решение комбинаторных задач сводится к определению вида сочетания, о котором идёт речь в задаче, и применение соответственной формулы для вычисления количества этих сочетаний.
Здесь основная трудность – определение вида сочетаний: перестановки, размещения, комбинации.
Перестановки.
Пусть имеется n различных объектов. Будем переставлять их всеми возможными способами (число и состав объектов остаётся неизменными, меняется только их порядок). Получившиеся комбинации называются перестановками.
Перестановками называют комбинации, состоящие из одних и тех же n различных объектов и отличающиеся только порядком их расположения.
Или
Перестановками называются такие выборки элементов, которые отличаются только порядком расположения элементов, но не самими элементами.
Отличительной особенностью перестановок является то, в каждой из них участвует всё множество, то есть, все n объектов.
Формула для числа перестановок.
Если перестановки
производятся на множестве из n элементов, их
число определяется по формуле:
По определению,
считают, что
0! = 1, 1! = 1.
Схема для решения комбинаторных задач.
Перед решением задачи на вычисление разных видов сочетаний предлагается схема способствующая правильному выявлению вида сочетания согласно условию задачи. При этом учитываются характеристические свойства каждого вида сочетаний.
ЗАДАЧА:
Сколькими способами можно рассадить 5 человек за столом ?
РЕШЕНИЕ:
Используем формулу количества перестановок.
Р5 = 5! = 120.
ОТВЕТ:
120 способами.
ЗАДАЧА:
На книжной полке помещается 30 томов. Сколькими способами их можно расставить, чтобы при этом 1-й и 2-й тома не стояли рядом ?
РЕШЕНИЕ:
Определим общее число перестановок из 30 элементов по формуле
Р30 = 30!
Чтобы вычислить число “лишних” перестановок, сначала определим, сколько вариантов, в котором 2-й том находится рядом с 1-ым справа от него. В таких перестановках 1-ый том может занимать места с первого по 29-е, а 2-й со второго по 30-е – всего 29 мест для этой пары книг. И при каждом таком положении первых двух томов остальные 28 книг могут занимать остальные 28 мест в произвольном порядке. Вариантов перестановки 28 книг
Р28 = 28!
Всего “лишних” вариантов при расположении 2-го тома справа от 1-го получится
29×28! = 29!
Аналогично рассмотрим случай, когда 2-й том расположен рядом с первым, но слева от него. Получается такое же число вариантов
29×28! = 29!
Значит всего “лишних” перестановок
2×29!,
а нужных способов расстановки
30! – 2×29!
Вычислим это значение
30! – 2×29! =
29!×30 – 2×29! =
29!×(30 – 2) =
29!×28.
Итак, нам нужно перемножить все натуральные числа от 1 до 29 и ещё раз умножить на 28.
ОТВЕТ:
2,4757335×1032.
ЗАДАЧА:
Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами
0, 5, 7, 9 ?
РЕШЕНИЕ:
Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки (цифры на которых различны), и это очень важная предпосылка для применения формулы Рn = n! Очевидно, что, переставляя карточки, мы будем получать различные четырёхзначные числа, но когда карточка с нулём располагается на 1-м месте, то число становится трёхзначным, поэтому данные комбинации следует исключить.
Сначала найдём количество всех возможных
перестановок 4 карточек
Р4 = 4! = 24.
Пусть ноль находится на 1-м месте, тогда оставшиеся 3 цифры в младших разрядах можно переставить
Р3 = 3! = 6 способами.
Так как карточек немного, то здесь несложно перечислить все такие варианты
0579, 0597, 0759,
0795, 0957, 0975.
Таким образом, из предложенного набора можно составить
24 – 6 = 18
четырёхзначных чисел.
ОТВЕТ: 18.
Перестановки с повторениями.
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом:
Сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k < n), т. е. одинаковые предметы.
Формула для числа перестановок с повторениями.
Схема для решения комбинаторных задач.
В слове “темперамент” 11 букв (n = 11) , буква “т” повторяется дважды (n1 = 2), буква “е” – трижды (n2 = 3) и буква “м” – дважды (n3 = 2). Число возможных перестановок букв в этом слове:
ЗАДАЧА:
Сколько различных буквосочетаний можно получить перестановкой карточек со следующими буквами:
К, О, Л, О, К, О, Л, Ь, Ч, И, К ?
РЕШЕНИЕ:
В том случае, если бы все буквы были различны, то следовало бы применить тривиальную формулу Рn, однако совершенно понятно, что для предложенного набора карточек некоторые манипуляции будут срабатывать <<вхолостую>>, так, например, если поменять местами любые две карточки с буквами <<К>> в любом слове, то получится то же самое слово. Причём, физически карточки могут сильно отличаться: одна быть круглой с напечатанной буквой <<К>>, другая – квадратной с нарисованной буквой <<К>>. Но по смыслу задачи даже такие карточки считаются одинаковыми, поскольку в условии спрашивается о буквосочетаниях.
Всё предельно просто – всего 11
карточек, среди которых буква
К – повторяется 3 раза.
О –
повторяется 3 раза.
Л –
повторяется 2 раза.
Ь –
повторяется 1 раз.
Ч –
повторяется 1 раз.
И –
повторяется 1 раз.
Проверка:
3 + 3 + 2 + 1 + 1 + 1,
Что и требовалось проверить.
По формуле количества перестановок с повторениями:
На практике вполне допустимо не записывать общую формулу
и, кроме того, опускать единичные факториалы:
ЗАДАЧА:
Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и один день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю ?
РЕШЕНИЕ:
Формула Р7 = 7! здесь не годится, поскольку учитывает совпадающие перестановки (например, когда меняются местами силовые упражнения в среду с силовыми упражнениями в четверг).
По формуле количества перестановок с повторениями:
ОТВЕТ: 105.
Перестановки и теория вероятностей.
Часто необходимость подсчёта числа вариантов возникает в теории вероятностей.
ЗАДАЧА:
На книжной полке стояло 30 томов. Ребёнок уронил книги с полки, а затем расставил их в случайном порядке. Какова вероятность того, что он не поставил 1-й и 2-й тома рядом ?
РЕШЕНИЕ:
Сначала определим вероятность событие А, состоящего в том, что ребёнок поставил 1-й и 2-й тома рядом. Элементарное событие – некая расстановка книг на полке. Понятно, что общее число всех элементарных событий будет равно общему числу всех возможных перестановок
Р30 = 30!.
Число элементарных событий, благоприятствующих событию А, равно числу перестановок, в которых 1-й и 2-й тома стоят рядом, оно равно
2×29!.
Вероятность определяем делением числа благоприятствующих элементарных событий на число всех возможных элементарных событий.
Р(В) = 1 – Р(А) =
1 – 1/15 = 14/15
=
0,9333.
ОТВЕТ: 0,9333.
В ответе получилось число близкое к единице, это означает, что при таком количестве книг случайно поставить два заданных тома рядом сложнее, чем не поставить.
Задания к уроку 3
Другие уроки:
Комментариев нет:
Отправить комментарий