Здравствуйте! Меня зовут Владимир Подольский. На этой неделе мы продолжим с вами обсуждать комбинаторику. И начнем мы с обсуждения свойств чисел сочетаний. Давайте рассмотрим такую задачу: пусть у нас есть обучающая выборка размера n для нашей модели машинного обучения; и мы хотим выделить из нее тестовую выборку размера k. Это частая ситуация в задачах машинного обучения: у нас есть выборка, и мы хотим на части этой выборки обучить модель, а на части протестировать. И вот мы хотим выбрать выборку тестовую размера k. Сколько есть способов это сделать? В этой задаче, по сути, мы хотим выбрать подмножество размера k в n-элементном множестве. И мы уже знаем ответ, из прошлых видео мы знаем, что это число сочетаний из n по k, C из (n по k) — это n факториал делить на k факториал и делить на n минус k факториал. Но давайте посмотрим на эту задачу с другой стороны. Давайте для простоты начнем с примера, и пусть n у нас равно пять и k равно трем, то есть мы хотим выбрать три объекта из пятиэлементного множества. Тогда ответ мы знаем опять же: это С из (пяти по три) — это 10 (мы уже вычисляли его); давайте обозначим элементы нашей выборки через A, B, C, D и E, и давайте просто выпишем все возможные тестовые выборки (здесь, на слайде, они выписаны). И выписываем мы их по следующему принципу (мы выделяем цветом те элементы, которые мы выбираем в выборку), и в левом столбце мы выписали все выборки, в которых содержится A. Таким образом, давайте посмотрим на это внимательнее, как это все устроено. Элемент A в них во всех содержится, и из оставшихся элементов нам нужно выбрать еще две штуки. Мы выбираем BC, BD, B и E и так далее — получается шесть вариантов. Сколько получается строчек в первом столбце? Тут шесть выборок; но, с другой стороны, это же — мы что здесь делаем? Мы выбираем два элемента из четырех оставшихся элементов, то есть на самом деле это число сочетаний из (четырех по два). Давайте посмотрим на второй столбец. Там выписаны все выборки, в которых первый элемент не содержится (элемент A не содержится). Тогда из четырех оставшихся элементов нам нужно выбрать три: и в первой строчке у нас все, кроме последнего, во второй строчке — все, кроме D, в третьей строчке — все, кроме C, и так далее; в последней — все, кроме B. Здесь у нас остается сколько выборок? Нам нужно выбрать из четырех элементов три — и это С из (четырех по три). Хорошо. Что мы получили в итоге? Мы знаем, что число сочетаний здесь — С из (пяти по три); с другой стороны, тех, что содержат элемент A, — их C из (четырех по два); а тех, что не содержат элемент A, — их C из (четырех по три). Получается, что по правилу суммы мы можем это сложить; и получаем, что у нас всего C из (четырех по два) плюс C из (четырех по три) выборок. И мы получили равенство: получается, что C из (пяти по три) — это то же самое, что C из (четырех по два) плюс C из (четырех по три). Хорошо. На самом деле, в общем виде работает все то же самое. Для произвольных n и k мы можем повторить это рассуждение; давайте быстро это сделаем. Всего у нас выборок C из (n по k); и давайте рассмотрим элемент A в нашей выборке (какой-то отдельный элемент). Можем поделить все тестовые выборки на два типа: выборки, содержащие элемент A, и выборки, не содержащие элемент A. Тогда первого типа: у нас выборка уже содержит элемент A, и из оставшихся элементов осталось выбрать (k минус один) элемент. Это число способов выбрать из (n минус одного) элемента (k минус один) — это C из (n минус один по k минус один). Во втором типе элемент A не содержится, поэтому из остальных элементов нам нужно выбрать k штук, то есть получается, что нам из (n минус одного) элемента нужно выбрать k, — и таких способов C из (n минус один по k). По правилу суммы опять же мы получаем, что всего выборок у нас C из (n минус один по k минус один) плюс C из (n минус один по k). И мы снова получили равенство. Давайте подведем итог. Вот наша задача. С одной стороны, ответ в ней — C из (n по k); с другой стороны, ответ — C из (n минус один по k минус один) плюс C из (n минус один по k). Мы получили вот такое равенство, которое называется рекуррентным соотношением для биномиальных коэффициентов. Заметим, что: что мы здесь добились? Мы биномиальный коэффициент для n и k выразили через биномиальные коэффициенты для меньших n: для меньшего n и для меньшего k тоже (в одном из двух коэффициентов). Хорошо. Мы, конечно, можем доказывать это соотношение разными способами; на самом деле, можно было его проверить и прямым вычислением. Давайте это тоже проделаем. У нас есть вот такое равенство; давайте просто убедимся, что оно верно, потому что для всех элементов этого равенства у нас есть формула: C из (n по k) — это n факториал делить на k факториал на (n минус k) факториал. C из (n минус один по k минус один) — для него тоже есть формула: просто подставляем вместо n и k (n минус один) и (k минус один). И аналогично для C из (n минус один по k). Получаем. Давайте посмотрим, что у нас получается. Давайте сложим; вот два биномиальных коэффициента расписали в формулу, и давайте вынесем за скобку все множители в числителе и в знаменателе, какие только можно. Давайте их вынесем. В числителе мы можем вынести (n минус один) факториал, в знаменателе — (k минус один) факториал. В первом слагаемом больше в знаменателе нет k, там не встречается; и также в знаменателе можем вынести (n минус k минус один) — это то, что есть во втором слагаемом; (n минус k) там нету, поэтому это максимум, который мы можем вынести. Что у нас осталось? В первом слагаемом мы не вынесли за скобку в знаменателе — (n минус k), во втором — мы не вынесли в знаменателе k; осталось вот такое в скобках. Давайте приведем это к общему знаменателю: просто перемножим знаменатели; в числителе получается k плюс (n минус k). И заметим, что k и минус k сокращаются; получается, что в числителе осталось n. Давайте посмотрим, какие множители из этой скобки у нас добавились. В числителе добавилось n, и (n минус один) факториал умножить на n — это n факториал. В знаменателе добавился k, и мы можем приписать его к (k минус один) факториал — получатся k факториал. И в знаменателе же добавилось (n минус k); можем также приписать его и получить (n минус k) факториал. И это в точности формула для C из (n по k). Вот мы это равенство проверили прямым вычислением. Хорошо. Давайте обсудим еще вот такой вопрос: как вообще мы можем вычислять число сочетаний? С одной стороны, мы знаем простую формулу: C из (n по k) — это n факториал делить на k факториал на (n минус k) факториал. Вроде бы несложная формула, можно ею пользоваться, но, на самом деле, если мы хотим вычислять биномиальный коэффициент на практике, то эта формула не очень удобна. Эта формула удобна, когда мы работаем с формулами, когда мы подставляем ее куда-то; но для вычисления на практике она не очень пригодна, потому что здесь много операций. И на самом деле, если делать это не очень аккуратно, то числа в вычислениях могут стать большими: n факториал — это может быть огромное число (даже для не очень больших n). Так что это не очень удобная формула для вычислений на практике. Теперь мы знаем также, что можно C из (n по k) выразить через два предыдущих биномиальных коэффициента, и тогда мы можем вычислять биномиальные коэффициенты рекурсивно. То есть мы можем для начала вычислить все биномиальные коэффициенты, например, для n минус один; если нам нужен для n, то мы сводим в задачу для n минус один (и, в свою очередь, можно свести к n минус два и так далее). То есть мы можем начать с маленьких n и последовательно вычислить биномиальные коэффициенты. Оказывается, что это лучше работает. На самом деле есть еще один способ, другой хороший вариант — это вычислить C из (n по k) через предыдущий биномиальный коэффициент для меньшего n и меньшего k. На самом деле, просто если написать здесь формулы, то видно, что они отличаются: в числителе — множителем n, в знаменателе — множителем k.
