Тема 5.2. Понятие о методе рекуррентных соотношений

Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным или возвратным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.

Проиллюстрируем метод рекуррентных соотношений на конкретном примере.

Пример 5.1:Найти число сочетаний изпос повторениями, т.е. число.

Решение: Рассмотрим множество . Пусть– множество всех сочетаний изпос повторениями, тогда. Представимкак объединение множестваи множества.– это множество сочетаний с повторениями, которые не содержат элементатогда.– множество сочетаний с повторениями, содержащих хотя бы один раз элементтак как каждое такое сочетание может быть получено присоединением кнекоторого сочетания изпото. Очевидно, что пересечение множествиявляется пустым множеством, поэтомут.е.

Получили рекуррентное соотношение, используя которое надо найти . Последовательно применяя формулу, находим

Очевидно, что ,

тогда, полагая , получим

При получим

Проделанные выкладки позволяют выдвинуть гипотезу:

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

т.е. формула верна и при подстановке вместо –. Следовательно, согласно принципу математической индукции, формула верна для любого натурального.

Тема 5.3. Метод производящих функций

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

Определение: Если степенной рядсходится на множествек функции, то она называется производящей функцией для последовательности.

Проиллюстрируем идею метода производящих функций следующей задачей. Если необходимо найти все члены некоторой числовой последовательности, то сначала с помощью рекуррентного соотношения для общего члена последовательности или, исходя непосредственно из комбинаторных соображений, находят производящую функцию, а затем для неё – ряд Маклорена. Коэффициент этого степенного ряда прии будет искомым выражением для общего члена числовой последовательности.

Пример 5.2:Найти число сочетаний изпос повторениями, т.е.

Решение:Дляимеем следующее рекуррентное соотношение

Для того чтобы равенство имело место и при достаточно считать, что.

Пусть производящая функция для последовательноститогда

Умножим обе части равенства и сложим почленно все равенства, тогда получим

, но

,

и, подставляя эти значения, имеем

, откуда следует

Так как , то

следовательно, . Из теории степенных рядов известно, что

значит, из единственности разложения функции в ряд Маклорена, следует .

Тема 5.4. Метод траекторий

Метод траекторий состоит в том, что для комбинаторной задачи указывается геометрическая интерпретация, которая сводит задачу к подсчёту числа путей (траекторий), обладающих определённым свойством. Этим методом фактически была решена задача в примере 4.2. Проиллюстрируем метод траекторий ещё на одном примере.

Пример 5.3:Возле кассы собралисьчеловек, причёмиз них имеют монеты стоимостью 50 копеек, а другие имеют лишь по рублю. Сначала в кассе нет денег, билет стоит 50 копеек. Сколько всего имеется способов размещения всех покупателей в очереди так, чтобы ни один из них не ждал сдачи?

Решение: Допустим, что покупатели расположены в очереди некоторым образом. Пусть

Рассмотрим сумму

Ясно, что значение , является разностью между количеством пятидесятикопеечных монет и количеством рублей, которые будут поданы в кассу первымипокупателями из очереди.

Введём на плоскости декартову прямоугольную систему координат. Построим в ней точки с координатамии рассмотрим ломаную, соединяющую точкус точкойи проходящую через точки. Будем называть ломаную траекторией, соответствующей данному способу размещения покупателей в очереди. Каждая траектория состоит изотрезков,из которых направлены вверх, анаправлены вниз. Если указать номера тех отрезков, которые направлены вверх, то тем самым траектория будет полностью определена. Следовательно, общее число траекторий, т.е. число возможных размещений покупателей в очереди, равно.

Траектории, соответствующие тем способам размещения покупателей, при которых ни один покупатель не ждет сдачи, не имеют общих точек с прямой . Действительно, если для некоторогото, в лучшем случае, это означает, что первыепокупателей подали в кассу одинаковое количество полтинников и рублей, а следующий покупатель подал рубль и вынужден ожидать сдачу. Определим число траекторий, имеющих общую точку с прямой. Поставим в соответствие каждой траектории, имеющей с прямойхотя бы одну общую точку, ломануюпо следующему правилу. До первой общей точки с прямойломанаясовпадает с, а далее является симметричным отображением T относительно прямой. Все ломаныезаканчиваются в точке, являющейся симметричным отображением точкиотносительно прямой. Установленное соответствие является взаимно однозначным. Число ломаных типа, равно числу ломаных, соединяющих точкии. Это число легко подсчитать. Если ломанаясостоит изотрезков, направленных вниз, иотрезков, направленных вверх, то

откуда получаем ,. Таким образом, число траекторий, имеющих общую точку с прямой, равно. Следовательно, искомое число траекторий, соответствующих тем способам размещения покупателей, при которых ни один покупатель не ждет сдачи, равно