Cтраница 2
В наше время нередко случается, что при решении перечислительных задач переоткрываются многие известные теоремы теории перечисления. Это происходит в основном из-за плохой информированности исследователей, работающих в смежных областях естествознания. [16]
Наличие эффекта замещения у функциональных групп лишь незначительно усложняет перечислительную задачу. При этом достаточно, кроме типов звеньев, различать их рода ( см. разд. II зависит энергия молекулы. [17]
Для расчета термодинамических характеристик в рамках этой модели достаточно иметь решение чисто перечислительной задачи о числе способов А ( 1, Ъ) размещения на решетке графов с заданными числами / и Ъ вершин и ребер. Точное решение этой и даже более простых задач о числе А ( Г) или А ( Ъ) размещений графов, характеризуемых лишь одним из параметров I или 6, на реальных решетках не получено. [18]
Ранее были введены некоторые рекуррентные соотношения и продемонстрирована их роль при решении перечислительных задач. Здесь будет сформулирован общий метод рекуррентных соотношений. [19]
ПЕРЕЧИСЛЕНИЯ ТЕОРИЯ - раздел комбинаторного анализа, в к-ром изучаются и разрабатываются методы решения перечислительных задач. Эти задачи, как правило, сводятся к подсчету числа элементов конечного множества, обладающих определенными свойствами, или их классов эквивалентности. К таким методам относятся, напр. Теория перечисления Пойа ( см. Пойа теорема) часто позволяет преодолевать трудности при подсчете разных объектов, когда их приходится рассматривать как неразличимые. [20]
Исходная идея авторов этой работы заключается в констатации того факта, что во многих случаях успех при решении перечислительной задачи определяется не тем или иным специально придуманным приемом, а естественной порядковой структурой перечисляемых объектов. [21]
Настоящая статья представляет собой обзор тех методов асимгр-тотического анализа, которые особенно полезны при получении асимптотических результатов в перечислительных задачах. Полезность различных методов иллюстрируется на многих примерах. Предполагается, что явно или неявно заданы сумма или производящая функция последовательности ап. [22]
В случае вероятностного пространства с равномерным распределением, рассматриваемые задачи, несмотря на вероятностную терминологию, по существу представляют собой перечислительные задачи комбинаторного анализа. Вероятностный подход в этих случаях обеспечивает удобную форму представления и помогает привлекать методы асимптотического анализа, хорошо развитые в теории вероятностей. [23]
Принципиальная особенность, отличающая решетку Бете от всех остальных, заключается в том, что для них не удается получить формулы типа (1.9), (1.10), которые позволили бы найти точное решение перечислительной задачи. [24]
Отношения, совместимые с порядком. В большинстве перечислительных задач требуется не полная алгебра инцидентности, но значительно меньшая ее подалгебра. Эти подалгебры возникают при выборе подходящих отношений эквивалентности на сегментах локально конечного упорядоченного множества Р и последующем рассмотрении функций, которые принимают одинаковые значения на эквивалентных сегментах. Поэтому мы приходим к следующему. [25]
Вместо того чтобы вводить на таком множестве линейный порядок, во многих случаях бывает полезнее применить технику, учитывающую естественный ( комбинаторный) порядок множества. При этом подходе возникает ряд перечислительных задач, связанных с обращением сумм, распространяющихся на частично-упорядоченные множества. Основной тезис работы [104], как и всега цикла, заключается в том, что формула обращения Мебиуса для частично упорядоченного множества является фундаментальным, принципом перечисления. [26]
Асимптотики для специалиста в области комбинаторики являются одновременно и более широким, и более узким предметом, чем для специалиста по анализу. Более широким, поскольку имеется много перечислительных задач, которые никто не может сформулировать в виде, допускающем применение аналитических методов. Более узким, поскольку в комбинаторике нас интересуют только суммы и функции, возникающие из перечислительных задач. Из-за этой узости лишь ограниченная часть аппарата, разработанного в анализе, пригодна для рассмотрения большинства перечислительных задач. Насколько известно, пока не существует обзора асимптотик с этой точки зрения. Мун [38] обсуждает некоторые асимптотики для графов, главным образом в последней главе. Здесь будет приведен обзор асимптотических методов, наиболее подходящих для теории перечислений. [27]
Существует много конфигураций, которые не являются графами per se 2, но по своей природе - суть графические объекты. Ограниченные пространственные возможности позволяют нам указать перечислительные задачи только для некоторых из этих структур. Мы рассматриваем здесь следующие конфигурации: симплициальные комплексы, латинские квадраты, узлы, полимино, а также конфигурации на шахматной доске и замощения. [28]
Известно, что одним из наиболее полезных принципов перечисления в дискретных задачах теории вероятностей и в комбинаторном анализе является метод включения-исключения. Умелое применение метода включения-исключения дает решение многих перечислительных задач. Но на практике не всегда легко заметить возможность применения метода включения-исключения. В работе Рота [104] началось систематическое изучение очень общего принципа перечисления, для которого метод включения-исключения является простейшим частным случаем. [29]
Перечислительные задачи комбинаторики состоят в нахождении точного или приближенного выражения для числа комбинаторных объектов, обладающих требуемым свойством. В этой книге применяется вероятностный подход к перечислительным задачам. [30]