РАЗМЕЩЕНИЯ БЕЗ СОСЕДЕЙ

Аннотация

В настоящей работе мы рассматриваем некоторые задачи из комбинаторного анализа, связанные с размещениями без соседей на графах, а именно, мы находим количества и вероятности таких размещений на простейших графах (отрезок, два отрезка, цикл), а также (это более трудно) такие же задачи для цикла с точностью до поворота.

Полный текст

Пусть Γ - конечный граф с множеством вершин V , без петель и двойных ребер. Пусть L(V ) - множество функций на V со значениями 0 и 1 , назовем их размещениями. Размещением без соседей мы называем такую функцию, что в соседних вершинах она не может одновременно принимать значение 1 . Пусть S(Γ) - множество таких функций. Для конечного множества A через |A| обозначаем количество элементов в нем. Пусть n = |V | .