Следствие совершенно замечательное, но пишется совсем коротко.
Утверждается всего лишь, что величина g от (n, m) равняется C из (n + m) по m.
Ну или, согласно первому комбинаторному тождеству,
можно написать C из (n + m) по n.
Конечно, всё совершенно симметрично и благополучно свидетельствует о том,
что g от (n, m) и g от (m, n) – это, по сути, одно и то же, конечно.
Вот. Другое дело, почему это так?
Сейчас вы увидите.
Всё очень красиво.
Значит, как вывести наше следствие из того рекурентного соотношения тех
начальных условий, которые мы знаем?
А по индукции, естественно, по индукции.
Смотрите, g от (1,
0) – это, как мы с вами знаем, 1,
но C из (1 + 0) по 0 – это, естественно, тоже 1.
То есть, первое начальное условие благополучно согласуется.
Ну, естественно, g от (0, 1) – это есть, опять же, C из (1 + 0) по 1 – это есть 1.
То есть, и второе начальное условие тоже согласуется благополучно.
Это то, что называется базой индукции.
То есть, мы понимаем,
что уже в вот этих случаях заведомо справедливо наше утверждение.
Ну хорошо, давайте предположим, что оно справедливо для n − 1 и m,
и что оно справедливо для m − 1 и n.
Понятное предположение.
Тогда у нас получится, что g от (n, m), как мы знаем,
равняется g от (n − 1, m) плюс g от (n,
m − 1), и каждую из этих величин мы уже считаем вычисленной.
Давайте напишем, чему она равна, согласно нашему предположению.
Это C из (n − 1 плюс m), ну давайте, вот в этой форме, например,
по n − 1 + C из n + C
из m − 1 по n, вот так вот.
Ничего не напоминает?
Ну это в точности тождество для треугольника Паскаля,
как треугольник Паскаля формируется.
Простейшее второе комбинаторное тождество.
Ну давайте, я ещё раз перепишу, хотя нет, не нужно, всё, понятно.
Зачем ещё раз переписывать?
Здесь стоит n + m − 1, и здесь то же самое число n + m − 1,
но один раз оно берется по n − 1, а другой раз оно берется по m.
Ну давайте, я напомню.
Вот было такое тождество: C из a по b равняется C из a −
1 по b − 1 + C из a − 1 по b.
Вот это вот – тождество, которое формирует треугольник Паскаля,
мы его доказывали давным-давно, но оно здесь явно и присутствует.
Вот это вот a − 1, вот это – оно же, a − 1, вот это – b, а вот это – b − 1.
Я думаю, что в такой записи уже совершенно понятно, чего происходит.
У нас получается C из a + 1, вот, из a, вернее,
a − 1 + 1, то есть, C из m + n по n − 1, n, n.
Всё, следствие доказано.
Больше делать нечего.
Доказали.
Общее количество выравниваний в тех предположениях,
каких мы их определяли – это в точности C из n + m по n.