Комбинаторика
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
Комбинаториката е сред най-старите и силно развити дялове на математиката и по-специално на дискретната математика. Основен обект, с който се занимава комбинаториката, е комбинаторната конфигурация. В областта на комбинаториката са се оформили две проблеми области: изброителна комбинаторика и структурна комбинаторика.
За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. |
Ако елементът а може да бъде избран по 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, тогава и само тогава, когато к = р.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.