Задача с графом.

[Slow]

Дан граф $G$. Пронумеруем все вершины случайным образом числами от $1$ до $n$, назовем вершину экстремальной, если ее номер больше, чем номера всех соседних с ней вершин. Среднее количество экстремальных вершин по всем расстановкам обозначим $f(G)$.
Какое минимально возможное значение $f(G)$ по всем графам $G$, содержащим ровно $200$ вершин и $700$ ребер?

Я начал с того что попытался выяснить чему равна $f(G)$ для произвольного графа $G$. Пусть $a_{ij}=1$, если для $i$-ой перестановки $j$-ая вершина является экстремальной, иначе $a_{ij}=0$. Тогда $f(G) \cdot n! = \sum\limits_{i=1}^{n!} \sum\limits_{j=1}^n a_{ij}$, от перестановки слагаемых сумма не меняется, поэтому $f(G) \cdot n! = \sum\limits_{j=1}^n \sum\limits_{i=1}^{n!} a_{ij}$. Теперь рассмотрим $g(j)=\sum\limits_{i=1}^{n!} a_{ij}$, $g(j)$ зависит от количества соседей вершины под номером $j$, обозначим его $n(j)$.
Посчитаем количество нумераций таких, что номер вершины $j$ больше номера любого из ее соседей: номер вершины $j$ обязан быть больше количества ее соседей, поэтому рассмотрим случай когда номер вершины $j$ равен $n(j)+1$, тогда количество подходящих нумераций ее соседей равно $n(j)!$, далее если номер вершины $j$ равен $n(j)+k$, тогда количество подходящих нумераций ее соседей равно $\frac{(n(j)+k-1)!}{(n(j)+k-1-n(j))!}$, при этом каждой такой нумерации соответствует $(n-n(j)-1)!$ нумераций остальных вершин, тогда $g(j)=(n-n(j)-1)!(\sum\limits_{k=1}^{n-n(j)} \frac{(n(j)+k-1)!}{(k-1)!})$, ну а дальше нифига не понятно что с этим чудом делать, кажется что вообще не туда забрел

[DeBill]

Slow
Ну, мы же знаем, что матожидание суммы равно сумме матожиданий. Потому достаточно найти матожидание числа случаев, когда данная конкретная вершина экстремальна (что равно вероятности ей быть таковой, каковая легко считается), и сложить по всем вершинам. Ну, и сумма степеней вершин чему равна - это мы знаем, и сколько их - тоже. И соотношение между средними арифметическим и гармоническим тоже знаем...И вот что то кажется мне, что двудольный граф и будет хорош...

-- 04.02.2019, 23:08 --

Slow
Да Вы, собственно, хорошо все делали - только кол-во хороших нумераций неудачно считали. А ведь это можно делать так: рассмотрим те нумерации, у которых на заданную вершину , и всех ее $n(j)$ соседей выпали некоторые фиксированные номера . Тогда она экстремальна - только когда в ней стоит наибольший из этих фиксированных номеров. Так что доля удачных расстановок в точности равна $\frac{1}{n(j)}$. Вроде. так....

-- 04.02.2019, 23:13 --

И еще: сумма Ваша таки считается! Слагаемые в ней - это почти что биноминальные коэф-ты , и стоят они (к-ты из треугольника Паскаля) на "диагонали". Заменив верхнее из них (т.е., единичку) ниже стоящей единичкой, по свойству "число есть сумма над ним стоящих" быстро-быстро свернем сумму в биноминальный же коэффициент. Ну, и получим то что надо...

[Slow]

DeBill в сообщении #1374167 писал(а):

Slow
Ну, мы же знаем, что матожидание суммы равно сумме матожиданий. Потому достаточно найти матожидание числа случаев, когда данная конкретная вершина экстремальна (что равно вероятности ей быть таковой, каковая легко считается), и сложить по всем вершинам.

Хм, кажется что именно это я и сделал:

Slow в сообщении #1374158 писал(а):

$f(G) \cdot n! = \sum\limits_{j=1}^n \sum\limits_{i=1}^{n!} a_{ij}$

DeBill в сообщении #1374167 писал(а):

А ведь это можно делать так: рассмотрим те нумерации, у которых на заданную вершину , и всех ее $n(j)$ соседей выпали некоторые фиксированные номера . Тогда она экстремальна - только когда в ней стоит наибольший из этих фиксированных номеров. Так что доля удачных расстановок в точности равна $\frac{1}{n(j)}$

Тут я не очень понял мысль если честно.

DeBill в сообщении #1374167 писал(а):

И еще: сумма Ваша таки считается! Слагаемые в ней - это почти что биноминальные коэф-ты , и стоят они (к-ты из треугольника Паскаля) на "диагонали". Заменив верхнее из них (т.е., единичку) ниже стоящей единичкой, по свойству "число есть сумма над ним стоящих" быстро-быстро свернем сумму в биноминальный же коэффициент. Ну, и получим то что надо...

А вот тут Вы мне прямо спасательный круг кинули, как представил себе треугольник Паскаля, сразу понял как считать эту сумму.
Для начала меняем все размещения на перестановки:
$g(j)=(n-n(j)-1)!\sum\limits_{k=1}^{n-n(j)}n(j)!C_{n(j)+k-1}^{n(j)}=(n-n(j)-1)!n(j)!\sum\limits_{k=1}^{n-n(j)}C_{n(j)+k-1}^{k-1}=(n-n(j)-1)!n(j)!(C_{n(j)}^{0}+C_{n(j)+1}^{1}+...+C_{n-1}^{n-n(j)-1})=(n-n(j)-1)!n(j)!(C_{n(j)+1}^{0}+C_{n(j)+1}^{1}+...+C_{n-1}^{n-n(j)-1})=(n-n(j)-1)!n(j)!(C_{n(j)+2}^{1}+C_{n(j)+2}^{2}+...+C_{n-1}^{n-n(j)-1})=(n-n(j)-1)!n(j)!(C_{n(j)+3}^{2}+C_{n(j)+3}^{3}+...+C_{n-1}^{n-n(j)-1})=(n-n(j)-1)!n(j)!C_{n}^{n-n(j)-1}=\frac{n!}{n(j)+1}$,
отсюда $f(G)=\sum\limits_{j=1}^{200}\frac{1}{n(j)+1}$
Фуууух, теперь пользуемся леммой о рукопожатиях и получаем $\sum\limits_{j=1}^{200}n(j)=1400$, а значит $\sum\limits_{j=1}^{200}(n(j)+1)=1600$, отсюда $\frac{f(G)}{200}\geqslant\frac{200}{1600}$, получается ответ 25! Уррааа, большое спасибо Вам.

[DeBill]

Slow
Да, все верно (а у меня там неточность была, да: надо $\frac{1}{n(j)+1}$).
Но: это была оценка. А еще надо пример, на котором экстремум достигается!

[Slow]

Полученная оценка достигается только при условии $n(j)+1=n(i)+1$ для любых $i,j$, значит $n(j)=n(i)$, значит $n(j)=7$ для любых $j$, то есть у каждой вершины должно быть $7$ соседей.
Берем 4 вершины, обозначим их $1_1, 2_1, 3_1, 4_1$, к ним добавляем еще 4 вершины $1_2, 2_2, 3_2, 4_2$ и соединяем их таким образом: $1_1$ c $4_2, 1_2, 2_2, 2_1$; $2_1$ с $1_1, 1_2, 2_2, 3_2$; $3_1$ c $2_2, 3_2, 4_2, 4_1$; $4_1$ c 3_1, 3_2, 4_2, 1_2;$ далее по аналогии $1_i$ с $4_{i+1}, 1_{i+1}, 2_{i+1}, 2_i$; $2_i$ с $1_i, 1_{i+1}, 2_{i+1}, 3_{i+1}$; $3_i$ c $2_{i+1}, 3_{i+1}, 4_{i+1}, 4_i$; $4_i$ c $3_i, 3_{i+1}, 4_{i+1}, 1_{i+1}$; индекс берем по модулю $200$, при $i = 50$ в построенном графе будет $200$ вершин. Скорее всего не очень наглядно получилось, но лучше я не придумал.