Комбінаторний аналіз - Енциклопедія Сучасної України
Beta-версія
Комбінаторний аналіз

КОМБІНАТО́РНИЙ АНА́ЛІЗ – розділ математики, присвяче­ний вирішенню завдань вибору та розміщення елементів деякої, зазвичай скінченної множини відповідно до заданих правил. Результат такого вибору називають комбінатор. конфігурацією. Метою К. а. є вивчення ком­бінатор. конфігурацій, алгоритмів їхньої побудови, оптимізації таких алгоритмів, а також визна­чення кількості конфігурацій пев­ного класу. Гол. частину К. а. ста­новлять методи безпосеред. під­рахунку кількості конфігурацій, метод твір. функцій, логічні, екс­тремал., геом. та ін. методи. При підрахунку кількості комбінатор. конфігурацій важливу роль відіграє правило множення (осн. принцип К. а.): якщо дію А можна здійснити m способами, а дію B – n способами, то заг. кількість усіх способів послідов. здій­снен­ня дій A і B дорівнює m • n. Найпростішими прикладами комбінатор. конфігурацій є розміщен­ня, перестановки, комбінації. Як­що з множини M, що складаєть­ся з n елементів, послідовно по одному вибирають m елементів, то одержані набори (відрізняють­ся один від одного або елемента­ми, або їхнім порядком) нази­ва­ють розміщеннями з n елементів по m. Кількість таких роз­міщень

Розміщення з n елементів по n називають перестановками. Їхня кількість

Комбінації з n елементів по m – це всі можливі m-елементні під­множини з M; їхня кількість

Виникнення осн. понять і розвиток К. а. відбувалися паралель­но зі становленням тісно по­в’я­заних із ним галузей математики, зокрема алгебри, чисел теорії та ймовірностей теорії. Його зародження пов’язують із працями франц. учених Б. Паскаля (1623–62) і П. Ферми (1601–65) з теорії азарт. ігор, що й скла­ли основу теорії ймовірностей і одночасно містили принципи підрахунку кількості комбінацій елементів скінчен. множини. Вста­новлений ними зв’я­зок між К. а. і теорією ймовірностей не­­вдовзі став традиційним. Знач. внесок у систематич. розви­ток комбінатор. методів зро­били нім. учений Г.-В. Лейбніц (1646–1716) і швейцар. математик Я. Бер­нуллі (1654–1705). Вони ввели низку комбінатор. по­нять з їхнім застосуванням до об­числень ймовірностей, що призвело до виділення комбіна­тор. методів у самост. розділ ма­тематики. Пізніше рос. учений швейцар. походження Л. Ейлер (1707–83) започаткував один з осн. методів перерахунку комбі­натор. конфігурацій – метод твір. функцій. Особливий інтерес до К. а. науковці почали проявляти у 1950-х рр. у зв’язку з бурхливим розвитком кібернетики та дискрет. математики (див. Диск­ретний аналіз) і широким вико­ристанням електронно-обчислюв. техніки. Саме у цей період активізувалася зацікавленість класич. комбінатор. задачами. Нині К. а. використовують у багатьох комп’ютер. науках, напр., для побудови й аналізу різноманіт. алгоритмів, знач. прогре­су досягнуто у комбінатор. вивченні опуклих многогранників, виявлено тісний зв’язок з алгеб­раїч. топологією. В Україні з роз­­витком К. а. пов’язана школа А. Скорохода з тео­рії ймовірно­­стей.

Літ.: Риордан Дж. Введение в комби­наторный анализ / Пер. с англ. Москва, 1963; Ежов И. И., Скороход А. В., Яд­­ренко М. И. Элементы комбинаторики. Москва, 1977; D. F. Knuth. The Art of Com­puter Programming. Vol. 3. Massachu­setts, 1997; R. P. Stanley. Enumerative Com­binatorics. Vol. 1, 2. Cambridge; New York, 1997; 1999; B. E. Sagan. The Sym­metric Group. Representations. Combina­torial Algorithms. New York; Berlin; Hei­delberg, 2001; B. Grünbaum. Convex Po­­lytopes. Berlin, 2003; E. Bachmat, E. D. Be­­rend, L. Sapir, S. Skiena, N. Stolyarov. Analysis of airplane boarding times // Ope­ration Research. 2009. Vol. 57; A. Björ­ner, R. P. Stanley. A Combinatorial Mis­cellany. Geneve, 2010.

В. І. Горбачук

Стаття оновлена: 2014