КОМБИНАТОРНЫЙ АНАЛИЗ
комбинаторная
математика, комбинаторика, отдел математики, в к-ром изучаются вопросы,
связанные с размещением и взаимным расположением частей конечного множества
объектов произвольной природы (а также бесконечных множеств, удовлетворяющих
нек-рым условиям конечности).
Идеи комбинаторного характера имеют
самое широкое распространение в математике, в таких её разделах, как теория
вероятностей, теория чисел, алгебра и др. Задачи К. а. известны уже с глубокой
древности. В развитие К. а. большой вклад внесли многие математики. Однако
в самостоятельную науч. дисциплину К. а. стал оформляться лишь в 20 в.
К. а. тесно связан с теорией графов,
теорией конечных автоматов и др. отраслями математики. Его результаты применяются
при планировании и анализе науч. экспериментов, кодировании сообщений,
в линейном и динамич. программировании, в матем. экономике и мн. др. областях
науки и техники.
Различают три типа проблем К. а.
Задачи на перечисление. В задачах
такого типа интересуются количеством возможных размещений, удовлетворяющих
различным условиям, конечного множества объектов. Одним из типичных примеров
такого рода задач является задача о размещении к.-л. п частиц в
N
ячейках;
как частицы, так и ячейки могут быть различимыми и неразличимыми, и это
обусловливает различные ответы на поставленную задачу. Для решения разнообразных
перечислительных задач, встречающихся на практике, разработаны мощные методы;
среди них основные - метод производящих функций и метод перечисления Пойа.
Задачи о существовании и построении.
В задачах такого рода интересуются, существует ли конфигурация частей конечного
множества, обладающая нек-рыми заданными свойствами, и если да, то как
её построить. Напр., существует ли такая система подмножеств (блоков )
данного
конечного множества, что любые два различных элемента множества встречаются
вместе в этих блоках заданное число раз. Такие системы наз. блок-схемами.
Они и им подобные конфигурации интенсивно изучаются в К. а. При этом большую
роль играют теоретико-числовые и алгебраич. методы.
Задачи о выборе. В задачах этого
типа исследуются условия, при к-рых можно осуществить такой выбор подмножества
или нек-рой совокупности частей множества, чтобы удовлетворялись нек-рые
требования, носящие чаще всего оптимальный характер. Напр., пусть дано
множество и имеется нек-рая система подмножеств; при каких условиях можно
выбрать по одному элементу в каждом подмножестве так, чтобы все эти элементы
были попарно различны? Это - задача о системе различных представителей
для системы подмножеств. При решении задач о выборе, наряду с чисто комбинаторными
соображениями, также существенно применяется алгебраич. аппарат.
Лит.: Риордан Дж., Введение
в комбинаторный анализ, пер. с англ., М., 1963; Райзер Г. Д ж.. Комбинаторная
математика, пер. с англ., М., 1966. В. Е. Тараканов.
А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я