Cтраница 3
В этом примере строится и исследуется алгоритм решения комбинаторных перечислительных задач для ( 0 1) - матриц с заданными количествами единиц в строках и столбцах. [31]
Для получения производящих функций в комбинаторике широко применяются алгебры формальных степенных рядов и различные символич. Ниже в качество примера даны построения алгебр инцидентности и показано, как с их помощью решаются нек-рые перечислительные задачи. [32]
Функциональные уравнения возникают в перечислительных задачах тогда, когда в результате последовательных операций строятся объекты, число которых нужно найти. Будем рассматривать функциональные уравнения вида F ( z, ш) 0, которые определяют функцию w ( z) неявно. Перечислительные задачи теории графов являются основным источником таких уравнений. [33]
Имеются результаты в направлении возможной унификации методов перечисления, связанные с рассмотрением так наз. При решении перечислительных задач существенную роль играет формализация понятия неразличимости объектов. Использование для этих целей понятия эквивалентности объектов относительно нек-рой группы подстановок в сочетании с применением метода производящих функций было положено в основу так наз. Сущность этой теории состоит в следующем. [34]
Для чтения этого обзора не требуется обширных сведений из анализа и комбинаторики: необходимы лишь элементарный анализ для первой части и основы теории функций комплексной переменной для второй. Доказательства некоторых асимптотических формул приведены или потому, что автор не мог найти их в литературе, или по той причине, что доказательства иллюстрируют обсуждаемые асимптотические методы. Для понимания доказательств и примеров требуется некоторое знакомство с перечислительными задачами. Комбинаторные результаты приводятся обычно без доказательств. [35]
Асимптотики для специалиста в области комбинаторики являются одновременно и более широким, и более узким предметом, чем для специалиста по анализу. Более широким, поскольку имеется много перечислительных задач, которые никто не может сформулировать в виде, допускающем применение аналитических методов. Более узким, поскольку в комбинаторике нас интересуют только суммы и функции, возникающие из перечислительных задач. Из-за этой узости лишь ограниченная часть аппарата, разработанного в анализе, пригодна для рассмотрения большинства перечислительных задач. Насколько известно, пока не существует обзора асимптотик с этой точки зрения. Мун [38] обсуждает некоторые асимптотики для графов, главным образом в последней главе. Здесь будет приведен обзор асимптотических методов, наиболее подходящих для теории перечислений. [36]
В статье изучаются блоковые коды с целочисленными координатными символами, предназначенные для исправления аддитивных, ошибок некоторых типов. Коды определяются проверочным уравнением над конечной абелевой группой и, таким образом, являются обобщением кодов Варшамова и Константина - Рао. Основные результаты статьи касаются корректирующей способности, включая метод декодирования обобщенных кодов Варшамова, и главным образом связаны с перечислительными задачами. Получена общая формула для нумератора спектра; она применена к кодам Варшамова и Константина - Рао. [37]
Асимптотики для специалиста в области комбинаторики являются одновременно и более широким, и более узким предметом, чем для специалиста по анализу. Более широким, поскольку имеется много перечислительных задач, которые никто не может сформулировать в виде, допускающем применение аналитических методов. Более узким, поскольку в комбинаторике нас интересуют только суммы и функции, возникающие из перечислительных задач. Из-за этой узости лишь ограниченная часть аппарата, разработанного в анализе, пригодна для рассмотрения большинства перечислительных задач. Насколько известно, пока не существует обзора асимптотик с этой точки зрения. Мун [38] обсуждает некоторые асимптотики для графов, главным образом в последней главе. Здесь будет приведен обзор асимптотических методов, наиболее подходящих для теории перечислений. [38]
Отправляясь от его формул, сравнительно просто удалось перечислить корневые графы, связные графы и ориентированные графы. А когда были временно исчерпаны все легкие перечислительные задачи, мы опубликовали статью, содержавшую 27 нерешенных задач перечисления. К настоящему времени почти половина этих задач решена, а последовательные пересмотры первоначального списка 27 нерешенных задач перечисления регулярно публиковались. Современное состояние дел в этой области отражено в заключительной главе данной книги. Хотя Эйлер и решил ряд задач перечисления для некоторых типов триангулированных многоугольников, расположенных на плоскости, все же существенные шаги в теории перечисления графов были сделаны лишь в девятнадцатом столетии. [39]
Отправляясь от его формул, сравнительно просто удалось перечислить корневые графы, связные графы и ориентированные графы. А когда были временно исчерпаны все легкие перечислительные задачи, мы опубликовали статью, содержавшую 27 нерешенных задач перечисления. К настоящему времени почти половина этих задач решена, а последовательные пересмотры первоначального списка 27 нерешенных задач перечисления регулярно публиковались. Современное состояние дел в этой области отражено в заключительной главе данной книги. Хотя Эйлер и решил ряд задач перечисления для некоторых типов триангулированных многоугольников, расположенных на плоскости, все же существенные шаги в теории перечисления графов были сделаны лишь в девятнадцатом столетии. [40]
На практике эти результаты наиболее полезны при исследовании целых функций. Результаты Хеймана проще и более удовлетворительны. Прежде чем приводить его чисто техническое определение, в теореме 6 будет дано рекуррентное описание подкласса класса допустимых целых функций. Это позволит охватить больше допустимых производящих функций, чем нужно для перечислительных задач. [41]