Шестое. Шестое. Давайте... Я традиционно его рассказываю, не формулируя. А сначала что-то там разбиваю на части и в конце прихожу к тождеству. Ну почему нет? Давайте возьмем множество A, состоящее из n + 1 объекта. [ПИШЕТ] Давайте возьмем множество A, состоящее из n + 1 объекта. n произвольное, понятное дело. Ну давайте через V обозначим множество всех m-сочетаний с повторениями. Заметьте, с повторениями. Тут надо аккуратно. Это m-сочетание с повторениями. Повторяться могут. Так, с повторениями из A. Ну, естественно, мощность V — это есть C из n + 1 по m с чертой. Ну просто по определению, просто обозначение. А для этого обозначения есть формула через обычную C, которая пишется как? Надо к этому прибавить вот это, да? И вычесть единичку. То есть будет C из n + m, ну а взять это просто по m. Помните, да, такую формулу? Доказывали. Так, чудесно. Давайте как-нибудь V разобьем на части. Просто вот придумаем некоторым специальным образом, как его разбить. Ну, например, давайте через Vi обозначим множество всех, естественно, m-сочетаний с повторениями, то есть мы опять находимся внутри V. Множество всех m-сочетаний с повторениями, каждое из которых содержит ровно i, ровно i символов a1. Каждое из которых содержит ровно i символов a1. Они же с повторениями? Так что символ a1 может входить много раз. Могут вообще не входить, то есть i у нас, вообще говоря, начинается с нуля. Никто не мешает вообще не входить в наше сочетание символу a1. Ну а максимальное количество раз, которое может встречаться символ a1 в нашем сочетании, оно какое? Ну m, естественно, да. То есть вообще-то никто не мешает просто взять и сказать так: а, а, а. а, а. a1, a1, a1, a1, да? Так, хорошо. То есть мощность V, таким образом, — это есть сумма мощностей V0, V1 и так далее, V с индексом m. Это следствие из того, что мы V разбили на кусочки Vi. Понятно, что разбили, да ведь? Так, ну здесь, мы знаем, у нас стоит C из n + m по m. И мне из некоторых соображений хочется это написать как C из n + m по n. Ну какая разница? Есть первое тождество. Это верно, конечно. Так, давайте обсудим, чему равняется, например, мощность V0, — так как-то приятней рассуждать. Сколько есть m-сочетаний с повторениями, которые вообще не содержат символ a1? Нет, ну понятно, сколько их есть. Надо из n взять по m и нарисовать черточку. Ну какой вопрос вообще? Это очевидно. Они же не содержат a1, значит они содержат любые элементы из n оставшихся. Вот из этих n надо выбрать произвольные m, но с повторениями. То есть это есть C из n + m – 1 по m. Или, что то же самое, C из n + m – 1. По кому? По n – 1. Это мы по-прежнему пользуемся первым тождеством: C из n + m – 1 по n – 1. Так, ну здесь один раз в сочетании встречается элемент a1. Что это значит? Ну это значит, что надо из n, правильно? Но выбрать уже не m, а m – 1, потому что один-то раз мы его учли. И это взять с чертой. Это опять же есть C из n + m – 2 по m – 1. И это есть C из n + m – 2, — о чудо, — снова по n – 1. Так, все успевают? Последнее. Это что такое, если m раз он встречается? Это значит — надо взять C из n по 0 с чертой. Вы уж меня простите за занудство. Но вот я именно так это напишу. Соответственно, это у нас будет C из n + 0 – 1 по 0. И это же можно переписать как C из n – 1 по n – 1. Опять получилось сверху n – 1. Итого: вот, вот оно тождество: C из n + m по n = C из n + m – 1 по n – 1 + C из n + m – 2 по n – 1 +... + C из n – 1 по n – 1. Вот это вот — то самое тождество, ради которого мы старались. Оно справедливо вообще при любых парах n и m. Какие два натуральных числа не зафиксируете, оно всегда верно. Такое вот замечательное тождество.