ВУЗ:
Составители:
Рубрика:
19
§ 13. Понятие о методе рекуррентных соотношений
Метод рекуррентных соотношений состоит в том, что решение комбинаторной
задачи с n предметами выражается через решение аналогичной задачи с меньшим
числом предметов с помощью некоторого соотношения, которое называется рекур-
рентным или возвратным. Пользуясь этим соотношением, искомую величину мож-
но вычислить, исходя из того, что для небольшого количества предметов (одного,
двух) решение задачи легко находится.
Проиллюстрируем метод рекуррентных соотношений на конкретном примере.
Пример 17. Найти число сочетаний из n по
r
с повторениями, т.е. число .
r
n
f
Решение.
Рассмотрим множество }.,...,{
1 n
aaA
=
Пусть
−
B
множество всех соче-
таний из
n по
r
с повторениями, тогда .)(
r
n
fBN = Представим
B
как объедине-
ние множества
1
B и множества .
2
B
−
1
B это множество сочетаний с повторениями,
которые не содержат элемента
,
1
a тогда
r
n
fBN
11
)(
−
= .
−
2
B множество сочетаний
с повторениями, содержащих хотя бы один раз элемент ,
1
a так как каждое такое со-
четание может быть получено присоединением к
1
a некоторого сочетания из n по
,1−
r
то .)(
1
2
−
=
r
n
fBN Очевидно, что пересечение множеств
1
B и
2
B является
пустым множеством, поэтому ),()()(
21
BNBNBN
+
=
т.е.
r
n
r
n
r
n
fff
1
1
−
−
+= (25)
Получили рекуррентное соотношение, используя которое надо найти .
r
n
f Последо-
вательно применяя (25), находим
....)(
1
1
1
2
1
1
1
2
1
1
1 −
−
−
−
−
−
−
−
−
++++=++=
rrr
n
r
n
r
n
r
n
r
n
r
n
ffffffff (26)
Очевидно, что
1,
1
1
==
r
n
fnf , (27)
тогда, полагая в (26)
,2=
r
получим
.
2
)1(
12...)1(
2
1
2
+
=
+
=+++−+=
nn
C
nn
nnf (28)
При
3=
r
из равенства (26), учитывая формулы (27),(28) и равенство (22) получим
....
3
2
2
2
2
3
22
1
3
++
=++++=
nnnn
CCCCCf Проделанные выкладки позволяют вы-
двинуть гипотезу – утверждение:
.:
1
r
rn
r
n
CfNr
−+
=∈∀ (29)
Проверяем истинность гипотезы методом математической индукции. При 1
=
r
ра-
венство (29) верно в силу первой формулы из (27). Теперь находим
,......
1
121121
1
+
++−+−+−
+
=++++=++++=
r
rn
r
r
r
r
r
rn
r
rn
rrr
n
r
n
r
n
CCCCCfffff
т.е. (29) верно и при подстановке вместо
r
).1(
+
r
Следовательно, согласно прин-
ципу математической индукции, формула (29) верна для любого натурального .
r
Задача решена.
