Основни методи и формули на комбинаториката
Комбинаторика (от латинскисombinare- свързвам, комбинирам) - дял от математиката за избора и подреждането на елементи от определено множество въз основа на определени условия.
Комбинаторните проблеми могат да бъдат решени чрез три основни метода: изброяване на всички възможни варианти, логически метод и използване на схема (виж по-долу). В зависимост от задачата, методите могат да бъдат различни, но комбинаторната задача може да бъде решена с всеки от трите посочени метода.
Нека да разгледаме примерите за използване и на трите метода.
Аз. Изброяване на възможните опции.
Този метод е директно да предоставите всички възможни опции и след това да ги преброите.
Пример: Дадени са три карти с числа 1,1,2. Колко от тях могат да бъдат числа?
Нека прегледаме всички възможни числа, които могат да бъдат направени с помощта на посочените карти с числа (удобно е да ги изпишете във възходящ ред, в този случай има по-малък шанс да загубите някоя опция).
Получаваме: 1; 2; единадесет; 12; 112; 121; 211. Така получаваме седем варианта.
Забележка: Този метод се използва рядко, тъй като с голям брой опции е много трудоемък, нерационален и позволява голям брой грешки, ако поне един случай е загубен при изброяването.
Понякога е удобно методът за изброяване да се форматира катодърво с възможни опции.
Пример. Колко различни трицифрени числа могат да се съставят от цифрите 1, 3, 5, 7, като всяка от тях се използва не повече от веднъж в записа?
| Първа цифра | 1 | 3 | 5 | 7 | ||||||||
| Втора цифра | 3 | 5 | 7 | 1 | 5 | 7 | ||||||
| Трета цифра | 5 7 | 3 7 | 3 5 | 5 7 | 17 | 15 | … | … | … | … | … | … |
Получаваме 24 опции (броя на числата в третия ред или броя на клоните отгоре).
В този случай обикновено след първия "ствол" на дървото става ясно как бързо да получите резултата: първият ствол съдържа 6 клона, има общо 4 ствола, следователно общо 6 4 = 24 начина.
II. Булев метод.
Логичният метод е, забелязвайки някои модели, да преброим броя на начините, като избягваме изброяването на всички опции.
Пример: Има пет карти с числа 1, 2, 3, 4, 5. Колко трицифрени числа могат да бъдат направени от тях?
По конвенция номерът се състои от три цифри. На първо място можете да поставите всяка от петте (т.е. получаваме пет начина), на второ място можете да поставите една от четирите цифри (тъй като една вече е на първо място), на трето една от трите останали цифри. Тъй като с всяка карта можете да разгледате всички опции за други карти, за да получите общия брой опции, трябва да умножите всичко (комбинаторно правило за умножение), тоест 5 × 4 × 3 = 60. По този начин получаваме, че общо 60 различни трицифрени числа могат да бъдат направени при тези условия.
Като цяло,правилото за комбинаторно умножение се формулира, както следва:
Нека имаnелемента и се изисква да изберете някоиkелемента един по един. Ако първият елемент може да бъде избран поn1начина, след което вторият елемент може да бъде избран от останалите елементи поn2начина, след това третият елемент поn3начина и т.н., тогава броят на начините, по които всичкиkелемента могат да бъдат избрани, е равен на произведението отn1 n2 ...nk.
Забележка: Логическият метод за решаване на комбинаторни задачи е най-често използваният.