Елементи на комбинаториката
| Множеството е едно от основните понятия на математиката, което не подлежи на формална дефиниция. |
| В математиката понятиетонаборсе използва за описание на колекция от обекти или обекти. Предполага се, че обектите (обектите) на дадено множество могат да бъдат разграничени един от друг и от обекти, които не са включени в това множество. Например, можем да говорим за множеството от всички книги на дадена библиотека, множеството от всички върхове на даден многоъгълник, множеството от всички естествени числа, множеството от всички точки на дадена права. Книги от дадена библиотека, върхове на даден многоъгълник, естествени числа, точки от дадена права саелементина съответните множества. |
Множествата обикновено се означават с главни букви A, B, X. Фактът, че обект a е елемент от множество A, се записва по следния начин: и се чете "a принадлежи на множество A", "a е включено в множество A". Записът означава, че a не е елемент от множеството A.
Наборът от естествени числа, разположени между числата 21 и 22, не съдържа нито едно число. Такова множество се нарича празно множество. Празното множество се означава с ∅.
Множествата A и B се наричат равни, ако са съставени от еднакви елементи. В този случай пишете
В училищния курс по математика се приема стандартната нотация за числови множества: N е множеството от естествени числа, Z е множеството от цели числа, Q е множеството от рационални числа, R е множеството от реални числа.
В този случай казваме, че множеството Aсе съдържа в множество B или множество B съдържа множество A. Ако има поне един елемент в множество A, който не принадлежи на множество B, тогава A не е подмножество на множество B:
От дефиницията на подмножество следва, че всяко множество е подмножество на себе си, тоест
За крайно множество A означаваме с m(A) броя на неговите елементи. Броят на елементите на празното множество очевидно е равен на нула. За всякакви крайни множества A и B е вярно равенството: =
| Нека има множество, съдържащо n-елемента. Всяко от неговите подредени подмножества, състоящо се от k-елементи, се наричаподреждане на n-елементи по k-елементи. |
| При комбинаторни задачи е необходимо да можете да преброите броя на всички разположения от n-елементи по k-елементи. За обозначаване на това число се използва специален символ (да се чете: „брой разположения от n до k“ или „A от n до k“. = 1. |
А е първата буква на френската дума "аранжиране", което означава "поставяне, подреждане".
Умножаваме и разделяме продукта от дясната страна на формула (1) на След това получаваме:
или (2) ако сме съгласни, че
| Разпределенията на n-елементи по n-елементи се наричат пермутации на n-елементи. |
Пермутациите са специален случай на поставяне. Тъй като всяка пермутация съдържа всички n-елементи от множеството, различните пермутации се различават една от друга само по реда на елементите.
Броят на пермутациите на n-елементите се означава с Pn. P е първата буква от френската дума "пермутация".
Наистина формула (2) дава:
Pn = = = = n!
От формула (1) намираме:
Pn = = n (n − 1) (n − 2) . (n − n + 1) = n!
И така, броят на пермутациите на n-елементи е n!.
C е първата буква на френската дума "combinasion" - "комбинация".
= (3).
Формула (3) може да бъде написана в друга, по-удобна за изчисления форма. След като намалихме числителя и знаменателя на дробта на, получаваме т.е. броят на комбинациите от n-елементи с k-елементи е равен на произведението на всички естествени числа от n до включително, делено на k!.
| Когато се решават сложни комбинаторни задачи, често се налага да се използват следните две правила. |
1. Ако някакъв избор може да бъде направен по m различни начина и за всеки от тези начини може да бъде направен някакъв избор по n различни начина, тогава броят на начините да се направи последователност от тези избори е равен на произведението от mn.