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

от Уикипедия, свободната енциклопедия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

Броят на различните вариации от елемента от -ти клас се означава с . е броят на вариациите без повторение от елемента от -ти клас.

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

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

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

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

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

Решение:

Отговор: Изборът може да стане по 119700 начина.

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

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

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

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

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

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

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

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