Розділ і. Дискретна математика (Варіант 2)

Теоретичні відомості Комбінаторика (Комбінаторний аналіз) — розділ математики, присвячений розв'язанню задач вибору та розташування елементів деякої, зазвичай скінченної, множини відповідно до заданих правил. Кожне таке правило визначає спосіб побудови деякої конструкції із елементів вихідної множини, що зветься комбінаторною конфігурацією. Тому на меті комбінаторного аналізу стоїть дослідження комбінаторних конфігурацій, алгоритмів їх побудови, оптимізація таких алгоритмів, а також розв'язання задач переліку.

Найпростішими прикладами комбінаторних конфігурацій є перестановки, розміщення, комбінація та розбиття. Комбінаторика пов'язана з багатьма іншими розділами математики.

Термін «комбінаторика» ввів Лейбніц, який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво». Іноді під комбінаторикою розуміють більш широкий розділ дискретної математики, що включає теорію графів. Перестановка - це будь-яка безліч або підмножина об'єктів або подій, в якій внутрішній порядок має значення. Як правило, перестановки вважаються для заданого числа об'єктів, які вибираються із загального числа об'єктів. Традиційно, загальне число об'єктів або подій позначають N, вибиране число об'єктів або подій - K, а число перестановок з N по K позначають Pk,n. Існує формула, що дозволяє легко визначити число перестановок з N по K: Число перестановок з N по K Тут N! - факторіал числа N, тобто, твір вигляду 1*2*...*N. У Excel рахувати перестановки дуже зручно, не потрібно навіть обчислювати факторіали: =ПЕРЕСТ(N;K) Замість N і K задаються цілі позитивні числа, N?K. Наприклад, червону, синю і зелену кульки можна переставити шістьма способами: =ПЕРЕСТ(3;3) КСЗ КЗС ЗКС СЬКЗ СЗК ЗСЬК Вибрати 2 чарки з трьох, що стоять на столі, можна також шістьма способами: =ПЕРЕСТ(3;2) (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)

В комбінаториці розрізняють власне комбінації або поєднання, в цьому завданні вважається число всіх можливих поєднань N об'єктів в групи по K елементів, причому порядок елементів в групі неістотний. У тих же позначеннях, формула для визначення числа поєднаньпо K об'єктів з N має вигляд

Дуже часто число поєднань з N по K позначають як CNK. У Excel число комбінацій рахує функція =ЧИСЛКОМБ(N;K) Значення N і K також мають бути цілими і позитивними, N>= KЗ цієї точки зору вибрати 2 чарки з трьох можна всього трьома способами: =ЧИСЛКОМБ(3;2) (1,2), (1,3), (2,3).

Як відомо, згідно з класичним означенням ймовірностей, щоб обчислити ймовірність тієї чи іншої випадкової події, необхідно вміти обчислити кількість п усіх елементарних подій (розмір простору елементарних подій ) і число елементарних подій, які сприяють появі випадкової події.

У багатьох випадках для обчислення чисел і використовуються наступні елементи комбінаторики: перестановки, розміщення та комбінації, які є окремим видом сполук елементів певної множини.

Розміщення - різні впорядковані k-елементні підмножини множини з n елементів. Розміщення відрізняються один від одного або елементами, або їх порядками слідування. Приклад типового завдання на обчислення розміщень: у групі 5 дівчат і 8 хлопців. Для представництва цієї групи на конференції обирають 4 людини, яким присвоюються номери для виступу на даній конференції. Скільки різних варіантів складання такої групи можна побудувати? У даній задачі буде змінюватися як склад підмножини, так і порядок елементів даного підмножини. Тому застосовується формула для обчислення розміщень.

Комбінація - довільне k-елементне підмножина даного безлічі з n елементів. порядок елементів у поєднанні не істотний. Приклад типового завдання на поєднання: є 2 червоних і 5 жовтих тюльпанів; букет складають з 3-х квіток; скільки різних варіантів складання букета? Тут береться підмножина з 3-х елементів з безлічі, що складається з 7-ми елементів, порядок абсолютно не важливий.

Комбінаціями з елементів по ( ) називають такі множини із k елементів, взятих з даних елементів, що відрізняються між собою хоча б одним елементом без врахування їх порядку.

Кількість таких множин позначають через і знаходять поформулі

Значне число комбінаторних задач розв’язуються з використанням двох основних правил комбінаторики — правила суми та правила добутку.

Правило суми. Якщо деякий вибір А можна здійснити т різними способами, а вибір В — п способами, причому , то вибрати А або В можна способами.

Правило добутку. Якщо деякий вибір основні правила А можна здійснити т різними способами, а для кожного з цих способів деякий інший вибір В можна здійснити п способами, то вибір А і В можна здійснити способами.