Направо към съдържанието

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

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

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

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

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

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

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

Ако елементът а може да бъде избран по 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, тогава и само тогава, когато к = р.