подсчёт комбинации графов

[Soul Friend]

Дано максимальное количество вершин равное $n$, и эти вершины равнозначны и равномерно расположены в двухмерном пространстве относительно друг от друга (на одинаковом радиусе по периметру круга). Максимальное количество рёбер (когда все точки соединены между собой) будет равна $\sum_{x=1}^{n-1}(x)$, но количество комбинации, когда то или иное ребро будет отсутствовать - значительно больше. И для каждой такой комбинации будет существовать ровно $(n-1)$ зеркальных (сдвинутых) отображении. Если отбросить эти зеркальные отображения и оставить только одну из них (из зеркальных отображении), то как сосчитать эти комбинации? Есть ли формула? Для $n=4$ я насчитал 13 таких комбинации:

Для $n=5$ примерно 74 таких комбинации (но не уверен, так как мог запутаться и недосчитать что-то, но их точно больше 70-ти). Для $n=3$ всего одна такая комбинация, и соответственно, для $n=0$, $n=1$ их Ноль. И ещё, есть условие что каждая вершина (точка) должна быть в паре как минимум с ещё одной вершиной (точкой). Последовательность A058380 не подходит.

[Xaositect]

Soul Friend в сообщении #1172679 писал(а):

Для $n=3$ всего одна такая комбинация

Почему? \begin{tikzpicture}\draw (-0.3,0)--(0.3,0); \draw[fill] (-0.3,0) circle(1pt); \draw[fill] (0.3,0) circle(1pt); \draw[fill] (0,0.5) circle(1pt);\end{tikzpicture} и \begin{tikzpicture}\draw (-0.3,0)--(0.3,0)--(0,0.5); \draw[fill] (-0.3,0) circle(1pt); \draw[fill] (0.3,0) circle(1pt); \draw[fill] (0,0.5) circle(1pt);\end{tikzpicture}.

Вообще, для таких вещей используется теорема Редфилда-Пойя (https://en.wikipedia.org/wiki/P%C3%B3ly ... on_theorem)

[Soul Friend]

Soul Friend в сообщении #1172679 писал(а):

И ещё, есть условие что каждая вершина (точка) должна быть в паре как минимум с ещё одной вершиной (точкой)

поэтому одна комбинация для трёх точек.
Надо бы добавить в OEIS эту последовательность хотя-бы до некоторого значения $n$.
комбинации из $n=5$ :


пока не разобрался с формулой из википедии.

[Soul Friend]

вот асимптотическая формула:

$$ (n-2)(n-1)!+(n-3)$$

только, насколько приблизительно она считает при $\,n>5$

[B@R5uk]

Soul Friend в сообщении #1172679 писал(а):

Максимальное количество рёбер (когда все точки соединены между собой) будет равна $\sum_{x=1}^{n-1}(x)$

Эта же сумма считается:

$$\frac{1}{2}n(n-1)$$

Soul Friend в сообщении #1172679 писал(а):

но количество комбинации, когда то или иное ребро будет отсутствовать - значительно больше.

Тоже считается:

$$2^{\frac{n(n-1)}{2}}$$

Однако посчитать количество симметрий (вернее честно разбить эту массу комбинаций на классы эквивалентности относительно перестановок, а их $n!$ штук) будет очень тяжело.

Soul Friend в сообщении #1172679 писал(а):

но не уверен, так как мог запутаться и недосчитать что-то

Трудно поверить, что вы на бумажке уместили и сравнили все 1024 комбинации.

Soul Friend в сообщении #1172679 писал(а):

И ещё, есть условие что каждая вершина (точка) должна быть в паре как минимум с ещё одной вершиной (точкой)

Если принципиально рассматриваете несвязные графы, то почему бы для начала это условие не опустить? Думаю, задача будет решаться легче. Если вершина не имеет ребра, то откинув её получаем ту же самую задачу с на единицу меньшим количеством рёбер. Если две вершины — то задачу с количеством рёбер, меньшим на два. То есть можно выразить одно решение через другое.

-- 30.11.2016, 08:45 --

Soul Friend в сообщении #1172679 писал(а):

Если отбросить эти зеркальные отображения и оставить только одну из них (из зеркальных отображении), то как сосчитать эти комбинации?

Только зеркальные отображения или повороты тоже не считаются? Или же совпадения при вообще любой перестановке точек (тогда располагать их на окружности не обязательно)? Если только зеркальные, то относительно какой прямой?

Если считать конфигурации одинаковыми, если они совпадают только при комбинации поворотов и зеркальной симметрии, то будет $2n$ вариантов перестановок для проверки (включая тривиальную). Думаю, что даже вплоть до семи точек можно произвести полный перебор с помощью компьютера.