Читайте также:
|
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с 
предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным или возвратным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.
Проиллюстрируем метод рекуррентных соотношений на конкретном примере.
Пример 5.1: Найти число сочетаний из по 
с повторениями, т.е. число 
.
Решение: Рассмотрим множество 
. Пусть 
– множество всех сочетаний из по с повторениями, тогда 
. Представим как объединение множества 
и множества 
. – это множество сочетаний с повторениями, которые не содержат элемента 
тогда 
. – множество сочетаний с повторениями, содержащих хотя бы один раз элемент так как каждое такое сочетание может быть получено присоединением к некоторого сочетания из по 
то 
. Очевидно, что пересечение множеств и является пустым множеством, поэтому 
т.е. 
Получили рекуррентное соотношение, используя которое надо найти . Последовательно применяя формулу, находим
Очевидно, что 
, 
тогда, полагая 
, получим 
При 
получим 
Проделанные выкладки позволяют выдвинуть гипотезу:
Проверяем истинность гипотезы методом математической индукции. При 
равенство верно в силу того, что . Теперь находим
т.е. формула верна и при подстановке вместо – 
. Следовательно, согласно принципу математической индукции, формула верна для любого натурального .
Дата добавления: 2015-10-28; просмотров: 75 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Тема 5.1. Бином Ньютона | | | Тема 5.3. Метод производящих функций |