Вікіпедія

Комбінаторика: відмінності між версіями

Інтерактивний перегляд історії
[перевірена версія][перевірена версія]
← Попереднє редагуванняНаступне редагування →
Вилучено вміст Додано вміст
ВізуальнийВікірозмітка
Виправлено джерел: 1; позначено як недійсні: 0. #IABot (v2.0beta15)
Коректура
Рядок 7:
Термін «комбінаторика» ввів Лейбніц, який у 1666 році опублікував свою працю «Міркування про комбінаторне мистецтво».
 
Іноді під комбінаторикою розуміють більш широкийширший розділ дискретної математики, що включає теорію графів.
 
== Основні положення ==
Рядок 26:
{{Докладніше|Правило суми}}
В основі розв'язання багатьох задач комбінаторики лежать два простих правила — ''правило суми'' та ''правило добутку''.
 
''Правило суми'' стверджує, що якщо є можливість вибрати елемент з деякої множини елементів ''А'' <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>
 
Особливістю цього правила є те, що воно використовує сполучник або, який протиставляє різні дії одна одній.
Рядок 38 ⟶ 40:
'''Приклад 1'''. На денне чергування в студентському гуртожитку може піти або студент з кімнати 1, де проживають три студенти, або студент з кімнати 2, де проживають чотири студенти.
Скількома способами можна вибрати одного студента на денне чергування в гуртожитку?
 
'''''Розв'язання'''''. Загальна кількість способів, якими можна вибрати одного студента або з кімнати 1 або з кімнати 2 на денне чергування, згідно з ''правилом суми'' буде 3+4=7.
 
Рядок 47 ⟶ 50:
<p align="center" >У загальному вигляді правило Добутку буде мати такий вигляд.</p>
 
<p align="center" >''Якщо треба виконати якусь дію, що може бути виконана '''''к''''' сумісними діями, перша з яких може бути виконана n<sub>1</sub> способами, друга&nbsp;— ''n''<sub>2</sub> і&nbsp;т.&nbsp;д. до '''''к'''&nbsp;— ої''-ї дії, яку можна виконати ''n<sub>k</sub>'' способами, то основна дія може бути виконана '''''М''''' способами, де</p>
<p align="center" >'''''М'' = ''n''<sub>1</sub>•n • ''n''<sub>2</sub> •…•n• … • ''n<sub>k</sub>.''.'''</p>
<p align="center" >У цьому правилі важливу роль відіграє сполучник ''і'', який об'єднує різні дії в одну.</p>
 
'''Приклад 2'''. На денне чергування в студентському гуртожитку вибирається два студента&nbsp;— один студент зіз трьох, що проживають у кімнаті 1, і один студент зіз чотирьох, які проживають у кімнаті 2. Скільки існує можливих способів формування різних пар з двох студентів для чергування?
 
'''''Розв'язання.''''' Кількість способів чергувань двох студентів з різних кімнат відповідно до ''правила добутку'' буде 3*4=12.
 
== Історичний нарис ==
Базові поняття комбінаторики і розраховані результати з'явилися ще в [[Стародавній світ|стародавньому світі]]. В 6-му столітті до н.е., індійській [[лікар]] {{нп|Сушрута||en|Sushruta}} в праці [[Сушрута Самхіта]] наводить, що із 6-ти різних смаків можна утворити 63 різні комбінації, якщо спочатку взяти по одному, потім поєднати по два, і т. д., таким чином знайшов всі 2<sup>6</sup>&nbsp;&minus;&nbsp;1 можливих комбінацій. [[Стародавня Греція|Грецький]] [[історіограф]] [[Плутарх]] обговорює дискусію між [[Хрісіпп]]ом (3-єтє століття до .н. е.) і [[Гіппарх]]ом (2-еге століття до н. е.) досить делікатної задачі нумерації, згодом було показано що вона тісно пов'язана із {{нп|Числа редера-Гіппарха|числами редера-Гіппарха|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-етє століття до н. е.) розглядає {{нп|головоломку із черепицею||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
Рядок 77 ⟶ 81:
|archivedate = 2011-05-14
|deadurl = yes
}}</ref>.
 
Остаточно комбінаторика як самостійний розділ математики оформилася в працях [[Леонард Ейлер|Ейлера]]. Він детально розглянув, наприклад, такі проблеми:
* [[задачаЗадача про хід коня]];
* [[сім мостів Кеніґсберґа|Задача семи мостів Кеніґсберґа]], з якої почалася [[теорія графів]];
* побудоваПобудова {{нп|Греко-латинський квадрат|греко-латинських квадратів||Graeco-Latin square}};
* [[числа Ейлера I роду|Узагальнені перестановки]].
 
Крім перестановок і поєднань, Ейлер вивчав [[Розбиття числа|розбиття]], а також поєднання і розміщення з умовами.
Рядок 110 ⟶ 114:
|ref =
}} {{ref-uk}}
* Комбінаторика : Навч. посіб. для студ. вищ. навч. закл. / В. М. Бушмакін, В. К. Гануліч, А. З. Мохонько, С. І. Томецька, Н. М. Тимошенко; Нац. ун-т "«Львів. політехніка"». -— Л., 2002. -— 195 c. -— (Сер. "«Математика для інженерів"»; N№ 8). -— Бібліогр.: 16 назв.
* {{книга
|автор = [[Базилевич Лідія Євгенівна|Л.Є. Базилевич]]
Отримано з https://uk.wikipedia.org/wiki/Комбінаторика