1.3. Элементы комбинаторики
Комбинаторика – это отдельный раздел математики, и без неё дальше никуда. В узком смысле комбинаторика – это подсчёт различных комбинаций, которые можно составить из некоторого множества дискретных объектов. Под объектами понимаются какие-либо обособленные предметы или живые существа – люди, звери, грибы, растения, насекомые и т.д. Самыми распространёнными видами комбинаций являются перестановки объектов, их выборка из множества ( сочетания ) и распределение в выборке ( размещения ). Не пугайтесь малопонятных терминов, тем более, некоторые из них не очень удачны:
Перестановки, сочетания и размещения без повторений
Начнём с хвоста заголовка – что значит « без повторений »? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов, либо которые считаются таковыми по смыслу задачи. Представьте, что перед вами на столе слева направо выложены: яблоко / груша / банан Вопрос первый : сколькими способами их можно переставить ? Одна комбинация уже записана выше и с остальными проблем не возникает: яблоко / банан / груша груша / яблоко / банан груша / банан / яблоко банан / яблоко / груша банан / груша / яблоко Итого : 6 комбинаций или 6 перестановок . Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт! Пожалуйста, откройте Приложение Основные формулы комбинаторики и в пункте № 2 найдите формулу количества перестановок . Никаких мучений – 3 объекта можно переставить: P 3 3! 6 способами. Вопрос второй : сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт? а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний (см. тот же п.2 Приложения) : … Запись С 3 1 следует читать и понимать так : «сколькими способами можно выбрать 1 фрукт из трёх?».
| Внимание! Это демо-версия книги, полную и свежую версию курса можно найти здесь: http://mathprofi.com/knigi_i_kursy/ | 13 |
б) Перечислим все возможные сочетания двух фруктов: яблоко и груша; яблоко и банан; груша и банан. Количество комбинаций легко проверить по той же формуле:
| С 2 | 3! | 3 |
| 3 | 1! 2! | |
Запись С 3 2 понимается аналогично : «сколькими способами можно выбрать 2 фрукта из трёх?». в) И, наконец, три фрукта можно выбрать единственным способом:
| С 3 | 3! | 1 |
| 3 | 0! 3! | |
Следует отметить, что формула количества сочетаний сохраняет смысл и для
| пустой выборки: | |||
| С 0 | 3! | 1 способом можно выбрать ни одного фрукта – собственно, ничего не | |
| 3 | 3! 0! | ||
взять и всё. Но это явно не про студенток г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта (любые) или все 3 фрукта: … способами можно выбрать хотя бы один фрукт. …внимательные читатели уже кое о чём догадались. Но о смысле знака «плюс» позже. И для ответа на третий вопрос мне требуется два добровольца…, ну что же, раз никто не хочет, тогда буду вызывать к доске =) Вопрос третий : сколькими способами можно раздать по одному фрукту Даше и Наташе? Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно С 3 2 3 способами, перепишу их заново: яблоко и груша; яблоко и банан; груша и банан. Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов: яблоком можно угостить Дашу, а грушей – Наташу; либо наоборот – груша достанется Даше, а яблоко – Наташе. И такая перестановка возможна для каждой пары фруктов.
| Внимание! Это демо-версия книги, полную и свежую версию курса можно найти здесь: http://mathprofi.com/knigi_i_kursy/ | 14 |
В данном случае работает формула количества размещений : A 3 2 2 3 6 Она отличается от формулы С 3 2 тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждой возможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей. Пожалуйста, ещё раз внимательно перечитайте пункт №2 Приложения Основные формулы комбинаторики и постарайтесь хорошо уяснить разницу между перестановками, сочетаниями и размещениями. В простых случаях легко пересчитать все возможные комбинации вручную, но чаще всего это становится трудноподъёмной задачей, именно поэтому и нужно понимать смысл формул. Теперь остановимся на каждой комбинации подробнее:
Перестановки
Перестановками называют комбинации, состоящие из одних и тех же n различных объектов и отличающиеся только порядком их расположения. Количество всех возможных перестановок выражается формулой P n n ! Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть – все n объектов. Например, дружная семья: Задача 1 Сколькими способами можно рассадить 5 человек за столом? Решение : используем формулу количества перестановок: P 5 5! 120 Ответ : 120 способами Невероятно, но факт. И здесь не имеет значения круглый ли стол, квадратный, или вообще все люди сели встали, легли на скамейку вдоль одной стены – важен лишь их порядок расположения. Аналогично решается типовая задача о перестановке различных книг на полке, но это было бы слишком просто даже для «чайника»: Задача 2 Сколько четырёхзначных чисел можно составить из четырёх карточек с цифрами 0, 5, 7, 9? Для того чтобы составить четырёхзначное число нужно задействовать все четыре карточки (цифры на которых различны! ) , и это очень важная предпосылка для применения формулы P n n ! Очевидно, что, переставляя карточки, мы будем получать различные четырёхзначные числа, но стоп…, а всё ли тут в порядке? 😉
| Внимание! Это демо-версия книги, полную и свежую версию курса можно найти здесь: http://mathprofi.com/knigi_i_kursy/ | 15 |
Хорошенько подумайте над задачей! Сверить своё решение можно в конце книге. Вообще, это характерная черта комбинаторных и вероятностных задач – в них НУЖНО ДУМАТЬ. И зачастую думать чисто по-житейски, как, например, в разборе вступительного примера с фруктами. Сочетания В учебниках обычно даётся лаконичное и не очень понятное определение сочетаний, поэтому в моих устах формулировка будет не особо рациональной, но, надеюсь, доходчивой: Сочетаниями называют различные комбинации из m объектов, которые выбраны из множества n различных объектов, и которые отличаются друг от друга хотя бы одним объектом. Иными словами, отдельно взятое сочетание – это уникальная выборка из m элементов, в которой не важен их порядок (расположение). Общее же количество таких
| уникальных сочетаний рассчитывается по формуле С n m | n ! | . | |
| ( n m )! m ! | |||
Задача 3 В ящике находится 15 деталей. Сколькими способами можно взять 4 детали? Решение : прежде всего, обращаю внимание на то, что по логике такого условия, детали считаются различными – даже если они на самом деле однотипны и визуально одинаковы (в этом случае их можно, например, пронумеровать) . В задаче речь идёт о выборке из четырёх деталей, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество: … (прерываю решение для промежуточных объяснений) И здесь, конечно, не нужно «тягать» значения 11! 39916800, 15! 1307674368000 . В похожей ситуации я советую использовать следующий приём: в знаменателе выбираем наибольший факториал (в данном случае 11!) и сокращаем на него дробь. Для этого числитель следует представить в виде 15! 11! 12 13 14 15 . Распишу очень подробно:
| (*) | 11! 12 13 14 15 | 12 13 14 15 | 12 13 14 15 | 1365 | способами можно взять |
| 11! 4! | 4! | 24 |
4 детали из ящика. Ещё раз: что это значит? Это значит, что из 15 различных деталей можно составить одну тысячу триста шестьдесят пять уникальных сочетаний из 4 деталей. То есть, каждая такая комбинация из четырёх деталей будет отличаться от других комбинаций хотя бы одной деталью. Ответ : 1365 способами
| Внимание! Это демо-версия книги, полную и свежую версию курса можно найти здесь: http://mathprofi.com/knigi_i_kursy/ | 16 |
Источник
Перестановки, сочетания и размещения без повторений
Не пугайтесь малопонятных терминов, тем более, некоторые из них действительно не очень удачны. Начнём с хвоста заголовка – что значит «без повторений»? Это значит, что в данном параграфе будут рассматриваться множества, которые состоят из различных объектов. Например, представьте, что перед вами на столе яблоко, груша и банан. Выкладываем фрукты слева направо в следующем порядке:
Вопрос первый: сколькими способами их можно переставить?
Одна комбинация уже записана выше и с остальными проблем не возникает:
яблоко / банан / груша
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша
банан / груша / яблоко
Итого: 6 комбинаций или 6 перестановок.
Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше? Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!
Пожалуйста, откройте справочный материал Основные формулы комбинаторики, найдите формулу количества перестановок.
Никаких мучений – 3 объекта можно переставить способами.
Вопрос второй: сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?
а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний:
Запись в данном случае следует понимать так: «сколькими способами можно
б) Перечислим все возможные сочетания двух фруктов:
яблоко и груша;
яблоко и банан;
груша и банан.
Количество комбинаций легко проверить по той же формуле:
Запись понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».
в) И, наконец, три фрукта можно выбрать единственным способом:
Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки:
способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё.
г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
способами можно выбрать хотя бы один фрукт.
Вопрос третий: сколькими способами можно раздать по одному фрукту Даше и Наташе?
Для того чтобы раздать два фрукта, сначала нужно их выбрать. Согласно пункту «бэ» предыдущего вопроса, сделать это можно способами, перепишу их заново:
яблоко и груша;
яблоко и банан;
груша и банан.
Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов:
яблоком можно угостить Дашу, а грушей – Наташу;
либо наоборот – груша достанется Даше, а яблоко – Наташе.
И такая перестановка возможна для каждой пары фруктов.
В данном случае работает формула количества размещений:
Она отличается от формулы тем, что учитывает не только количество способов, которым можно выбрать несколько объектов, но и все перестановки объектов в каждой возможной выборке. Так, в рассмотренном примере, важно не только то, что можно просто выбрать, например, грушу и банан, но и то, как они будут распределены (размещены) между Дашей и Наташей.
Также напоминаю, что сейчас речь идёт о множестве с различными объектами, и если яблоко/грушу/банан заменить на 3 яблока или даже на 3 очень похожих яблока, то в контексте рассмотренной задачи они всё равно будут считаться различными.
Остановимся на каждом виде комбинаций подробнее:
Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:
Источник