|
|
Большая Советская Энциклопедия (цитаты)
|
|
|
|
|
Комбинаторный анализ | Комбинаторный анализ (далее К) комбинаторная математика, комбинаторика, отдел математики, в котором изучаются вопросы, связанные с размещением и взаимным расположением частей конечного множества объектов произвольной природы (а также бесконечных множеств, удовлетворяющих некоторым условиям конечности).
Идеи комбинаторного характера имеют самое широкое распространение в математике, в таких ее разделах, как теория вероятностей, теория чисел, алгебра и др. Задачи К известны уже с глубокой древности. В развитие К большой вклад внесли многие математики. Однако в самостоятельную научную дисциплину К стал оформляться лишь в 20 в.
К тесно связан с теорией графов, теорией конечных автоматов и другими отраслями математики. Его результаты применяются при планировании и анализе научных экспериментов, кодировании сообщений, в линейном и динамическом программировании, в математической экономике и многих других областях науки и техники. Различают три типа проблем К Задачи на перечисление. В задачах такого типа интересуются количеством возможных размещений, удовлетворяющих различным условиям, конечного множества объектов. Одним из типичных примеров такого рода задач является задача о размещении каких-либо n частиц в ячейках; как частицы, так и ячейки могут быть различимыми и неразличимыми, и это обусловливает различные ответы на поставленную задачу. Для решения разнообразных перечислительных задач, встречающихся на практике, разработаны мощные методы; среди них основные - метод производящих функций и метод перечисления Пойа.
Задачи о существовании и построении. В задачах такого рода интересуются, существует ли конфигурация частей конечного множества, обладающая некоторыми заданными свойствами, и если да, то как ее построить. Например, существует ли такая система подмножеств (блоков) данного конечного множества, что любые два различных элемента множества встречаются вместе в этих блоках заданное число раз. Такие системы называют блок-схемами. Они и им подобные конфигурации интенсивно изучаются в К При этом большую роль играют теоретико-числовые и алгебраические методы.
Задачи о выборе. В задачах этого типа исследуются условия, при которых можно осуществить такой выбор подмножества или некоторой совокупности частей множества, чтобы удовлетворялись некоторые требования, носящие чаще всего оптимальный характер. Например, пусть дано множество и имеется некоторая система подмножеств; при каких условиях можно выбрать по одному элементу в каждом подмножестве так, чтобы все эти элементы были попарно различны? Это - задача о системе различных представителей для системы подмножеств. При решении задач о выборе, наряду с чисто комбинаторными соображениями, также существенно применяется алгебраический аппарат.
Лит.: Риордан Дж. Введение в комбинаторный анализ, пер. с англ., М., 1963; Раизер Г. Дж. Комбинаторная математика, пер. с англ., М., 1966.
В. Е. Тараканов. |
Для поиска, наберите искомое слово (или его часть) в поле поиска
|
|
 |
 |
 |
|
