Разделы 
Дополнительно
Задача по математике - 2600
2019-03-30 
Дана последовательность $a_1, a_2, a_3, \cdots, a_{10}$. Сколькими способами ее можно разбить на группы, сохраняя фиксированный порядок ее элементов, каждая из которых состоит из одного элемента или двух рядом стоящих элементов?
Решение:
Пусть $P_n$ - ответ на вопрос задачи для последовательности, состоящей из $n$ элементов. B первой группе может оказаться либо один элемент ($a_1$) либо два элемента ($a_1, a_2$). Разбиений, содержащих в первой группе один элемент ($a_1$), будет столько, сколько разбиений можно образовать из $n-1$ оставшихся членов последовательности $a_2, a_3, \cdots, a_n$, т. е. $P_{n-1}$. Разбиений же, содержащих в первой группе два элемента, будет $P_{n-2}$, так как после образования группы ($a_1, a_2$) останется $n-2$ элементов $a_3, \cdots, a_n$.
Итак, $P_n = P_{n-1} + P_{n-2}$.
Tакая формула называется рекуррентной, потому что, зная $P_1$ и $P_2$ и применяя ее последовательно, мы получим $P_3$ затем $P_4$ и т. д. Поскольку $P_1 = 1$, а $P_2 = 2$, то $P_3 = 3, P_4 = 5, P_5 = 8, P_6 = 13, P_7 = 21, P_3 = 3, P_8 = 34, P_9 = 55, P_{10} = 89$.
Ответ. 89.
Дана последовательность $a_1, a_2, a_3, \cdots, a_{10}$. Сколькими способами ее можно разбить на группы, сохраняя фиксированный порядок ее элементов, каждая из которых состоит из одного элемента или двух рядом стоящих элементов?
Решение:
Пусть $P_n$ - ответ на вопрос задачи для последовательности, состоящей из $n$ элементов. B первой группе может оказаться либо один элемент ($a_1$) либо два элемента ($a_1, a_2$). Разбиений, содержащих в первой группе один элемент ($a_1$), будет столько, сколько разбиений можно образовать из $n-1$ оставшихся членов последовательности $a_2, a_3, \cdots, a_n$, т. е. $P_{n-1}$. Разбиений же, содержащих в первой группе два элемента, будет $P_{n-2}$, так как после образования группы ($a_1, a_2$) останется $n-2$ элементов $a_3, \cdots, a_n$.
Итак, $P_n = P_{n-1} + P_{n-2}$.
Tакая формула называется рекуррентной, потому что, зная $P_1$ и $P_2$ и применяя ее последовательно, мы получим $P_3$ затем $P_4$ и т. д. Поскольку $P_1 = 1$, а $P_2 = 2$, то $P_3 = 3, P_4 = 5, P_5 = 8, P_6 = 13, P_7 = 21, P_3 = 3, P_8 = 34, P_9 = 55, P_{10} = 89$.
Ответ. 89.
