Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Перестановки, сочетания и размещения без повторенийСтр 1 из 2Следующая ⇒ Задачи по комбинаторике. Примеры решений Автор: Емелин Александр http://www.mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html Для вычисления вероятностей событий необходимо разобраться с основными понятиями комбинаторики. Следует отметить, что комбинаторика является самостоятельным разделом высшей математики (а не частью ТВ). Нам достаточно небольшой доли теоретических знаний, которые мы рассмотрим ниже, и познакомимся с решением типовых комбинаторных задач. В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа – люди, звери, грибы, растения, насекомые и т.д. При этом комбинаторику совершенно не волнует, что множество состоит из тарелки манной каши, паяльника и болотной лягушки. Принципиально важно, что эти объекты поддаются перечислению – их три (дискретность) и существенно то, что среди них нет одинаковых. Предварительно введем новое важное для нас понятие: факториал. Факториал – это произведение всех натуральных чисел от 1 до п. Обозначают п! ичитают: п — факториал.
Заметим,
Например, 6! = 720, 7! = 5040. Объясните, как получены данные равенства.
Вычислим значение выражения: . Объясните, как выполнены вычисления. Теперь перейдем к комбинациям. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества (сочетание) и распределение (размещение). Перестановки, сочетания и размещения без повторений Начнём с хвоста заголовка – что значит «без повторений»? Это значит, что в данной статье будем рассматривать множества, которые состоят из различных объектов. Представьте, что перед вами на столе лежат яблоко, груша и банан (при наличии таковых ситуацию можно смоделировать и реально). Выкладываем фрукты слева направо в следующем порядке: яблоко / груша / банан Вопрос первый: сколькими способами их можно переставить? Одна комбинация уже записана выше и с остальными проблем не возникает: яблоко / банан / груша Итого: 6 комбинаций или 6 перестановок. Хорошо, здесь не составило особого труда перечислить все возможные случаи. Но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт! Попробуйте их составить самостоятельно. Получится 24 различных комбинаций. А чтобы составить все комбинации из 5 фруктов, то потребуется достаточно много времени, чтобы их записать. Пожалуйста, откройте справочный материал Основные формулы комбинаторики (методичку удобно распечатать) и в пункте №2 найдите формулу количества перестановок. Никаких мучений – 3 объекта можно переставить Р3 = 3! = 6 способами. Вопрос второй: сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт? а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний: Запись в данном случае следует понимать так: «число способов, которыми можно выбрать один фрукт из трёх» б) Перечислим все возможные сочетания двух фруктов: яблоко и груша; Количество комбинаций легко проверить по той же формуле: в) И, наконец, три фрукта можно выбрать единственным способом: Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки: способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё. г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта: + + = 3 + 3 + 1 = 7 способами можно выбрать хотя бы один фрукт. Читатели, внимательно изучившие вводный урок по теории вероятностей, уже кое о чём догадались. Но о смысле знака «плюс» позже. Вопрос третий: сколькими способами можно раздать по одному фрукту Даше и Наташе? Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново: яблоко и груша; Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов: И такая перестановка возможна для каждой пары фруктов. В данном случае работает формула количества размещений: Пожалуйста, внимательно прочитайте Основные формулы комбинаторики и постарайтесь хорошо уяснить разницу между перестановками, сочетаниями и размещениями. В простейших случаях можно пересчитать все возможные комбинации вручную, но чаще всего это становится неподъемной задачей, именно поэтому и нужно понимать смысл формул. Остановимся на каждом виде комбинаций подробнее: Перестановки Перестановками называют комбинации, состоящие из одних и тех же n различных объектов и отличающиеся только порядком их расположения. Количество всех возможных перестановок выражается формулой Рn = n!. Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все n объектов. Задача 1 Сколькими способами можно рассадить 5 человек за столом? Решение: используем формулу количества перестановок: Р5 = 5! = 1 × 2 × 3 × 4 × 5 = 120. Ответ: 120 способами Невероятно, но факт. Обратите внимание, что здесь не имеет значения круглый ли стол, квадратный, или вообще все люди сели Задача 2 Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9? Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки (цифры на которых различны! ), и это очень важная предпосылка для применения формулы Рn = n!. Очевидно, что, переставляя карточки, мы будем получать различные четырёхзначные числа. … Стоп, а всё ли тут в порядке? Хорошенько подумайте над задачей! Вообще, это характерная черта комбинаторных и вероятностных задач – в них НУЖНО ДУМАТЬ. И зачастую думать по-житейски, как, например, в разборе вступительного примера с фруктами. Решение и ответ в конце урока. Сочетания В учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому, в данная ниже формулировка будет не особо рациональной, но, надеюсь, доходчивой. Сочетаниями называют различные комбинации из m объектов, которые выбраны из множества n различных объектов, и которые отличаются друг от друга хотя бы одним объектом. Иными словами, отдельно взятое сочетание – это уникальная выборка из m элементов, в которой не важен их порядок (расположение). Общее же количество таких уникальных сочетаний рассчитывается по формуле: Задача 3 В ящике находится 15 деталей. Сколькими способами можно взять 4 детали? Решение: прежде всего, снова обращаю внимание на то, что по логике условия детали считаются различными – даже если они на самом деле однотипны и визуально одинаковы В задаче речь идёт о выборке из 4-х деталей, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество: Здесь, конечно же, не нужно ворочать огромные числа 11! = 39916800, 15! = 1307674368000. 1365 способами можно взять 4 детали из ящика. Ещё раз: что это значит? Это значит, что из набора 15-ти различных деталей можно составить одну тысячу триста шестьдесят пять уникальных сочетания 4-х деталей. То есть, каждая такая комбинация из 4-х деталей будет отличаться от других комбинаций хотя бы одной деталью. Ответ: 1365 способов Формуле необходимо уделить самое пристальное внимание, поскольку она является «хитом» комбинаторики. При этом полезно понимать и без всяких вычислений записывать «крайние» значения: , , , . Применительно к разобранной задаче: – единственным способом можно взять ни одной детали; – способами можно взять 1 деталь (любую из 15-ти); – способами можно взять 14 деталей (при этом какая-то одна из 15-ти останется в ящике); Задача 4 Сколькими способами из колоды в 36 карт можно выбрать 3 карты? Это пример для самостоятельного решения. Чем приятны многие комбинаторные задачи, так это краткостью – главное, разобраться в сути. Размещения Или «продвинутые» сочетания. Размещениями называют различные комбинации из k объектов, которые выбраны из множества n различных объектов, и которые отличаются друг от друга как составом объектов в выборке, так и их порядком. Количество размещений рассчитывается по формуле = n (n – 1) (n – 1)… (n – k +1). Данная формула может быть преобразована и записана и в таком виде: = Задача 5 Боря, Дима и Володя сели играть в «очко». Сколькими способами им можно сдать по одной карте? (колода содержит 36 карт) Решение: ситуация похожа на предыдущую задачу, но отличается тем, что здесь важно не только то, какие три карты будут извлечены из колоды, но и то, КАК они будут распределены между игроками. По формуле размещений: = 36 × 35 × 34 = 42840 способами можно раздать 3 карты игрокам. Есть и другая схема решения, которая, с моей точки зрения, даже понятнее. Рассмотрим ее. Первый шаг: способами можно извлечь 3 карты из колоды. Второй шаг: теперь давайте рассмотрим, какую-нибудь одну из семи тысяч ста сорока комбинаций, например: король пик (КП), девятка червей (9Ч), семерка червей (7Ч). Выражаясь комбинаторной терминологией, эти 3 карты можно «переставить» между Борей, Димой и Володей Р3 = 3! = 6 способами: КП, 9Ч, 7Ч; Такое количество перестановок имеется для любого уникального набора из 3-х карт. А таких наборов, не забываем, мы насчитали . Не нужно быть профессором, чтобы понять, что найденное количество сочетаний следует умножить на шесть и тогда мы получим количество всех способов раздачи по одной карте трем игрокам. Итак: способами можно сдать по одной карте 3-м игрокам. Этот результат равен тому, который получили, решая задачу по формуле размещения. По существу, получилась наглядная проверка формулы . Конкретный смысл этой формуле более подробно рассмотрен в конце решения задачи 8. Ответ: 42840 способов. Задача 6 В студенческой группе 23 человека. Сколькими способами можно выбрать старосту и его заместителя? Задача о «размещении» должностей в коллективе встречается очень часто. Краткое решение и ответ в конце урока.
|