количество графов с n вершинами и m компонентами связности

[Senchaid]

Нужна формула для количества возможных графов имеющих n вершин и m компонент связности. Для общего случая.
Графы попарно неизоморфные, неориентированные, без петель и кратных ребер.

Предполагаю, что для этого существует доказанная теорема и не надо изобретать велосипед, но никак не могу эту теорему найти.
Буду благодарен, если порекомендуете книгу, в которой это есть/может быть или сошлетесь на конкретную теорему.

[ИСН]

То, что этой формулы нет даже для банально связных графов, Вас не смущает?

[maxal]

См. A201922 и рядом. Там есть формула.

-- Tue Dec 06, 2011 02:58:33 --

ИСН в сообщении #504204 писал(а):

То, что этой формулы нет даже для банально связных графов, Вас не смущает?

Как это нет?! A001349 легко выражается в терминах A000088, а для последней есть формула.

[ИСН]

Ну, если это считать формулой, тогда конечно.
(Наверное, в строгом смысле это так и есть, но у меня как-то язык не поворачивается называть формулой такой алгоритм, который начинается со слов "сумма по таким-то специальным разбиениям...")

[maxal]

ИСН в сообщении #511994 писал(а):

Ну, если это считать формулой, тогда конечно.
(Наверное, в строгом смысле это так и есть, но у меня как-то язык не поворачивается называть формулой такой алгоритм, который начинается со слов "сумма по таким-то специальным разбиениям...")

Вполне себе стандартная вещь в комбинаторике. Например, полиномы Белла определяются через аналогичные суммы.

[melancholic]

А формулу для количества перенумерованных связных графов с n вершинами и l ребрами не подскажете?

[maxal]

melancholic в сообщении #650540 писал(а):

А формулу для количества перенумерованных связных графов с n вершинами и l ребрами не подскажете?

В A057500 приводится такая формула:

$$\sum_{k=1}^n \frac{(-1)^{k+1}}{k} \sum_{n_1+\dots+n_k=n,\ n_i>0} \binom{n}{n_1, \dots, n_k} \binom{\binom{n_1}{2}+\dots+\binom{n_k}{2}}{\ell}$$

[melancholic]

Ого, вот это формула! Спасибо большое. Только непонятно, что это за разбиение n1 + ... + nk = n?

Ага, посмотрел в оригинале - это, вроде, по каждому дереву длиной k проходим.

[Deggial]

melancholic, для набора формул используйте ТеХ