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

Комбинаториката може да се събере в няколко основни правила.

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

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

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

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

Пермутации на N–елемента

Пермутации от N–елемента се наричат такива съединения, във всяко от които влизат всички дадени елементи и се различават само по реда на елементите. Броят на всички възможни начини на подреждане на N–елементи т.е. броя на пермутациите от N–елемента се означава с Pn.

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

Pn = 1.2.3.4....(n - 1)n. Произведението 1.2.3....(n - 1).n е прието да се означава с n! и се четe „ен факториел“
Рn = n!
0! = 1

Вариации от N–елемента k-ти клас

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

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

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

броя на вариациите:

без повторение от n елемента от k-ти клас е:

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

Комбинации от n-елемента k-ти клас

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

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

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

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

Вижте още

Източници

Philippe Flajolet, Robert Sedgewick - Analytic Combinatorics, Cambridge University Press, 2008
S. E. Payne - Applied Combinatorics, University of Colorado, 2003
Albert Nijenhuis, Herbert S. Wilf - Combinatorial Algorithms, Academic Press Inc, 1978
Linfan Mao - Combinatorial Geometry with Application to Field Theory, InfoQuest, 2009
Deirdre Haskell, Anand Pillay, Charles Steinhorn - Model Theory, Algebra and Geometry, Cambridge University Press , 2000
Louis J. Billera, at al. - New Perspectives in Algebraic Combinatorics, Cambridge University Press, 1999
Anthony Hilton and John Talbot - Surveys in Combinatorics

Външни препратки