- Основные комбинации и повторения
- Перестановки
- Сочетания
- Размещения
- Правила работы с комбинациями
- Выводы
Комбинаторика — эта та сфера математики, которую мы используем каждый день. Для примера вспомните ситуацию, когда вы заказывали пиццу/бургер/ролл/салат в сочетании с колой/соком/чаем/кофе. Выбрать какую-то комбинацию блюда и напитка — значит, решить комбинаторную задачу.
Конечно, комбинаторика используется и в профессиональной среде:
- В программировании, чтобы посчитать затраты ресурсов на расчет того или иного цикла
- При разработке алгоритмов криптографии или оптимизации
- В анализе и прогнозировании рынков, оптимизации бизнес-процессов и распределении ресурсов
- В продуктовых задачах на расчет вероятностей события, чтобы посчитать все возможные исходы события
В целом, комбинаторика полезна всем, кто сталкивается с организацией, размещением, перечислением или оптимизацией элементов в системе или комплексе. В этом уроке мы изучим основы комбинаторики и обсудим самые базовые комбинации.
Основные комбинации и повторения
Комбинаторика помогает посчитать количество различных комбинаций, которые можно составить из набора предметов или вариантов действий. В ней выделяют три основные вида комбинаций:
- Перестановки
- Сочетания
- Размещения
Важно запомнить, что все они бывают с повторениями и без. О повторениях удобнее рассказать на примере. Предположим, у нас есть задача – посчитать, сколькими разными способами можно разложить на столе яблоко, грушу и банан.
Если у нас на руках есть ровно одно яблоко, одна груша и один банан – это будет задача без повторений. Если у нас есть три одинаковых яблока, две груши и один банан, то это будет задача с повторениями.
Перестановки
Это комбинации различных элементов, которые отличаются только порядком расположения элементов. Работать с ними помогает такая формула:
Pₙ = n!, где Pₙ — это количество возможных перестановок, а n — число элементов в наборе
Применим ее на практике для перестановок без повторений. Представим, что у нас есть ручка, карандаш и фломастер. Сколько существует способов разложить их в разном порядке? Используем формулу и выясним, что это можно сделать шестью способами: P₃ = 3! = 6
Кроме того, перестановки могут быть и с повторениями — некоторые элементы могут совпадать. Для примера возьмем набор карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К. Сколько различных комбинаций можно составить, переставив карточки? В нашем наборе 11 букв, в том числе три К, три О и две Л. Применим формулу, которая учитывает эти повторения:
P₁₁ = (11!)/(3!*3!*2!) = 39916800/(6 * 6 * 2) = 554400
Сочетания
Сочетания — это уникальные выборки из всех элементов множества. При этом сочетания должны отличаться друг от друга хотя бы одним объектом. В этом случае порядок элементов не важен. Иными словами, отдельно взятое сочетание – это уникальный набор из m элементов, выбранных из множества n. Общее количество таких уникальных сочетаний рассчитывается по формуле:
Pₙ ^ m = (n!) / ((n - m)! * m!), где:
m— количество элементов, которые мы хотим выбратьn— общее количество элементов в выборке
Сочетания без повторений отвечают на вопрос «Сколько существует способов выбрать n фруктов из нашего множества?». Посмотрим, как это работает на примере. Представим, что у нас есть три фрукта — яблоко, груша и банан. Из этого множества мы хотим выбрать только один фрукт. Посчитаем, сколько существует способов это сделать.
Взять один фрукт из набора можно тремя способами — только яблоко, только грушу или только банан:
C₃ ^ 1 = (3!)/(2! * 1!) = 6/(2 * 1) = 3
А теперь представим, что мы хотим взять два фрукта. Есть три возможных сочетания — яблоко + груша, яблоко + банан, груша + банан. Посмотрим на формулу:
C₃ ^ 2 = (3!)/(1! * 2!) = 3
Попробуем взять три фрукта и выясним, что существует всего один способ:
C₃ ^ 3 = (3!)/(0! * 3!) = 1
А теперь проверим, сколькими способами можно взять хотя бы один фрукт. Условия «хотя бы один» подразумевает, что нас устроит выборка с любым количеством фруктов. Другими словами, все семь сочетаний выше нам подходят:
C₃ ^ 1 + C₃ ^ 2 + C₃ ^ 3 = 3 + 3 + 1 = 7
А еще существует один способ выбрать ноль фруктов:
C₃ ^ 0 = (3!)/(3! * 0!) = 1
Кроме того, сочетания могут быть с повторениями. В этом случае мы собираем выборку из нескольких групп, причем каждая группа состоит из одинаковых объектов.
Представим студенческую столовую с тремя видами выпечки — на полке лежат хот-доги, ватрушки и пончики. Если мы хотим купить пять товаров, сколько существует способов это сделать?
В нашей выборке обязательно будут одинаковые пирожки, потому что мы хотим купить 5 штук и выбираем всего из 3 видов. Варианты тут на любой вкус: 5 хот-догов, 5 ватрушек, 3 хот-дога + 2 ватрушки, 1 хот-дог + 2 ватрушки + 2 пончика и так далее.
Как и при обычных сочетаниях, порядок выбора и поедания не важен. Используем формулу и выясняем, что есть 21 возможное сочетание:
P₃ ^ 5 = C_(3+5-1) ^ 5 = C₇ ^ 5 = (7!)/(2! * 5!) = (6 * 7)/(2!) = 21
Размещения
Размещения — это комбинации, выбранные из множества, которые отличаются друг от друга составом объектов и порядком их размещения. Количество возможных сочетаний рассчитывается по формуле:
Aₙ ^ m = (n -m + 1) * ... * (n - 1) * n, где:
m— количество элементов в нашей выборкеn— общее количество элементов множества
Вернемся к задаче с яблоком, грушей и бананом. Представим, что из этого набора нам нужно раздать по одному фрукту Даше и Наташе. Для начала выбираем два фрукта из трех, это можно сделать тремя способами (C₃ ^ 2).
На предыдущем шаге мы выбрали два фрукта, но не определили, кому что достанется. Если учитывать порядок раздачи фруктов, комбинаций станет в два раза больше:
- Если берем яблоко и грушу, есть два варианта — яблоко Наташе и груша Даше (или наоборот)
- Если берем яблоко и банан, есть два варианта — яблоко Наташе и банан Даше (или наоборот)
- Если берем грушу и банан, есть два варианта — грушу Наташе и банан Даше (или наоборот)
В этом случае работает формула для размещений, которая учитывает не только возможные наборы фруктов, но и перестановки внутри каждого набора:
A₃ ^ 2 = 2 * 3 = 6
Как и другие комбинации, размещения могут быть с повторениями. В этой ситуации мы можем выбрать любой объект многократно — от множества не убудет. Если применять повторения к задаче с фруктами выше, то Наташа и Даша могут получить по яблоку, груше или банану, их фрукты не обязаны отличаться.
Попробуем разобрать более сложную задачу и выяснить, сколько существует четырехзначных пин-кодов. Размещения с повторениями считаются по такой формуле:
Pₙ ^ m = n ^ m
По условию нам предложен набор из n = 10 цифр, из которых выбираются m = 4 цифры и располагаются в определенном порядке. При этом цифры в выборке могут повторяться. Получается, что из 10 цифр можно составить 10000 четырехзначных кодов:
P₁₀ ^ 4 = 10 ^ 4 = 10000
Правила работы с комбинациями
Для начала рассмотрим правило сложения комбинаций. Знак + следует понимать как союз ИЛИ. Вспомним задачу с яблоком, грушей и бананом:
C₃ ^ 1 + C₃ ^ 2 + C₃ ^ 3 = 3 + 3 + 1 = 7
Есть семь способов выбрать хотя бы один фрукт. Другими словами, можно взять 1 любой фрукт ИЛИ любое сочетание 2 фруктов ИЛИ все 3 фрукта. Сложение комбинаций предполагает безразличие выбора — нам без разницы, сколько фруктов мы выберем.
Рассмотрим еще одни пример: группа состоит из 23 танцоров, среди них есть 10 парней и 13 девушек. Сколькими способами можно выбрать двух человек одного пола?
Формула количества сочетаний C₂3 ^ 2 не подойдет, потому что множество комбинаций из двух человек включается в себя и разнополые пары. Условие «выбрать двух человек одного пола» подразумевает, что нужно выбрать двух парней или двух девушек.
Посчитаем такие сочетания по отдельности, а потом сложим:
C₁₀ ^ 2 = (10!)/(8! * 2!) = (8! * 9 * 10)/(8! * 2!) = (9 * 10)/2 = 45возможных комбинаций из двух парнейC₁₃ ^ 2 = (13!)/(11! * 2!) = (11! * 12 * 13)/(11! * 2!) = (12 * 13)/2 = 78возможных комбинаций из двух девушекC₁₀ ^ 2 + C₁₃ ^ 2 = 45 + 78 = 123возможные комбинации из двух человек одного пола
Перейдем к правилу умножения комбинаций. Знак * следует понимать как союз И.
Рассмотрим ту же группу студентов и посчитаем, сколько разнополых пар можно составить:
C₁₀ ^ 1 = 10способами можно выбрать одного парняC₁₃ ^ 1 = 13способами можно выбрать одну девушкуC₁₀ ^ 1 * C₁₃ ^ 1 = 10 * 13 = 130способами можно составить разнополую пару
Еще есть принцип подсчета комбинаций. Когда из каждого множества выбирается по одному объекту, то работает следующий принцип подсчета комбинаций:
Каждый объект из одного множества может составить пару с каждым объектом другого множества
Другими словами, Олег может пригласить на танец любую из 13 девушек, аналогичный выбор есть и у остальных парней, поэтому можно составить 10 * 13=130 возможных пар. Отметим, что в этом примере не имеет значения упорядоченность пары.
Но попробуем поменять задачу и учесть инициативу от девушек. Тогда количество комбинаций нужно удвоить, потому что каждая из 13 девушек тоже может пригласить на танец каждого из 10 юношей.
Рассмотрим еще один пример подсчета комбинаций и выясним, сколько трехзначных чисел можно разделить на 5:
- В разряд сотен можно записать любую из
C₉ ^ 1 = 9цифр — ноль не годится, потому что тогда число перестает быть трехзначным - В разряд десятков можно выбрать любую из 10 цифр:
C₁₀ ^ 1 = 10 - По условию число должно делиться на 5, то есть заканчиваться на 5 или ноль – значит, в младшем разряде можно выбрать одну из двух цифр
- В итоге, существует
C₉ ^ 1 * C₁₀ ^ 1 * 2 = 9 * 10 * 2 = 180трехзначных чисел, которые делятся на 5
Если вас заинтересовала комбинаторика, вы можете самостоятельно изучить еще один термин из нее — комбинаторный взрыв. Так описывают ситуацию, когда мы видим резкий «взрывной» рост временной сложности алгоритма при увеличении размера входных данных задачи.
Выводы
Повторим ключевые выводы этого урока:
- Комбинаторика изучает способы подсчета возможных комбинаций вещей или вариантов выбора
- Выделяют перестановки, сочетания и размещения
- Повторение – это наличие нескольких объектов одного типа: например, одинаковых букв в слове
- Комбинаторный взрыв – это резкое увеличение временной сложности алгоритма при увеличении размера входных данных задачи
Дополнительные материалы
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
