Шестое.
Шестое.
Давайте...
Я традиционно его рассказываю, не формулируя.
А сначала что-то там разбиваю на части и в конце прихожу к тождеству.
Ну почему нет?
Давайте возьмем множество 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.
Какие два натуральных числа не зафиксируете, оно всегда верно.
Такое вот замечательное тождество.