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

Комбинаториката е сред най-старите и силно развити дялове на математиката и по-специално на дискретната математика. Основен обект, с който се занимава комбинаториката, е комбинаторната конфигурация. В областта на комбинаториката са се оформили две проблеми области: изброителна комбинаторика и структурна комбинаторика.

Основни правила на комбинаториката

Правило за събиране

Ако елементът а може да бъде избран по m начина, a елементът b по n различни начина, изборът на „а или b“ може да се извърши по m + n начина. Правилото за събиране може да се обобщи за повече от две множества. Трябва броят на всички обекти да е равен на сбора от броя им в отделните групи.

Правило за умножение

Ако елементът а може да бъде избран по m начина и при всеки избор на а елементът b може да бъде избран по n начина, то изборът на наредената двойка (а,b) може да стане по m.n начина. Правилото за умножение може да се обобщи за намиране броя на наредени тройки обекти, наредени четворки обекти.

Пермутации

 Основна статия: Пермутация

Пермутация без повторение наричаме конфигурация от ${\displaystyle n}$-елементно множество, от което трябва да изберем всичките ${\displaystyle n}$ елемента, като редът е от значение. Броят на конфигурациите е ${\displaystyle n!}$ (ен факториел) и има стойност ${\displaystyle n!=n.(n-1).(n-2)...3.2.1}$.

Прост пример за една комбинаторна задача е: „По колко начина може да се нареди едно тесте от n карти?“. Отговорът е ${\displaystyle n!}$.

Пермутация с повторение наричаме съединение на ${\displaystyle n}$-елемента от ${\displaystyle n}$ – елементно множество, като редът е от значение, при което някои елементи от множеството могат да се повтарят в съединението. Броят на всичките конфигурации е ${\displaystyle n}$^{${\displaystyle n}$}. Например конфигурациите на нуклеотидните бази в генома могат да се представят като пермутации с повторение от 4-елементно множество: AAAA, ACGT, TTAC и т.н. Техните конфигурации са 256 на брой.

Вариации

 Основна статия: Вариация

Определение и примери

Вариациите без повторение на n елемента от k-ти клас (k < n) се наричат такива съединения, всяко от които съдържа по k различни елемента от дадените n и се различават едно от друго или по елементите, или по реда на елементите. Разликата между вариациите и пермутациите на елементите на някакво множество е единствено в това, че в една вариация не е задължително да участват всички елементи на множеството. Ясно е, че всяка пермутация е вид вариация (от n елемента n-ти клас), докато обратното не е вярно.

Пример: В дисциплината троен скок на световното първенство по лека атлетика участват 8 състезателки. По колко различни начина могат да се разпределят златния, сребърния и бронзовия медал, ако се знае, че представителката на България със сигурност ще вземе златния медал?

Решение: ${\displaystyle V_{7}^{2}={\frac {7!}{\left(7-2\right)!}}=42}$

Формула за броя на вариациите

Броят на различните вариации от ${\displaystyle n}$ елемента от ${\displaystyle k}$-ти клас се означава с ${\displaystyle V_{n}^{k}}$. ${\displaystyle V_{n}^{k}={\frac {n!}{\left(n-k\right)!}}}$ е броят на вариациите без повторение от ${\displaystyle n}$ елемента от ${\displaystyle k}$-ти клас.

От определенията на пермутациите и вариациите следва, че пермутациите на ${\displaystyle n}$ елемента могат да се разглеждат като вариации от ${\displaystyle n}$ елемента от ${\displaystyle n}$-ти клас.

Комбинации

 Основна статия: Комбинация (математика)

Определение и примери

Комбинации без повторение от n-елемента от k-ти клас се наричат такива съединения, всяко от които съдържа по k различни елемента от дадените n и се различават едно от друго с поне 1 елемент.

Пример: В един клас има 20 ученика и 15 ученички. За изпълнение на дадена задача на класа трябва да изберат 5 ученика, от които 3 момчета и 2 момичета. Намерете по колко различни начина може да стане този избор.

Решение:$${\displaystyle V_{20}^{3}={\frac {20!}{(20-3)!}}={\frac {20!}{17!}}=20\cdot 19\cdot 18=6840}$$$${\displaystyle V_{15}^{2}={\frac {15!}{(15-2)!}}={\frac {15!}{13!}}=15\cdot 14=210}$$$${\displaystyle {\frac {V_{20}^{3}}{3!}}\cdot {\frac {V_{15}^{2}}{2!}}={\frac {210\cdot 6840}{12}}={\frac {210\cdot 6840}{12}}={\frac {1436400}{12}}=119700}$$Отговор: Изборът може да стане по 119700 начина.

Формула за броя на комбинациите

Броят на различните комбинации без повторение от n-елемента от k-ти клас се означава с C(n,k) или C^k_n.

Броят на комбинациите от n-елемента от k-ти клас е:

$${\displaystyle C_{n}^{k}={\frac {V_{n}^{k}}{P_{k}}}={\frac {n\cdot ({n-1})\cdot ({n-2})\cdots ({n-k+1})}{k(k-1)\cdots 3\cdot 2\cdot 1}}}$$

Изброителна комбинаторика

Основен проблем на изброителната комбинаторика е по зададено множество и правила за комбиниране, да се намери броя на получаващите се комбинаторни конфигурации. Разглеждат се правила, при които комбинаторните конфигурации да бъдат краен брой.

Принципи на изброителната комбинаторика

Принцип на чекмеджетата (принцип на Дирихле) Нека Х е множество с к елемента (които ще наричаме предмети), а У е множество от р елемента (които ще наричаме чекмеджета) и к > р. Както и да поставим всички предмети в чекмеджетата, поне в едно чекмедже ще има поне два предмета.

Принцип на биекцията Нека Х и У са крайни множества, |X| = k и |Y| = р. Съществува биекция f: X->Y, тогава и само тогава, когато к = р.