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

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

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

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

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

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

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

Пермутации

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

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

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

Вариации

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

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

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

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

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

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

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

Комбинации

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

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

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

Решение:

V(20,3) = 20.19.18 = 6840
V(15,2) = 15.14 = 210
V(20,3)/3!.V(15,2)/2! = (210.6840)/12 =1436400/12 = 119700 начина

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

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

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

 C(n,k) = Vkn/Pk
        = n!/(k!(n-k)!)
        = (n.(n – 1).(n – 2)...(n – k + 1))/(k.(k – 1)...3.2.1)

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

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

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

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

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