Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 54 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

54
3. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ
При решении многих комбинаторных задач часто пользуются мето-
дом сведения данной задачи к задаче, касающейся меньшего числа пред-
метов. Метод сведения к аналогичной задаче для меньшего числа пред-
метов называется методом рекуррентных соотношений. Пользуясь
рекуррентными соотношениями, можно свести задачу об
n
предметах к
задаче об
1
-
n
предметах, потом к задаче об
2
-
n
предметах и т.д. После-
довательно уменьшая число предметов, доходим до задачи, которую уже
легко решить.
В книге «Liber Abaci» итальянский математик Фибоначчи среди мно-
гих других задач привел следующую: пара кроликов приносит раз в месяц
приплод из двух крольчат (самки и самца), причем новорожденные крольчата
через два месяца после рождения уже приносят приплод. Сколько кроликов
появится через год, если в начале года была одна пара кроликов?
Из условия задачи следует, что через месяц будет две пары кроликов.
Через два месяца приплод даст только первая пара кроликов, и получится 3
пары. А еще через месяц приплод дадут и исходная пара, и пара кроликов,
появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов.
Обозначим через )n(F количество пар кроликов по истечении
n
ме-
сяцев с начала года. Мы видим, что через
1
+
n
месяцев будет )n(F и еще
столько новорожденных пар кроликов, сколько было в конце месяца
1
-
n
,
то есть еще )n(F 1
-
пар кроликов. Иными словами, имеет место рекур-
рентное соотношение
).n(F)n(F)n(F 11
-
+
=
+
Так как по условию 10
=
)(F и 21
=
)(F , то последовательно находим
845332
=
=
=
)(F,)(F,)(F и т.д.
Числа )n(F называются числами Фибоначчи.
3.1 Решение рекуррентных соотношений
Будем говорить, что рекуррентное соотношение имеет порядок
k
,
если оно позволяет выразить
(
)
knf
+
через
(
)
(
)
(
)
11
-
+
+
knf,,nf,nf
K
.
Например,
(
)
(
)
(
)
(
)
11312
2
++-+=+ nfnfnfnf – рекуррентное соотношение
второго порядка, а
(
)
(
)
(
)
(
)
1263
+
+
+
=
+
nfnfnfnf
рекуррентное соотношение третьего порядка.
Если задано рекуррентное соотношение
k
-го порядка, то ему удов-
летворяет бесконечно много последовательностей. Дело в том, что первые 
                 3. РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

      При решении многих комбинаторных задач часто пользуются мето-
дом сведения данной задачи к задаче, касающейся меньшего числа пред-
метов. Метод сведения к аналогичной задаче для меньшего числа пред-
метов называется методом рекуррентных соотношений. Пользуясь
рекуррентными соотношениями, можно свести задачу об n предметах к
задаче об n � 1 предметах, потом к задаче об n � 2 предметах и т.д. После-
довательно уменьшая число предметов, доходим до задачи, которую уже
легко решить.
      В книге «Liber Abaci» итальянский математик Фибоначчи среди мно-
гих других задач привел следующую: пара кроликов приносит раз в месяц
приплод из двух крольчат (самки и самца), причем новорожденные крольчата
через два месяца после рождения уже приносят приплод. Сколько кроликов
появится через год, если в начале года была одна пара кроликов?
      Из условия задачи следует, что через месяц будет две пары кроликов.
Через два месяца приплод даст только первая пара кроликов, и получится 3
пары. А еще через месяц приплод дадут и исходная пара, и пара кроликов,
появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов.
      Обозначим через F( n ) количество пар кроликов по истечении n ме-
сяцев с начала года. Мы видим, что через n � 1 месяцев будет F( n ) и еще
столько новорожденных пар кроликов, сколько было в конце месяца n � 1 ,
то есть еще F( n � 1) пар кроликов. Иными словами, имеет место рекур-
рентное соотношение
                             F( n � 1) � F( n ) � F( n � 1).
      Так как по условию F( 0) � 1 и F( 1) � 2 , то последовательно находим
                       F( 2 ) � 3 , F( 3) � 5 , F( 4 ) � 8 и т.д.
      Числа F( n ) называются числами Фибоначчи.


                 3.1 Решение рекуррентных соотношений

     Будем говорить, что рекуррентное соотношение имеет порядок k ,
если оно позволяет выразить f �n � k � через f �n �, f �n � 1�,� , f �n � k � 1� .
Например,
      f �n � 2 � � f �n � f �n � 1� � 3 f 2 �n � 1� � 1 – рекуррентное соотношение
второго порядка, а
                               f �n � 3� � 6 f �n � f �n � 2 � � f �n � 1�
рекуррентное соотношение третьего порядка.
     Если задано рекуррентное соотношение k -го порядка, то ему удов-
летворяет бесконечно много последовательностей. Дело в том, что первые

                                       54

Страницы