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

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

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

Основни правила на комбинаториката[редактиране | edit source]

Правило за събиране[редактиране | edit source]

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

Правило за умножение[редактиране | edit source]

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

Пермутации[редактиране | edit source]

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

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

Вариации[редактиране | edit source]

Определение и примери[редактиране | edit source]

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

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

Решение: V27= 7.6 = 42

Формула за броя на вариациите[редактиране | edit source]

Броят на различните вариации от n елемента от k-ти клас се означава с Vkn. Vkn = n.(n - 1).(n - 2)....(n - (k - 1)) - е броят на вариациите без повторение от n елемента от k-ти клас е: Vnk = n.(n - 1).(n - 2)...(n – k + 1). От определенията на пермутациите и вариациите следва, че пермутациите на n елемента могат да се разглеждат като вариации от n елемента от n-ти клас.

            n.(n - 1).....(n — k + 1) = Vkn=n!/(n-k)!; k ≤ n

Комбинации[редактиране | edit source]

Определение и примери[редактиране | edit source]

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

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

Решение: P(20,3) = 20.19.18 = 6840 P(15,2) = 15.14 = 210 P(20,3)/3!.P(15,2)/2! = (210.6840)/12 =1436400/12 = 119700 начина

Формула за броя на комбинациите[редактиране | edit source]

Броят на различните комбинации без повторение от n-елемента от k-ти клас се означава с C(n,k) или Ckn. Броят на комбинациите от 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)

Изброителна комбинаторика[редактиране | edit source]

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

Принципи на изброителната комбинаторика[редактиране | edit source]

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

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