Комбинаторика

Комбинаторика наука, которая может рассматриваться как независимый элемент знания возможных комбинаций и их числовой расчет Комбинаторика используется как базис для расчета вероятности.

Удовлетворить потребности теории вероятности можно посредством основных формул комбинаторики, которые подразделяются по комбинациям на операции размещения, сочетания, перестановки, размещение с повторением, сочетания с повторением и перестановки с повторением. Рассмотрим подробнее базовые формулы комбинаторики.

Теорема перестановки

Если необходимо определить количество комбинаций при перестановки известного числа элементов, то используется формула перестановки: необходимо найти произведение количества всех элементов.

Например: существует компьютерная мышь, работающая от одной батарейки, имеется с виду одинаковых 4 батарейки. При этом две из них пустые, одна из них на половину израсходована, последняя новая. Цель — заменить батарейки, так чтобы мышь заработала. Подсчитаем количество возможных комбинаций при переборе батареек:

Всего 4 батарейки: 4*3*2*1=24. Таким образом, у нас есть 24 способа перебрать существующие батарейки. Сокращенно такой пример записывается так: 4!=24

Теорема размещения

Когда необходимо решить вопрос с размещением используются две величины — общего количества элементов и необходимого числа элементов. В данном случае выбор происходит последовательно и важен порядок.

Для расчета возможного числа комбинаций используется правило перестановки.

Пример: берем условие из прошлой задачи, но меняем аппаратную часть, теперь у нас компьютерная мышь нуждается в двух работающих батарейках, при этом для первого слота необходима полностью работающая батарейка, тогда подсчитаем количество возможных комбинаций:

4!/(4-2)!=4!/2!=24/2=12

В результате у нас имеется 12 способов перебрать батарейки для поиска двух необходимых.

Теорема сочетания

Когда необходимо определить количество комбинаций без повторений, вне зависимости от порядка используется метод сочетания.

Пример: немного изменим условия задачи — имеется компьютерная мышь, работающая от двух батареек, имеется 4 батарейки, две из которых работающие. Пронумеруем батарейки от 1 до 4 и подсчитаем количество возможных комбинаций. Не будет необходимости путать батарейки, а запоминаем их и переберем (!) каждую по одному разу.

4!/(2!*(4-2)!=24/4=6

По итогу выходит 6 возможных комбинаций перебора батареек.

Размещение с повторением

Если необходимо рассчитать количество возможных комбинаций при условии повторения счетного количества разных элементов используется размещение с повторением. Для этого подсчитывается количество элементов и возможных способов выбора, затем вводим число элементов в степень отражающих количество выбора.

Рассмотрим на живом примере, пусть имеется некоторое количество (стремящееся к бесконечности) карточек 10 различных цветов и 3 формы. Определим количество способов заполнения этих форм карточками, для этого возведем количество цветов в степень количества форм:

103=10*10*10=1000

Таким образом, существует 1000 различных способов заполнить формы исходя из 10 различных цветов с учетом безграничного количества фигур и их сочетаний

Сочетание с повторением

Если необходимо выяснить число возможных комбинаций в условиях компоновки элементов с повторениями используют следующую формулу. В числителе определяют сумму элементов и сочетаний минус 1, в знаменателе рассчитывают произведение элементов и сочетаний минус 1.

Рассмотрим живой пример. В кондитерской изготавливают 3 вида тянучек, 4 вида шоколадных конфет и 2 вида леденцов. Сколько вариантов конфетных букетов можно составить при условии, что в одном букете может быть всего 7 элементов.

Подсчитаем итоговое количество сладостей: 9 видов сладостей, 7 элементов в букете:

(9+7-1)!/7!*(9-1)!=15!/7!*8!=3*5**1*/1*1*1*1*1*1*1=429*15=6435

В итоге из такого немногочисленного набора сладостей можно получить 6435 разных букетов, при условии повторений.

Перестановка с повторением

Если необходимо определить количество возможных комбинаций в условиях перестановки с повторениями, то используется другая формула. Рассмотрим ее на предыдущем примере: имеем 3 вида тянучек, 4 вида шоколадных конфет и 2 вида леденцов. Сколько вариантов конфетных букетов можно составить при условии, что в одном букете может быть всего 7 элементов, при этом леденец может быть один, тянучек 2, конфет 4.

7!/(1!*2!*4!)=105

В результате выяснилось, что при сочетании определенного количества сладостей из трех групп можно получить 105 видов сладких букетов, при этом сладости одного вида в букете могут повторяться.