Следствие совершенно замечательное, но пишется совсем коротко. Утверждается всего лишь, что величина 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.