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

Слово «комбінаторика» походить від латинського combina – поєднувати, сполучати. Це розділ математики, що вивчає дискретні об’єкти, безлічі (поєднання, перестановки, розміщення і перелік елементів) і відносини на них.

Для формулювання і рішення комбінаторних завдань використовують різні моделі комбінаторних конфігурацій. Найбільш уживані комбінаторні конфігурації

Число розміщень. Число упорядкованих різних k елементів деякого n-елементного безлічі. Позначається Ank, і обчислюється за формулою:
Ank = n! / (N – k)!
Тут і далі символ n! (Читається n факторіал) позначає твір всіх натуральних чисел від 1 до n включно. Вважається, що 0! = 1! = 1.

Число перестановок. Число різних способів, якими може бути впорядковане n-елементне безліч. Позначається Pn, і обчислюється за формулою: Pn = n !.
Число сполучень. Довільний k-елементне підмножина n-елементного безлічі. Порядок елементів не важливий. Позначається Cnk, обчислюється за формулою:
Cnk = n! / (K! (N – k)!)
Залежність між числом розміщень, перестановок і поєднань виражається формулою Ank = CnkPk.

Існує два основних правила, використовувані при рішення задач комбінаторики.

Правило суми: нехай об’єкт A можна вибрати m способами, а об’єкт B – n способами, і існує k загальних способів вибору об’єктів A і B одночасно, тоді один з об’єктів A або B можна вибрати (m + n – k) способами.
Правило твори: нехай об’єкт A можна вибрати m способами, а об’єкт B – n способами, причому вибір B не залежить від вибору A, тоді пару об’єктів A і B можна вибрати m * n способами.
Комбінаторика розвивалася паралельно з іншими математичними теорія, такими як алгебра, теорія чисел, теорія ймовірно, з якими комбинаторика тісно пов’язана. Ще у 2 столітті до нашої ери математикам Індії були відомі формули обчислюють число поєднань. Народження комбінаторики як математичного розділу пов’язано з роботами Блеза Паскаля і П’єра Ферма, що поклали основу теорії ймовірності. Ці праці містили принципи визначення числа комбінацій елементів кінцевого безлічі, тим самим встановлюючи зв’язок комбінаторики з теорією ймовірності.

Поняття «комбінаторика» було введено Г. Лейбніцем в 1666 році в роботі «Роздуми про комбинаторном мистецтві», в якій так само наводиться наукове пояснення теорії поєднань і перестановок. Великий внесок у розвиток комбінаторики мали роботи Я. Бернуллі, присвячені теорії ймовірності, в яких викладені деякі комбінаторні поняття і вказані їх застосування до обчислення ймовірностей. Бернуллі так само вперше займався вивчення числа розміщень.

В середині 20 століття відроджується інтерес до комбінаторики в зв’язку з розвитком дискретної математики і кібернетики, а так само в зв’язку з широким використанням комп’ютерів.

Комбінаторика – один з розділів дискретної математики, який придбав велике значення в зв’язку з використанням його в теорії ймовірностей, математичній логіці, теорії чисел, обчислювальній техніці, кібернетиці. Так само вона знаходить застосування в багатьох інших областях наук: в біології, де вона займається вивченням складу білків і ДНК, в хімії, фізики, економіки, механіки складних споруд і т.д.

...
ПОДІЛИТИСЯ:

Дивіться також:
Візантійський іконопис