Перегляд вихідного коду сторінки Комбінаторика

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

Найпростішими прикладами комбінаторних конфігурацій є [[перестановка|перестановки]], [[Розміщення (комбінаторика)|розміщення]], [[Комбінація (комбінаторика)|комбінація]] та розбиття.

Комбінаторика пов'язана з багатьма іншими розділами математики.

Термін «комбінаторика» ввів [[Готфрід Вільгельм Ляйбніц|Ляйбніц]], який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво».

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

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

З комбінаторикою мають справу хіміки при вивченні різних можливих типів зв'язків атомів у молекулах; біологи, наприклад, у процесі знаходження послідовностей амінокислот у білкових сполуках; кібернетики при розв'язанні задач кодування й побудові обчислювальних пристроїв, математики&nbsp;— при розв'язанні багатьох різних задач, особливо в теорії ймовірності. Також комбінаторику використовують у своїх моделях фізики, архітектори, економісти й представники багатьох інших наук.

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

Після розв'язання першої задачі комбінаторики розв'язується не менш важлива ''друга''&nbsp;— задача ''переліку'' комбінаторних об'єктів, які відповідають вихідним правилам їх побудови. Саме на розв'язання цієї задачі спрямовані сьогодні зусилля багатьох учених. Є досить багато задач, які так чи інакше стосуються цієї загальної задачі. Наприклад, до неї належить питання про кількість різних способів, якими можна розмістити групу студентів з 30 чоловік на 30 чи більше місцях, або про кількість способів проведення матчів з футболу між 10 різними командами?

Далі на основі отриманих розв'язків конкретних задач з переліку комбінаторних об'єктів розв'язується ''третя'' задача комбінаторики&nbsp;— це її побудова. Наприклад, потрібно не лише підрахувати кількість можливих варіантів розподілу 30 студентів на 30 місцях, а й побудувати всі ці розподіли або деякі з них у вигляді їх комбінаторних конфігурацій. Також може виникнути потреба побудувати таблицю матчів між 10 футбольними командами, а не тільки знати їх кількість.

''Четверта'' і остання задача комбінаторики&nbsp;— це задача про пошук серед комбінаторних конфігурацій такої, яка б приводила деяку функцію до ''оптимуму''. Це на сьогодні досить нелегка для розв'язання загальна задача. Вона містить задачі ''комбінаторної оптимізації'', наприклад, [[Задача комівояжера|задачу комівояжера]], яка на сьогодні ще не має остаточного розв'язання.

=== Правило суми ===
{{Докладніше|Правило суми}}
В основі розв'язання багатьох задач комбінаторики лежать два простих правила&nbsp;— ''правило суми'' та ''правило добутку''.

''Правило суми'' стверджує, що якщо є можливість вибрати елемент з деякої множини елементів ''А'' <math>n</math> способами, а елемент з множини ''В'', яка не має спільних елементів з множиною ''А'',&nbsp;— <math>k</math> способами, то вибрати елемент множини ''А'' або елемент множини ''В'' можна <math>n+k</math> способами.

Це правило зручно продемонструвати з допомогою такої моделі. Якщо маємо дві урни і в одній з них знаходиться <math>n</math> куль, а в іншій <math>k</math>, то кількість способів, якими можна буде вийняти кулю з тієї чи іншої урни, дорівнюватиме <math>n+k</math>. Дійсно, з першої урни кулю можна вийняти <math>n</math> способами, але якщо з першої урни кулю не виймати, то тоді з другої урни її можна вийняти <math>k</math> способами. Тому загальна кількість способів, якими можна вийняти одну кулю з двох урн, буде дорівнювати <math>n+k</math>.

У загальному випадку правило суми може бути сформульоване таким чином.

<p align="center">Якщо треба виконати якусь дію ''n''<sub>1</sub> , ''n''<sub>2</sub>, … або ''n<sub>k</sub>'' способами, то кількість можливих способів реалізації цієї дії буде дорівнювати</p>
<p align="center">'''''N = n<sub>1</sub> + n<sub>2</sub> + … + n<sub>k</sub>.'''''</p>

Особливістю цього правила є те, що воно використовує [[сполучник]] ''або'', який протиставляє різні дії одна одній.

'''Приклад 1'''. На денне чергування в студентському гуртожитку може піти або студент з кімнати 1, де проживають три студенти, або студент з кімнати 2, де проживають чотири студенти.
Скількома способами можна вибрати одного студента на денне чергування в гуртожитку?

'''''Розв'язання'''''. Загальна кількість способів, якими можна вибрати одного студента або з кімнати 1 або з кімнати 2 на денне чергування, згідно з ''правилом суми'' буде 3+4=7.

=== Правило добутку ===
{{докладніше|Правило множення}}
''Правило добутку'' використовується тоді, коли кожний елемент множини ''А'' може бути вибраний разом з елементом множини ''В''. Відповідно до кожного способу вибору елемента множини ''А'' буде зіставлятися <math>k</math> способів вибору елемента множини ''В''. Тоді загальна кількість способів сумісного вибору елементів множини ''А'' з елементами множини ''В'', очевидно, дорівнюватиме <math>n\cdot k</math>.

Модель урн можна застосувати і для ілюстрації правила добутку. У цьому випадку розглядаються дві урни, у першій з яких знаходиться <math>n</math> куль, а в другій <math>k</math>. Будемо вважати, що будь-якій кулі першої урни може відповідати будь-яка куля з другої урни. ''А'' оскільки в першій урні знаходиться <math>n</math> куль, то й кількість способів вибору куль з першої урни разом з різними кулями з другої урни буде дорівнювати <math>n\cdot k</math>.
<p align="center" >У загальному вигляді правило Добутку буде мати такий вигляд.</p>

<p align="center" >Якщо треба виконати якусь дію, що може бути виконана '''''к''''' сумісними діями, перша з яких може бути виконана n<sub>1</sub> способами, друга&nbsp;— ''n''<sub>2</sub> і&nbsp;т.&nbsp;д. до '''''к'''''-ї дії, яку можна виконати ''n<sub>k</sub>'' способами, то основна дія може бути виконана '''''М''''' способами, де</p>
<p align="center" >'''''М'' = ''n''<sub>1</sub> • ''n''<sub>2</sub> • … • ''n<sub>k</sub>''.'''</p>
<p align="center" >У цьому правилі важливу роль відіграє сполучник ''і'', який об'єднує різні дії в одну.</p>

'''Приклад 2'''. На денне чергування в студентському гуртожитку вибирається два студента&nbsp;— один студент із трьох, що проживають у кімнаті 1, і один студент із чотирьох, які проживають у кімнаті 2. Скільки існує можливих способів формування різних пар з двох студентів для чергування?

'''''Розв'язання.''''' Кількість способів чергувань двох студентів з різних кімнат відповідно до ''правила добутку'' буде 3*4=12.

== Історичний нарис ==
Базові поняття комбінаторики і розраховані результати з'явилися ще в [[Стародавній світ|стародавньому світі]]. В 6-му столітті до н.&nbsp;е., індійській [[лікар]] [[Сушрута]] в праці [[Сушрута Самхіта]] наводить, що із 6-ти різних смаків можна утворити 63 різні комбінації, якщо спочатку взяти по одному, потім поєднати по два, і&nbsp;т.&nbsp;д., таким чином знайшов всі 2<sup>6</sup>&nbsp;&minus;&nbsp;1 можливих комбінацій. [[Стародавня Греція|Грецький]] [[історіограф]] [[Плутарх]] обговорює дискусію між [[Хрісіпп]]ом (3-тє століття до н.&nbsp;е.) і [[Гіппарх]]ом (2-ге століття до н.&nbsp;е.) досить делікатної задачі нумерації, згодом було показано що вона тісно пов'язана із {{нп|Числа редера-Гіппарха|числами редера-Гіппарха|en|Schröder–Hipparchus number}}<ref>[[Richard P. Stanley|Stanley, Richard P.]]; «Hipparchus, Plutarch, Schröder, and Hough», ''American Mathematical Monthly'' '''104''' (1997), no. 4, 344—350.</ref><ref>Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; «On the Second Number of Plutarch», ''American Mathematical Monthly'' '''105''' (1998), no. 5, 446.</ref>. У своїй праці ''{{нп|Остомахіон||en|Ostomachion}}'' [[Архімед]] (3-тє століття до н.&nbsp;е.) розглядає {{нп|головоломка на замощення|головоломку на замощення|en|tiling puzzle}}.

[[Джироламо Кардано]] написав математичне дослідження [[Гральні кубики|гральних кубиків]], опубліковане посмертно. Теорією цієї гри займалися також [[Нікколо Тарталья|Тарталья]] і [[Галілео Галілей|Галілей]]. В історію зароджуваної [[Теорія ймовірностей|теорії ймовірностей]] увійшло листування запеклого гравця Шевальє де Мере з [[П'єр Ферма|П'єром Ферма]] і [[Блез Паскаль|Блезем Паскалем]], де було порушено кілька тонких комбінаторних питань. Крім азартних ігор, комбінаторні методи застосовувалися (і продовжують застосовуватися) в [[Криптографія|криптографії]]&nbsp;— як для розробки шифрів, так і для їх зламу.

[[Файл: PascalTriangleAnimated2.gif|thumb|251px|[[Трикутник Паскаля]]]]
[[Блез Паскаль]] багато займався [[Біноміальний коефіцієнт|біноміальними коефіцієнтами]] і відкрив простий спосіб їх обчислення: «[[трикутник Паскаля]]». Хоча цей спосіб був уже відомим на Сході (приблизно з X століття), Паскаль, на відміну від попередників, суворо виклав і довів властивості цього трикутника. Поряд з [[Ґотфрід Вільгельм Лейбніц|Лейбницем]], він вважається основоположником сучасної комбінаторики. Сам термін «комбінаторика» придумав Лейбніц, який [[1666]] року (йому було тоді 20 років) опублікував книгу «Міркування про комбінаторне мистецтво». Щоправда, термін «комбінаторика» Лейбніц розумів надмірно широко, включаючи до нього всю скінченну математику і навіть логіку{{sfn|Виленкин Н. Я.|1975|с=19}}. Учень Лейбніца [[Якоб Бернуллі]], один із засновників теорії ймовірностей, виклав у своїй книзі «Мистецтво припущень» ([[1713]] року) безліч відомостей із комбінаторики.

У цей же період формується термінологія нової науки. Термін «[[Комбінація (комбінаторика)|комбінація]]» ({{lang-en|combination}}) вперше зустрічається у [[Блез Паскаль|Паскаля]] ([[1653]] року, опубліковано [[1665]] року). Термін «[[перестановка]]» ({{lang-en|permutation}}) вжив у зазначеній книзі [[Якоб Бернуллі]] (хоча епізодично він зустрічався і раніше). Бернуллі використовував і термін «[[Розміщення (комбінаторика)|розміщення]]» ({{lang-en|arrangement}}).

Після появи [[Математичний аналіз|математичного аналізу]] було виявлено тісний зв'язок комбінаторних і ряду аналітичних задач. [[Абрахам де Муавр]] і [[Джеймс Стірлінг]] знайшли формули для апроксимації [[факторіал]]у<ref name="O'Connor">{{cite web
 |url         = http://www-history.mcs.st-andrews.ac.uk/Biographies/De_Moivre.html
 |title       = Abraham de Moivre
 |accessdate  = 2010-05-31
 |last        = O'Connor
 |first       = John
 |coauthors   = Edmund Robertson.
 |year        = 2004
 |month       = 06
 |work        = The MacTutor History of Mathematics archive
 |archiveurl  = https://web.archive.org/web/20110514221314/http://www-history.mcs.st-andrews.ac.uk/Biographies/De_Moivre.html
 |archivedate = 2011-05-14
 |deadurl     = yes
}}</ref>.

Остаточно комбінаторика як самостійний розділ математики оформилася в працях [[Леонард Ейлер|Ейлера]]. Він детально розглянув, наприклад, такі проблеми:
* [[Задача про хід коня]]
* [[сім мостів Кеніґсберґа|Задача семи мостів Кеніґсберґа]], з якої почалася [[теорія графів]]
* Побудова {{нп|Греко-латинський квадрат|греко-латинських квадратів||Graeco-Latin square}}
* [[числа Ейлера I роду|Узагальнені перестановки]]

Крім перестановок і поєднань, Ейлер вивчав [[Розбиття числа|розбиття]], а також поєднання і розміщення з умовами.

== Див. також ==
{{Портал|Математика}}
* [[Дискретна математика]]
* [[Алгебрична комбінаторика]]
* [[Теорема Ділуорса]]
* [[Бієктивне доведення]]

== Література ==

=== Українською ===
* {{Вишенський.Перестюк.Комбінаторика}}
* Комбінаторика: Навч. посіб. для студ. вищ. навч. закл. / В.&nbsp;М.&nbsp;Бушмакін, В.&nbsp;К.&nbsp;Гануліч, А.&nbsp;З.&nbsp;Мохонько, С.&nbsp;І.&nbsp;Томецька, Н.&nbsp;М.&nbsp;Тимошенко; Нац. ун-т «Львів. політехніка».&nbsp;— Л., 2002.&nbsp;— 195 c.&nbsp;— (Сер. «Математика для інженерів»; №&nbsp;8).&nbsp;— Бібліогр.: 16 назв.
* {{книга
 |автор          = [[Базилевич Лідія Євгенівна|Л.Є. Базилевич]]
 |частина        = 
 |заголовок      = Дискретна математика у прикладах і задачах : теорія множин, математична логіка, комбінаторика, теорія графів
 |посилання      = 
 |видання        = Математичний практикум
 |відповідальний = 
 |місце          = [[Львів]] 
 |видавництво    = 
 |рік            = 2013
 |том            = 
 |сторінки       = 
 |сторінок       = 486
 |isbn           = 9789662645095
 |ref            =
}} {{ref-uk}}
* {{книга
 |автор          = [[Лариса Валентинівна Павлова|Л.В. Павлова]], [[Роман Львович Дітчук|Р.Л. Дітчук]]
 |частина        = 
 |заголовок      = Елементи комбінаторики і стохастики : навчально-методичний посібник
 |посилання      = 
 |видання        = Підручники і посібники
 |відповідальний = 
 |місце          = [[Тернопіль]] 
 |видавництво    = 
 |рік            = 2005
 |том            = 
 |сторінки       = 
 |сторінок       = 159
 |isbn           = 9660702396
 |ref            =
}} {{ref-uk}}

=== Іншими мовами ===
* {{cite book | last1=Chen | first1=Chuan-Chong | last2=Koh | first2=Khee-Meng  | authorlink2= |title= Principles and Techniques in Combinatorics | edition= | publisher=World Scientific Publishing Company| location=Singapore | year=1992 | pages=312 | isbn=978-9810211394}} {{ref-en}}
* {{cite book | last1=van Lint | first1=Jacobus Hendricus | last2=Wilson | first2=Richard Michael  | authorlink2= |title= A course in combinatorics | url=https://archive.org/details/courseincombinat0002lint | edition=Second | publisher=Cambridge University Press| location=Cambridge, UK | year=2001 | pages=620 | isbn=978-0521006019}} {{ref-en}}
* {{cite book | last1=Grimaldi | first1=Ralph |title= Discrete and Combinatorial Mathematics: An Applied Introduction | edition=Fourth | publisher=Addison Wesley Publishing Company| location=| year=1998 | pages=896 | isbn=978-0201199123}} {{ref-en}}
* {{cite book | last1=Graham | first1=Ronald L. | authorlink1=| last2=Knuth | first2=Donald E. | authorlink2=Дональд Кнут | last3=Patashnik|first3=Oren| authorlink3= |title= Concrete Mathematics | edition=Second | publisher=Addison-Wesley Professional| location=Reading, MA | year=1994 | pages=xiv+657 | isbn=0-201-55802-5}} {{ref-en}}
* {{cite book | last1=Anderson | first1=James A. |title= Discrete Mathematics with Combinatorics | edition=First | publisher=Prentice Hall| location=| year=2000 | pages=799 | isbn=978-0130869982}} {{ref-en}}
* {{книга |автор=Судоплатов С. В, Овчинникова Е. В. |заголовок=Элементы дискретной математики |місце= |видавництво=НГТУ |рік=2002 |isbn=5-7782-0332-2}} {{ref-ru}}
* {{книга |автор=Виленкин Н.Я. |заголовок=Популярная комбинаторика |місце=М. |видавництво=Наука |рік=1975 |ref=Виленкин Н. Я.}} {{ref-ru}}

== Примітки ==
{{reflist}}

== Джерела ==
{{refbegin}}
* {{cite book|
title=Элементы дискретной математики|
author=Судоплатов С. В., Овчинникова Е. В.|
year=2002|
publisher=НГТУ|
isbn=5-7782-0332-2}}

{{-}}
{{math-stub}}
{{Математика-footer}}
{{Інформатика}}

[[Категорія:Комбінаторика|*]]
[[Категорія:Розділи математики]]