Комбінаторний аналіз

КОМБІНАТО́РНИЙ АНА́ЛІЗ – розділ математики, присвячений вирішенню завдань вибору та розміщення елементів деякої, зазвичай скінченної множини відповідно до заданих правил. Результат такого вибору називають комбінатор. конфігурацією. Метою К. а. є вивчення комбінатор. конфігурацій, алгоритмів їхньої побудови, оптимізації таких алгоритмів, а також визначення кількості конфігурацій певного класу. Гол. частину К. а. становлять методи безпосеред. підрахунку кількості конфігурацій, метод твір. функцій, логічні, екстремал., геом. та ін. методи. При підрахунку кількості комбінатор. конфігурацій важливу роль відіграє правило множення (осн. принцип К. а.): якщо дію А можна здійснити 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 Computer Programming. Vol. 3. Massachusetts, 1997; R. P. Stanley. Enumerative Combinatorics. Vol. 1, 2. Cambridge; New York, 1997; 1999; B. E. Sagan. The Symmetric Group. Representations. Combinatorial Algorithms. New York; Berlin; Heidelberg, 2001; B. Grünbaum. Convex Polytopes. Berlin, 2003; E. Bachmat, E. D. Berend, L. Sapir, S. Skiena, N. Stolyarov. Analysis of airplane boarding times // Operation Research. 2009. Vol. 57; A. Björner, R. P. Stanley. A Combinatorial Miscellany. Geneve, 2010.

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

Рекомендована література

Риордан Дж. Введение в комбинаторный анализ / Пер. с англ. Москва, 1963;
Ежов И. И., Скороход А. В., Ядренко М. И. Элементы комбинаторики. Москва, 1977;
D. F. Knuth. The Art of Computer Programming. Vol. 3. Massachusetts, 1997;
R. P. Stanley. Enumerative Combinatorics. Vol. 1, 2. Cambridge; New York, 1997;
1999;
B. E. Sagan. The Symmetric Group. Representations. Combinatorial Algorithms. New York; Berlin; Heidelberg, 2001;
B. Grünbaum. Convex Polytopes. Berlin, 2003;
E. Bachmat, E. D. Berend, L. Sapir, S. Skiena, N. Stolyarov. Analysis of airplane boarding times // Operation Research. 2009. Vol. 57;
A. Björner, R. P. Stanley. A Combinatorial Miscellany. Geneve, 2010.