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

Трябва ли да знаеш колко различни петорки карти можеш да изтеглиш от тесте от 32 карти? Точно такива задачи решава комбинаториката. Има две основни комбинаторни правила – за събиране и за умножение. Всички останали методи са само разширение на тези основни принципи.

Комбинаторно правило за събиране

Правилото за събиране е съвсем просто. Казва ни, че ако имаме множества A, B, които нямат общ елемент, то броят на всички възможни начини да изберем един елемент от обединението A ∪ B е равен на |A| + |B|, т.е. на сбора от броя на елементите на множествата.

Ще започнем с лесен пример. Имаме 6 червени и 8 сини топки. Изсипваме ги в една урна. Колко възможности имаме общо, ако теглим една топка? В началото имахме множество от червените топки, което ще означим с A, и множество от сините топки, което ще означим с B. Тези множества са непресичащи се, т.е. нямат нито една обща топка. Искаме да изтеглим една топка, затова имаме общо |A| + |B| = 6 + 8 = 14 възможности. Това е всичко.

Комбинаторно правило за умножение

Отново имаме две множества – Ж и М. Множеството Ж съдържа три жени, а множеството М – четирима мъже. Сега питаме колко различни двойки мъж–жена можем да образуваме от тези множества. Опитваме се да направим следното: всеки път вземаме една жена и ѝ намираме някой мъж. Броят на всички двойки ще пресметнем така: вземаме една жена, Катя, и последователно ѝ съпоставяме всички мъже. Получаваме 4 различни двойки, защото можем да ѝ съпоставим общо 4 различни мъже. Същото правим и за останалите две жени – и те образуват по 4 двойки. Това е всичко, имаме общо 4 + 4 + 4 = 12 двойки.

Какво всъщност направихме? Умножихме броя на елементите на двете множества. Имахме 3 жени и 4 мъже, така че общият брой двойки е 3 · 4 = 12. Затова правилото се нарича комбинаторно правило за умножение. Ако имаме две множества, от които образуваме двойки, просто умножаваме броя на елементите на първото множество по броя на елементите на второто.

Можеш и да се увериш, че това наистина е така. Ето всички двойки, които можем да образуваме от 3 жени и 4 мъже. Всеки ред представя възможностите за една от жените, а всяка колона – възможностите за един от мъжете. Така имаме три реда и четири колони, т.е. общо редове · колони възможности.

$$\begin{array}{rcl}& & ({Ж}_1;{М}_1),({Ж}_1;{М}_2),({Ж}_1;{М}_3),({Ж}_1;{М}_4),\\ & & ({Ж}_2;{М}_1),({Ж}_2;{М}_2),({Ж}_2;{М}_3),({Ж}_2;{М}_4),\\ & & ({Ж}_3;{М}_1),({Ж}_3;{М}_2),({Ж}_3;{М}_3),({Ж}_3;{М}_4)\end{array}$$

Решени примери

1. Колко различни двуцифрени числа съществуват? Как изглежда такова двуцифрено число? На първо място стои една от цифрите 1, …, 9, а на второ място може да има и нула: 0, …, 9. В първото множество имаме 9 цифри, във второто – 10. Прилагаме комбинаторното правило за умножение и получаваме крайния резултат: 9 · 10 = 90.

• Колко различни трицифрени числа съществуват, ако никоя цифра не може да се повтаря? На първо място отново може да стои една от девет цифри, защото числото не може да започва с нула. На второ място може да стои всяка цифра, включително нулата, но не и цифрата от първата позиция, затова от десетте възможни цифри изваждаме едната (например ако трицифреното ни число започва с цифрата 4, ясно е, че на втората позиция не може отново да има 4, защото иначе тя би се появила в числото два пъти). На трето място отново може да стои всяка цифра, но не и цифрата от първата или от втората позиция. Причината е същата. Ако на първо място е цифрата 4, а на второ – 7, то на третото място можем да поставим една цифра от {0, …, 9} ∖ {4, 7}. От общо десетте цифри трябва да извадим две. Сега остава само да умножим 9 · 9 · 8 = 648. Общо такива числа са 648.
• Хвърляме два пъти поред обикновен зар. Колко различни резултата можем да получим? При първото хвърляне на зара могат да се паднат 6 различни резултата. При второто – също, затова общият брой възможности е 6 · 6 = 36.
• Хвърляме два пъти зар. Колко различни резултата можем да получим, ако при първото хвърляне се е паднало четно число? При първото хвърляне се е паднало четно число, т.е. едно от числата 2, 4, 6, което прави общо 3 възможности. При второто хвърляне може да се падне произволно число, затова общо имаме 3 · 6 = 18 възможности.