Перечисления Теория

Раздел комбинаторного анализа, в к-ром изучаются и разрабатываются методы решения перечислительных задач. Эти задачи, как правило, сводятся к подсчету числа элементов конечного множества, обладающих определенными свойствами, или их классов эквивалентности. К таким методам относятся, напр., включения и исключения принцип и различные его обобщения. Теория перечисления Пойа (см. Пойа теорема).часто позволяет преодолевать трудности при подсчете разных объектов, когда их приходится рассматривать как неразличимые. Основным инструментом при решении перечислительных задач являются производящие функции; они также играют существенную роль при получении асимптотич. соотношений (см. [1] — [3]). Для получения производящих функций в комбинаторике широко применяются алгебры формальных степенных рядов и различные символич. методы (см. [1], [2], [4]). В основе общего подхода к разработке методов получения производящих функций лежит тот факт, что многие дискретные объекты обладают естественной упорядоченностью (см. [1], [5]). Ниже в качестве примера даны построения алгебр инцидентности и показано, как с их помощью решаются нек-рые перечислительные задачи. Пусть задано частично упорядоченное множество Xс отношением порядка и пусть Xлокально конечно, т. е. любой его сегмент конечен. Алгеброй инцидентности I(X).наз. совокупность функций , принимающих действительные значения и таких, что f(x, у)=0 при . Сумма двух таких функций и умножение на число определяются обычным образом, а произведение вводится соотношением Умножение оказывается ассоциативным и дистрибутивным относительно сложения. Алгебра I(X).обладает единицей В алгебре I(X).выделяют два элемента: дзета-функцию при ) и обратную ей функцию Мёбиуса m=z-1. Справедливо утверждение: если локально конечное частично упорядоченное множество Xсодержит свою наибольшую нижнюю грань, функция f(x).определена для всех и для всех , то для всех (теорема обращения Мёбиуса). Если Х=В- множество всех конечных подмножеств нек-рого счетного множества, а означает, что , то при а обращение Мёбиуса есть не что иное, как принцип включения и исключения. Если X=D — множество натуральных чисел и означает, что хделит у, то при имеем , где m(n) — теоретико-числовая Мёбиуса функция. Редуцированной алгеброй инцидентности R(X).наз. подалгебра I(Х), к-рой принадлежат все функции I(Х), принимающие равные значения на эквивалентных сегментах. При этом отношение эквивалентности сегментов обладает тем свойством, что если f(x, y)=f(u, v).и g(x, y)=g(u, v).для , то и Это будет, напр., выполняться, если эквивалентными считать изоморфные сегменты. К алгебре R(X).всегда принадлежат дзета-функция и функция Мёбиуса. Если с естественной упорядоченностью чисел, то алгебра I(N0).изоморфна алгебре верхнетреугольных бесконечных матриц. Если к R(N0) отнести все такие функции , что f(m, n) = j(m', n').при n-m=n'-m'=k, то имеет место взаимно однозначное соответствие где при n — m=k, так что Таким образом, алгебра R(N0).изоморфна алгебре формальных степенных рядов и Если Х=В, то алгебра R(В).изоморфна алгебре экспоненциальных степенных рядов и где при Если X=D и рассматриваются f(m, n)=f(m', n') при , то алгебра R(D).оказывается изоморфной алгебре рядов Дирихле и Пример. Пусть с( х, у) — число цепей вида x<x1<. . .<xl-1<y в X, тогда — число таких цепей длины k(то есть l=k). Поэтому Рассмотрим эту формулу в R(Х).при X=N0, В, D. В случае X = N0 и у-х=п число с( х, у)=с п есть число упорядоченных разбиений (композиций) п. В R(N0) полученная формула имеет вид следовательно с n=2n-1, n>0. В случае Х=В число с( х, у)=с п есть число упорядоченных разбиений re-элементного множества, и В случае X=D число с( х, у)=с п есть число упорядоченных разложений на множители п=у/х. Следова тельно, Лит.:[1] Сачков В. Н., Комбинаторные методы дискретной математики, М., 1977; [2] Риордан Д ж.. Введение в комбинаторный анализ, пер. о англ., М., 1963; L3] Перечислительные задачи комбинаторного анализа. Сб. переводов, М., 197В; [4] Rоta G.-C., Мullin R., в кн.: Graph theory and its applications, N. Y.-L., 1970, p. 167-213; [5] Rota G.-C., "Z. Wahrscheinlichkeitstheor. und verw. Geb.", 1964, Bd 2,H. 4, S. 340-68; [6] Холл М., Комбинаторика, пер. с англ., М., 1970. В. М. Михеев.