Комбинаторика

Как считать комбинации

Перебор вариантов
Как кодировать комбинации
Правило умножения
Как считать комбинации без перебора
Правило деления
Как учесть беспорядок
Метод перегородок
Как вычислить число разбиений
Размещения и сочетания
Как систематизировать выборки
Треугольник Паскаля
Как вывести свойства числа сочетаний
Бином Ньютона
Как раскрывать скобочки

Треугольник Паскаля

Часто решение задачи несколькими способами вскрывает интересные взаимосвязи. Рассмотрим пример такой задачи, в которой раскрывается одно свойство чисел сочетаний.

На бумаге отметили сорок пять кружков в виде равнобедренного треугольника (смотри рисунок). В вершине треугольника стоит фишка. Фишку можно передвигать влево вниз или вправо вниз вдоль соединяющих линий. Сколько существует способов передвинуть фишку в середину основания треугольника (красный кружок на рисунке)?

Решение

Сначала решим задачу комбинаторно. Для этого закодируем все маршруты. Каждый ход фишку нужно опустить на один уровень вниз, а всего нужно опуститься на восемь уровней. А значит, любой маршрут состоит из восьми ходов. Нам нужно прийти точно в середину основания. Для этого необходимо, чтобы количество ходов влево было равно количеству ходов вправо. То есть в каждом маршруте будет четыре хода влево и четыре хода вправо. Зарезервируем восемь мест, на которых будем стрелками отмечать, какой ход сделан. Теперь из этих восьми мест нам нужно выбрать четыре места, на которых будут стоять стрелки вправо (на остальные места расставим стрелки влево). Итак, количество способов выбрать четыре места из восьми равно $C_{8}^{4} = 70.$

А теперь эту же задачу решим методом, который носит называние метода динамического программирования. Для этого подсчитаем, сколькими способами можно попасть в ближайшие от вершины кружки. В каждом кружке будем отмечать количество маршрутов, ведущих в этот кружок.

Поясним, как можно вычислить количество маршрутов, например, до кружка с цифрой три. В него можно попасть двумя путями: либо из левого верхнего кружка, в который можно попасть одним способом, либо из правого верхнего кружка, в который можно попасть двумя способами. Всего получаем $1 + 2 = 3$ маршрута. Вычислим аналогичным образом количество маршрутов до остальных кружков.

Применение метода динамического программирования

Итак, у нас получился тот же ответ. Теперь попробуем понять, почему он получился такой же. Мы уже знаем, что количество путей в середину основания равно $C_{8}^{4}$ . Закодируем пути в две клетки, ближайшие к этому кружку. В кружок левее и выше середины основания длина маршрута составляет семь ходов: три хода вправо и четыре хода влево. Значит, в него мы сможем попасть $C_{7}^{3}$ способами (выбрав, когда ходить вправо). В кружок правее и выше длина маршрута также составляет семь ходов: четыре хода вправо и три хода влево. Значит, в него мы сможем попасть $C_{7}^{4}$ способами. Объединяя комбинаторный метод и метод динамического программирования, получаем формулу $C_{7}^{3} + C_{7}^{4} = C_{8}^{4} .$

Связь метода динамического програмирования с комбинаторикой

Ответ: $70$ .

Теперь обобщим наши наблюдения. Обозначим буквой $n$ длину пути до определенного кружка. Пусть до этого кружка нужно сделать $k$ шагов вправо. Тогда количество путей до этого кружка равно $C_{n}^{k}$ . До кружка левее и выше нашего длина пути составляет $(n - 1)$ , и нужно сделать $(k - 1)$ шаг вправо, то есть получим $C_{n - 1}^{k - 1}$ маршрутов. До кружка правее и выше нашего длина пути также составляет $(n - 1)$ , и нужно сделать $k$ шагов вправо, мы получим $C_{n - 1}^{k}$ маршрутов. Применяя метод динамического программирования, выводим формулу

C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}

Докажем эту формулу комбинаторно, не привлекая метод динамического программирования.

Докажите, что $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k}$ .

Решение

Представим, что перед нами стоит $n$ человек. Нам нужно набрать команду, в которой будет $k$ человек. Количество способов это сделать (без учета порядка выбора) равно $C_{n}^{k}$ . Теперь вычислим это же число по-другому. Пусть среди $n$ человек есть некий Вася. Подсчитаем количество команд вместе с Васей. Тогда к Васе нужно добрать еще $(k - 1)$ человек. А выбирать мы будем из $(n - 1)$ человека. Значит, количество команд с Васей равно $C_{n - 1}^{k - 1} .$

Теперь вычислим, сколько существует команд без Васи. На этот раз мы будем набирать $k$ человек из $(n - 1)$ . Количество способов это сделать равно $C_{n - 1}^{k}$ .

Команды могут быть либо с Васей, либо без Васи, отсюда и получаем нашу формулу: $C_{n}^{k} = C_{n - 1}^{k - 1} + C_{n - 1}^{k} .$

Обратите внимание на решение задачи 11 из предыдущей статьи. В нем эта формула выведена еще одним способом.

Мы вывели способ быстрого вычисления чисел сочетаний с помощью метода динамического программирования и обосновали его комбинаторно. Треугольник, который у нас получился, называют треугольником Паскаля. Отметим на рисунке логику его построения: число $n$ обозначает длину маршрута от вершины, а число $k$ — количество ходов направо.

Задачи

В левом нижнем углу квадрата $8 \times 8$ стоит фишка (смотри рисунок). Фишку можно передвигать вверх и вправо по сторонам клеток. Сколько существует способов передвинуть фишку в правый верхний угол, если фишка обязательно должна пройти через центральную точку?

Решение.

Сначала вычислим количество маршрутов в центральную точку. Длина пути каждого маршрута равна восьми: четыре хода вправо и четыре хода вверх. Закодируем наш маршрут стрелками вверх и вправо. Тогда из восьми мест для стрелок нужно будет выбрать четыре для стрелок вверх. Количество способов это сделать составляет $C_{8}^{4} = 70$ . Аналогично найдем количество маршрутов из центральной точки в правый верхний угол, получим также $70$ . Эти маршруты выбираются независимо, а значит, по правилу умножения получаем, что общее количество маршрутов равно $70 \cdot 70 = 4900.$

Ответ: $4900$ .

Решение

Ответ

Докажите, что $C_{n}^{k} = C_{n}^{n - k}$ . Как это равенство можно увидеть в треугольнике Паскаля?

Решение.

Например, число сочетаний $C_{5}^{2}$ это количество способов выбрать два предмета из пяти. Предположим, что мы занумеровали предметы ${1, 2, 3, 4, 5}$ и выбрали из них предметы с номерами ${1, 2}$ . Этому способу выбрать два предмета соответсвует ровно один способ выбрать три предмета из пяти, а именно — выбрать оставшиеся предметы ${3, 4, 5}$ .

Аналогично рассуждаем и в общем случае: каждому способу выбрать $k$ предметов из $n$ соответствует ровно один способ выбрать остальные $(n - k)$ предметов из $n$ . Следовательно, $C_{n}^{k} = C_{n}^{n - k}$ .

Треугольник Паскаля составлен из чисел сочетаний. Из полученного равенства можно сделать вывод, что треугольник Паскаля симметричен относительно своей медианы, которая совпадает с биссектрисой и высотой.

Ответ: треугольник Паскаля симметричен.

Решение

Ответ

Рассмотрим $C_{N}^{x}$ как функцию целой неотрицательной переменной $x$ . Найдите $x$ , при котором эта функция принимает наибольшее значение.

Решение.

Исследуем отношение значений нашей функции в двух соседних точках. Если при некотором $x$ окажется, что $\frac{C_{N}^{x + 1}}{C_{N}^{x}} > 1$ , мы сделаем вывод, что $C_{N}^{x + 1} > C_{N}^{x}$ , и функция $C_{N}^{x}$ возрастает при этом $x$ . Если же окажется, что $\frac{C_{N}^{x + 1}}{C_{N}^{x}} < 1$ , следовательно, $C_{N}^{x + 1} < C_{N}^{x}$ , и функция $C_{N}^{x}$ убывает. Точка смены возрастания на убываение будет являться максимумом функции $C_{N}^{x}$ .

Вспомним из урока про сочетания, что $C_{n}^{k} = \frac{n!}{k! (n - k)!}$ . Используем это равенство. Сокращая факториалы, получим $\frac{C_{N}^{x + 1}}{C_{N}^{x}} = \frac{N - x}{x + 1} .$ Чтобы сравнить эту дробь с единицей, выделим единицу в явном виде: $\begin{matrix} \frac{N - x}{x + 1} = \\ = \frac{x + 1 + N - 1 - 2 x}{x + 1} = \\ = 1 + \frac{N - 1 - 2 x}{x + 1} . \end{matrix}$ Рассмотрим случай, когда число $N$ нечетно, то есть $N = 2 n + 1$ . Получим, что $\frac{C_{N}^{x + 1}}{C_{N}^{x}} = 1 + \frac{2 (n - x)}{x + 1} .$ Из этого равенства делаем вывод, что ${\begin{cases} C_{N}^{x + 1} > C_{N}^{x}, при x < n, \\ C_{N}^{x + 1} = C_{N}^{x}, при x = n, \\ C_{N}^{x + 1} < C_{N}^{x}, при x > n . \end{cases}$ Следовательно, наибольшее значение достигается в двух точках: при $x = n$ и $x = n + 1$ . Например, рассмотрим график функции $C_{7}^{x}$ . Видим, что он достигает наибольшего значения в двух точках: при $x = 3$ и $x = 4$ (сравните этот результат с треугольником Паскаля при $n = 7$ ).

Теперь рассмотрим случай, когда число $N$ четно, то есть $N = 2 n$ . Получим, что $\frac{C_{N}^{x + 1}}{C_{N}^{x}} = 1 + \frac{2 (n - x) - 1}{x + 1} .$ Из этого равенства делаем вывод, что ${\begin{cases} C_{N}^{x + 1} > C_{N}^{x}, при x \leq n, \\ C_{N}^{x + 1} < C_{N}^{x}, при x > n . \end{cases}$ Следовательно, наибольшее значение достигается в единственной точке: при $x = n$ . Рассмотрим график функции $C_{8}^{x}$ . Он достигает наибольшего значения в точке $x = 4$ .

Ответ: если $N = 2 n$ , тогда наибольшее значение достигается при $x = n$ ; если же $N = 2 n + 1$ , тогда наибольшее значение достигается при $x = n$ и $x = n + 1$ .

Решение

Ответ