299
правок
Изменения
м
→Числа Рамсея для раскрасок в несколько цветов
|statement=Пусть <tex>k,n_1,...,n_k \ge 2</tex> - натуральные числа. Тогда выполняются следующие утверждения:
<tex>1) r(k;n_1,...,n_k) \le r(k;n_1-1,n_2,...,n_k)+r(k;n_1,n_2-1,...,n_k)++r(k;n_1,n_2,...,n_k-1)-k+2</tex>
<texdpi="150">2)r(k;n_1,...,n_k) \le \frac{(n_1+n_2+...+n_k)!}{n_1!\cdot n_2!\cdot ...\cdot n_k!}</tex>
|proof=
1) Доказательстве полностью аналогично пункту 1 доказательства [[#ter1|теоремы 1]]
2) Доказательство аналогично [[#u1|утверждению 1]]. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно из чисел <tex>n_1,...,n_k</tex> равно 1 (левая часть в этом случае равна 1, а правая, очевидно не меньше 1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению:
<texdpi="150">\frac{(n_1+n_2+...+n_k)!}{n_1!\cdot n_2!\cdot ...\cdot n_k!}=\sum\limits_{i = 1}^k\frac{(n_1+...+(n_i-1)+...+n_k)!}{n_1!\cdot ...\cdot (n_i-1)!\cdot ...\cdot n_k!}</tex>
Следовательно, 2 неравенство из данной [[#ter3|теоремы]] выводится из неравенства 1 по индукции.
