Сколько подграфов у полного графа?

задан 14 Дек '17 22:38

10|600 символов нужно символов осталось
0

Пустой подграф учитывать не будем. Пусть $%1\le k\le n$% -- число вершин подграфа. Они могут быть выбраны $%C_n^k$% способами. При фиксированном выборе, в полном подграфе на этих $%k$% вершинах имеется $%\frac{k(k-1)}2$% рёбер, каждое из которых или присутствует, или отсутствует. Отсюда имеем формулу $%\sum\limits_{k=1}^nC_n^k2^{k(k-1)/2}$%.

Начальные десять членов этой последовательности таковы: 1, 4, 17, 112, 1449, 40068, 2350601, 286192512, 71213783665, 35883905263780, ... .

Можно также заметить, что почти все подграфы здесь имеют $%n$% вершин, то есть асимптотически их будет $%2^{n(n-1)/2}$%.

ссылка

отвечен 14 Дек '17 23:03

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,040
×585
×133

задан
14 Дек '17 22:38

показан
105 раз

обновлен
14 Дек '17 23:03

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru