Большая советсткая энциклопедия Комбинаторный анализ

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

Комбинаторный анализ, комбинаторная математика, комбинаторика, отдел математики, в котором изучаются вопросы, связанные с размещением и взаимным расположением частей конечного множества объектов произвольной природы (а также бесконечных множеств, удовлетворяющих некоторым условиям конечности).

Идеи комбинаторного характера имеют самое широкое распространение в математике, в таких её разделах, как теория вероятностей, теория чисел, алгебра и др. Задачи К. а. известны уже с глубокой древности. В развитие К. а. большой вклад внесли многие математики. Однако в самостоятельную научную дисциплину К. а. стал оформляться лишь в 20 в.

К. а. тесно связан с теорией графов, теорией конечных автоматов и другими отраслями математики. Его результаты применяются при планировании и анализе научных экспериментов, кодировании сообщений, в линейном и динамическом программировании, в математической экономике и многих других областях науки и техники. Различают три типа проблем К. а. Задачи на перечисление. В задачах такого типа интересуются количеством возможных размещений, удовлетворяющих различным условиям, конечного множества объектов. Одним из типичных примеров такого рода задач является задача о размещении каких-либо n частиц в N ячейках; как частицы, так и ячейки могут быть различимыми и неразличимыми, и это обусловливает различные ответы на поставленную задачу. Для решения разнообразных перечислительных задач, встречающихся на практике, разработаны мощные методы; среди них основные — метод производящих функций и метод перечисления Пойа.

Задачи о существовании и построении. В задачах такого рода интересуются, существует ли конфигурация частей конечного множества, обладающая некоторыми заданными свойствами, и если да, то как её построить. Например, существует ли такая система подмножеств (блоков) данного конечного множества, что любые два различных элемента множества встречаются вместе в этих блоках заданное число раз. Такие системы называют блок-схемами. Они и им подобные конфигурации интенсивно изучаются в К. а. При этом большую роль играют теоретико-числовые и алгебраические методы.

Задачи о выборе. В задачах этого типа исследуются условия, при которых можно осуществить такой выбор подмножества или некоторой совокупности частей множества, чтобы удовлетворялись некоторые требования, носящие чаще всего оптимальный характер. Например, пусть дано множество и имеется некоторая система подмножеств; при каких условиях можно выбрать по одному элементу в каждом подмножестве так, чтобы все эти элементы были попарно различны? Это — задача о системе различных представителей для системы подмножеств. При решении задач о выборе, наряду с чисто комбинаторными соображениями, также существенно применяется алгебраический аппарат.

Лит.: Риордан Дж. Введение в комбинаторный анализ, пер. с англ., М., 1963; Раизер Г. Дж. Комбинаторная математика, пер. с англ., М., 1966.

В. Е. Тараканов.