Найти максимальное число полных подграфов

[make78]

Каково наибольшее возможное количество полных подграфов размера $t$ в графе на $n$ вершинах, не содержащем полного подграфа на $t + 1$ вершинах?

Я решаю задачу в общем виде. Буду рад как помощи в продвижении в моем решении, так и подсказках в более изящных решениях (если они есть).

Будем обозначать $\mathtt{ex}(n; K_a, K_{b+1})$ максимальное число подграфов $K_a$ в простом графе на $n$ вершинах при отсутствии подграфа $K_{b+1}$ $(a\leqslant b)$.

Пусть в графе имеется $n=kb+r$ вершин, где $r=n\ \mathtt{mod}\ b$. Считаем, что $b\geqslant2$ (при $b=1$ в графе нет ребер).

При $k=0$, т.е. $n=r<b$, очевидно имеем не более $C_r^a$ подграфов $K_a$, что соответствует случаю полного графа на $r$ вершинах (понятно, что, если $r<a$, имеем $0$ таких подграфов).

Рассмотрим случай, когда $k\geqslant1$.



Пусть для всех $a\in\{1,..,a_0-1\}$ в графе $G_1$ на $n=kb+r$ вершинах выполнено:


$\mathtt{ex}(n; K_a, K_{b+1})=C_r^aC_{b-r}^0(k+1)^ak^0+C_r^{a-1}C_{b-r}^1(k+1)^{a-1}k+...+C_r^0C_{b-r}^a(k+1)^0k^a=$

$=\sum\limits_{j=0}^{a}C_r^jC_{b-r}^{a-j}(k+1)^jk^{a-j}$

Покажем справедливость этой формулы для графа $G$ на $n+a_0$ вершинах для $a=a_0$.

В графе $G$ выделим полный подграф $K_{a_0}$ (обозначим его $G_1$) (если такой есть хотя бы в одном экземпляре) и будем оценивать сверху число подграфов $K_{a_0}$ таких, что хотя бы одно ребро идет из $G_1$ в $G\setminus G_1$:

$\cdot$\ каждая вершина графа $G\setminus G_1$ дает не более одного подграфа $K_{a_0}$ (за счет соединения с подграфом $K_{a_0-1}$ в $G_1$), итого таких подграфов $K_{a_0}$ не более $n=\mathtt{ex}(n; K_1, K_{b+1});

$\cdot$\ каждое ребро графа $G\setminus G_1$ дает не более одного подграфа $K_{a_0}$ (за счет соединения обеих вершин этого ребра с каждой вершиной подграфа $K_{a_0-2}$ в $G_1$), итого таких подграфов $K_{a_0}$ не более $\mathtt{ex}(n; K_2, K_{b+1})$;

$...$

$\cdot$\ каждый подграф $K_i$ графа $G\setminus G_1$ дает не более одного подграфа $K_{a_0}$ (за счет соединения каждой вершины $K_i$ в $G\setminus G_1$ с каждой вершиной $K_{a_0-i}$ в $G_1$), итого таких подграфов $K_{a_0}$ не более $\mathtt{ex}(n; K_i, K_{b+1})$;

$...$

Итого всего подграфов $K_{a_0}$ в $G$ не более, чем $1+\sum\limits_{i=1}^{a_0-1}\mathtt{ex}(n; K_{i}, K_{b+1})+\mathtt{ex}(n; K_{a_0}, K_{b+1})$, где первое слагаемое -- число таких подграфов в $G_1$, последнее -- число таких подграфов в $G\setminus G_1$, то есть всего подграфов $K_{a_0}$ в $G$ не более, чем

$\sum\limits_{i=0}^{a_0}\mathtt{ex}(n; K_{i}, K_{b+1})=\sum\limits_{i=0}^{a_0}\sum\limits_{j=0}^{i}C_r^jC_{b-r}^{i-j}(k+1)^jk^{i-j}$.

Дальше нам нужно показать что последнее выражение совпадает с $\sum\limits_{j=0}^{a}C_r^jC_{b-r}^{a-j}(k+2)^j(k+1)^{a-j}$, что и представляет сложность (в том числе с учетом того, что некоторые "цэшки" равны $0$). На частных случаях формулу проверял - работает.