Теорвер: число вершин в случайном графе...

[max(Im)]

Пусть случайная величина $\xi$ -- число вершин в случайном графе, которые лежат в компонентах связности, являющихся деревом. Вопрос о нахождении математического ожидания $\xi$.

Пусть $\xi_i$ -- случайная величина, которая равна 1, если вершина $i$ лежит в дереве и 0 иначе. Тогда $M\xi=M\xi_1+\ldots+M\xi_n=np,$ где $p$ -- вероятность того, что заданная вершина графа будет лежат в компоненте, являющейся деревом. Вопрос в том, как её найти...

Пробую так: пусть $k$ -- число вершин в этом дереве. Тогда, так как число деревьев есть $k^{k-2}$, а количество способов выбрать остальные $k-1$ вершин есть $C_n^{k-1},$ то число деревьев через заданную вершину в графе есть $\sum_{k=1}^nC_n^{k-1}k^{k-2}.$ Число способов выбора остальной части графа есть $2^{C_{n-k}^2}.$ То есть вероятность

$$ p = \dfrac{\sum_{k=1}^nC_n^{k-1}k^{k-2}2^{C_{n-k}^2}}{2^{C_n^2}} $$

Но это совершенно неподъемная сумма...Можно ли проще?

[Хорхе]

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

[max(Im)]

То есть даже не через разложение $\xi$ в такую сумму ничего хорошего не вылезет?

[Хорхе]

Что означит "даже"?

Еще раз: формула есть, она правильная. На первый взгляд, упростить ее нельзя, на второй тоже. То есть вот он, ответ, только умножить на $n$.