Задачи мажордома

Введение

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

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

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

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