Вероятность выбора независимого множества вершин графа

[pptfhcs]

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

Вот такая задача.

Из графа размером $n$ вершин и $m$ рёбер наудачу выбрали $k$ вершин. С какой вероятностью никакие две выбранных вершины не соединены ребром?

Попробуем решить так

$p=1-\frac{m\cdot\binom{n-2}{k-2} - \binom{m}{2}\cdot\binom{n-3}{k-3} + \binom{m}{3}\cdot\binom{n-4}{k-4} - ...}{\binom{n}{k}}$

В числителе что-то вроде формулы включения-исключения. Складываем все случаи когда 2 вершины соединены, вычитаем когда 3 вершины соединены, и т.д.
Но формула неправильная, т.к 2-е слагаемое (когда выбрали 2 ребра) может исключить и 4 вершины, 3-е слагаемое (когда выбрали 3 ребра) - от 3 до 6 вершин. Итого, вообще кажется, что исходных $(n,m,k)$ данных недостаточно, решение зависит от конкретного графа.
Нельзя ли тем не менее получить какую-то оценку, исходя только из $(n,m,k)$?

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- отдельные обозначения надо набрать так же, как формулы;
- изложите содержательные попытки решения задачи с обоснованиями, как были получены те или иные промежуточные выводы.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»