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