Cтраница 2
Главное отличие этих двух таблиц состоит в том, что приводимая ниже таблица не имеет опечаток. Таблица для числа ( р, д) - графов была впервые напечатана в книге Риордана [1], стр. [16]
Приближенное выражение может быть получено на основе чисел Стирлинга или многочленов Бэлла, свойства которых указаны Риорданом [ 1958, стр. В двоичном случае выбор w тг / 2 приводит к относительно простой рекурсии. [17]
Риордан значительно помог мне советами и с выдержкой и тактом исправлял мои погрешности в английском языке. Кестену, который критически просмотрел большую часть рукописи и исправил там потрясающее количество ошибок. [18]
Аналогичные задачи можно сформулировать для слонов и коней. Можно рассмотреть и такие вариации рассмотренных задач, которые определяются выбором формы доски, например прямоугольной, L-образной, треугольной. Более интересной задачей с точки зрения теории перечисления является задача о нахождении числа различных ладейных многочленов, определенных в книге Риордана [1], стр. [19]
Ладья является самой распространенной фигурой в комбинаторных задачах на шахматной доске и часто упоминается даже в серьезной математической литературе. Что общего, скажем, между шахматным термином ладья и чисто математическим понятием многочлен. Риордан 23 как раз применяет термин ладейный многочлен. Оказывается, большой класс важных комбинаторных задач сводится к подсчету числа тех или иных расстановок ладей на шахматной доске. [20]
Производящая функция, рассматриваемая как цельный объект, может обладать такими свойствами, которые трудно и противоестественно записать в терминах отдельных коэффициентов ряда и которые даже совсем не имеют места для отдельно взятого коэффициента. Этим объясняется кажущийся парадокс: ряд задач на подсчет удается решить только после вышеупомянутого усложнения их постановки. Общий подход к нахождению считающих рядов и их производящих функций был впервые предложен Пойя [180]; сам автор применил свою основную теорему для подсчета количества неизоморфных деревьев с заданным числом вершин и выделенной вершиной ( корнем), а также для определения количества изомеров у некоторых химических соединений. Подробное изложение теоремы Пойя и разнообразных ее применений имеется в книге Риордана [52], однако для первого ознакомления мы рекомендуем статью Харари [133], в которой без введения большого числа понятий даются формулировка этой теоремы и ее непосредственные приложения, такие как подсчет графов и диграфов ( направленных графов) с заданными количествами вершин и ребер, подсчет связных графов и некоторых взвешенных графов. Из работ этого направления, появившихся в период между выходом оригинала книги Риордана ( 1958 г.) и 1962 годом, отметим работу Рида [185, 186]; доказанная им теорема суперпозиции позволяет значительно расширить сферу применимости теоремы Пойя, например, дает возможность подсчитывать количество неизоморфных графов с заданными степенями вершин. [21]
Производящая функция, рассматриваемая как цельный объект, может обладать такими свойствами, которые трудно и противоестественно записать в терминах отдельных коэффициентов ряда и которые даже совсем не имеют места для отдельно взятого коэффициента. Этим объясняется кажущийся парадокс: ряд задач на подсчет удается решить только после вышеупомянутого усложнения их постановки. Общий подход к нахождению считающих рядов и их производящих функций был впервые предложен Пойя [180]; сам автор применил свою основную теорему для подсчета количества неизоморфных деревьев с заданным числом вершин и выделенной вершиной ( корнем), а также для определения количества изомеров у некоторых химических соединений. Подробное изложение теоремы Пойя и разнообразных ее применений имеется в книге Риордана [52], однако для первого ознакомления мы рекомендуем статью Харари [133], в которой без введения большого числа понятий даются формулировка этой теоремы и ее непосредственные приложения, такие как подсчет графов и диграфов ( направленных графов) с заданными количествами вершин и ребер, подсчет связных графов и некоторых взвешенных графов. Из работ этого направления, появившихся в период между выходом оригинала книги Риордана ( 1958 г.) и 1962 годом, отметим работу Рида [185, 186]; доказанная им теорема суперпозиции позволяет значительно расширить сферу применимости теоремы Пойя, например, дает возможность подсчитывать количество неизоморфных графов с заданными степенями вершин. [22]
В формуле Кэли подсчитывается число всех деревьев с данными п вершинами. Многие из них изоморфны, и возникает вопрос о числе не изоморфных среди них. Это - более трудная задача, но она очень важна для многих приложений. По этому и по аналогичным вопросам, связанным с перечисленном всех не изоморфных графов частных типов, существует обширная литература. Большинство этих работ опирается на общий пршщшг, сформулированный Пойа. Полный анализ таких задач о перечислении вывел бы пас за рамки этой книги; читатель может обратиться к блестяще написанной книге Риордана. [23]