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

Математиката на броенето

Комбинаториката е дял от математиката, който се занимава с броенето на възможностите: по колко начина може да се направи, подреди или избере нещо. Тя е изненадващо практична и стои в основата на вероятностите.

Защо просто броене не стига

Когато възможностите са малко, ги броим една по една. Но колко са подредбите на 10 книги? Над три милиона! Тук ръчното броене е невъзможно. Затова комбинаториката дава правила, които броят бързо.

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

Правилото за умножение е основно: ако едно действие може да стане по m начина, а друго (независимо) по n начина, заедно те стават по m · n начина. Например 3 тениски и 2 панталона дават 3 · 2 = 6 различни облекла.

Пример с умножението

В ресторант има 4 предястия, 5 основни и 3 десерта. По колко начина може да си съставиш меню от трите? По 4 · 5 · 3 = 60 начина. Правилото за умножение действа, когато избираме по едно от всяка група.

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

Правилото за събиране: ако избираш едно нещо ИЛИ друго (взаимно изключващи се), броят на възможностите е m + n. Например ако имаш 3 книги и 4 списания и избираш ЕДНО четиво, имаш 3 + 4 = 7 възможности.

Умножение или събиране

Кога умножаваме и кога събираме? Умножаваме, когато действията се правят заедно („и": ястие И десерт). Събираме, когато избираме едното ИЛИ другото. Разпознаването на „и"/„или" е ключово в комбинаториката.

Какво е пермутация

Пермутацията е подреждане на елементи в определен ред. По колко начина може да се подредят? Това е честа комбинаторна задача. Например по колко начина 3 деца могат да застанат в редица?

Броене на пермутации

3 деца в редица: за първото място имаме 3 избора, за второто 2 (остават), за третото 1. По правилото за умножение: 3 · 2 · 1 = 6 подредби. Виждаш как пермутациите ползват правилото за умножение.

Факториелът

Произведението 3 · 2 · 1 се записва кратко като 3! (3 факториел). Общо n! = n · (n−1) · ... · 2 · 1. Броят на подредбите на n различни елемента е точно n!. Затова факториелът расте много бързо: 10! е над 3 милиона.

Дървото на възможностите

Полезно средство е дървото на възможностите: разклонена схема, която показва всички избори стъпка по стъпка. То помага да разберем правилото за умножение нагледно: всяко разклонение е нов избор. За малки задачи дървото е удобно.

Комбинаториката и вероятностите

Комбинаториката е основата на вероятностите: за да пресметнем вероятност, често броим благоприятните и всички възможни случаи. Затова умението да броиш е първата стъпка към теорията на вероятностите, която идва по-нататък.

Внимавай за реда

Важно е дали редът има значение. При подреждане в редица (пермутации) редът е важен. При избор на отбор (без подредба) редът не е важен: тогава броим различно. Затова всеки път се питай: важен ли е редът?

Защо я изучаваме

Комбинаториката развива логическото мислене и умението да броиш системно. Тя е навсякъде: в игрите, лотариите, паролите, генетиката, информатиката. А е и основата на вероятностите. Затова е важен и интересен дял на математиката.

Около нас

Комбинаторни задачи има всеки ден: колко различни PIN-кода има, по колко начина да се подредят играчите, колко комбинации има на ключалка. Когато се чудиш „по колко начина може...", вече мислиш комбинаторно.

Подреждане без повторение

При пермутациите всеки елемент се ползва веднъж: за първото място n избора, за второто n−1 и т.н. Затова резултатът е n!. Например 5 различни книги се подреждат по 5! = 120 начина. Важно е елементите да са различни.

Избор без значение на реда

Когато избираме група, в която редът не е важен (например 3 души за комисия от 10), броим различно от пермутациите. Тогава всяка група се брои веднъж, без значение в какъв ред е избрана. Затова винаги питай: важен ли е редът?

Принципът на чекмеджетата

Красив прост принцип: ако сложиш повече предмети, отколкото чекмеджета, поне в едно чекмедже ще има повече от един предмет. Например сред 13 души поне двама са родени в един и същ месец. Това е изненадващо мощен начин за разсъждение.

Вероятностите идват

Комбинаториката е основата на вероятностите: вероятността е отношение на броя благоприятни случаи към броя на всички случаи. Затова, за да пресметнеш вероятност (например за зар или карти), първо трябва да преброиш случаите комбинаторно.

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

Комбинаторни сметки стоят зад много неща: колко сигурна е една парола (колко комбинации има), колко тиража има лотарията, колко различни ДНК комбинации са възможни. Колкото повече възможности, толкова по-малка е вероятността за случайно познаване.

Около нас

Комбинаторни въпроси има всеки ден: колко PIN-кода има (10 000 за 4 цифри); по колко начина да се подредят отборите; колко менюта може да съставиш. Когато се питаш „по колко начина може...", вече разсъждаваш като комбинаторик.

Защо я изучаваме

Комбинаториката развива системното логическо мислене и умението да броиш точно. Тя е навсякъде: в игрите, паролите, лотариите, генетиката, информатиката, а е и основата на вероятностите. Затова е важен и изненадващо практичен дял на математиката.

Кратко обобщение

Комбинаториката брои възможностите. Правило за умножение: при последователни (независими) избори броят е m · n (за „и"). Правило за събиране: при взаимно изключващи се избори е m + n (за „или"). Пермутацията е подреждане; броят на подредбите на n елемента е n! (n факториел). Реда е важен при пермутации, но не при избор без подредба.