Розв'язник вправ по дискретній математиці/Комбінаторика/Вправи на рекурсію

Розв'язник вправ по дискретній математиці. Комбінаторика. Вправи на рекурсію

Рекурентним співвідношенням називається вираз, який дозволяє визначити наступні члени послідовності через попередні.

Під розв'язанням рекурентного співвідношення будемо розуміти формулу, яка дозволяє отримати елемент послідовності, що задається рекурсією, по його номеру, без обчислення попередніх елементів.

Наприклад, послідовність Фібоначчі:

a_n+1=a_n+a_n-1, a₁=1, a₂=1,

має розв'язком формулу Біне:

$F_{n}={\frac {\phi ^{n}-(-\phi )^{-n}}{\phi -(-\phi )^{-1}}}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}}\approx {\frac {\phi ^{n}}{\sqrt {5}}}\quad (n\geqslant 1).$

Де золотий перетин $\phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1,618.$

Лінійне однорідне рекурентне співвідношення з постійними коефіцієнтами

Лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку $k$ є рівняння

$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},$

де всі коефіцієнти $c_{i}$ постійні.

Ті ж самі коефіцієнти визначають характеристичний многочлен (або "допоміжний многочлен")

$p(t)=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}$.

Згідно з основною теоремою алгебри існує $d$ коренів рівняння $p(t)=0$. Ці корені відіграють вирішальну роль в знаходженні послідовності, яка відповідає заданому рекурентному співвідношенню.

Якщо всі корені $r_{1},r_{2},\dots ,r_{d}$ різні, то розв'язок рекурсії має вигляд:

$a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},$

де коефіцієнти $k_{i}$ визначаються в залежності від значень початкових елементів послідовності $a_{1},a_{2},\dots ,a_{d}$.

У випадку коли однакові корені присутні декілька разів (кратні корені) розв'язок рекурсії має інший вигляд. Якщо $r_{i}\ (i=1,\dots ,s)$ корінь кратності $l_{i}$ (для простого кореня $l_{i}=1$), тоді

$a_{n}=\sum _{i=1}^{s}(k_{i1}+k_{i2}n+\cdots +k_{il_{i}}n^{l_{i}-1})r_{i}^{n},$

де коефіцієнти $k_{ij}$ визначаються з початкових елементів послідовності.

Алгоритм розв'язання однорідного рекурентного співвідношення

1. Скласти характеристичний поліном і розв'язати його. Виписати формулу $a_{n}$ елемента послідовності в залежності від того чи наявні кратні корені.

2. Застосувати формулу для $a_{n}$ елемента, до початкових елементів $a_{1},a_{2}$, значення яких вже відомі. Таким чином буде отримана система лінійних рівнянь. Розв'язок лінійної системи дозволяє знайти остаточний вираз для $a_{n}$.

В якості прикладу можна зауважити, що послідовність Фібоначчі задається лінійним однорідним рекурентним співвідношенням з постійними коефіцієнтами порядку два. Застосування наведеного методу дає згадану вище формулу Біне.

Приклад розв'язання однорідного рекурентного співвідношення

Нехай $a_{n+2}=5a_{n+1}-6a_{n}$, початкові значення $a_{1}=5,a_{2}=7$. Знайти формулу для обчислення $a_{n}$.

1. Складаємо характеристичний поліном за допомогою наступної підстановки:

${\begin{array}{lll}a_{n+2}&\to &t^{2}\\a_{n+1}&\to &t^{1}=t\\a_{n}&\to &t^{0}=1\end{array}}$

Тоді, з $a_{n+2}=5a_{n+1}-6a_{n}$ отримуємо $t^{2}=5t-6$.

Знаходимо корені $t^{2}-5t+6=0$: $t_{1}=2,t_{2}=3$.

Так як корені різні, то тоді розв'язок рекурсії має вигляд:

$a_{n}=k_{1}t_{1}^{n}+k_{2}t_{2}^{n}=k_{1}*2^{n}+k_{2}*3^{n}$

2. Знайдемо невідомі коефіцієнти $k_{1},k_{2}$. Для цього застосуємо формулу для $a_{n}=k_{1}*2^{n}+k_{2}*3^{n}$, до початкових елементів $a_{1}=5,a_{2}=7$, значення яких вже відомі з умови. Таким чином отримаємо систему лінійних рівнянь:

$\left\{{\begin{array}{lll}a_{1}=&k_{1}*2^{1}+k_{2}*3^{1}&=5\\a_{2}=&k_{1}*2^{2}+k_{2}*3^{2}&=7\end{array}}\right.$

$\left\{{\begin{array}{ll}2k_{1}+3k_{2}&=5\\4k_{1}+9k_{2}&=7\end{array}}\right.$

Розв'язок цієї лінійної системи $k_{1}=4,k_{2}=-1$. Остаточний вираз для $a_{n}=4*2^{n}-3^{n}$.

Приклад розв'язання однорідного рекурентного співвідношення з комплексними числами

Нехай $a_{n}-2a_{n-1}+5a_{n-2}=0$, початкові значення $a_{0}=4,a_{1}=4$. Знайти формулу для обчислення $a_{n}$

1. Нехай $p^{n}$ розв'язок даного рівняння і $a_{n}=$ $p^{n}$. Тоді, рівняння $a_{n}-2a_{n-1}+5a_{n-2}=0$ матиме вигляд

$p^{n}-2p^{n-1}+5p^{n-2}=0$.

Далі, розділимо отримане рівняння на $p^{n-2}$:

$p^{2}-2p+5=0$.

Знайдемо його корені: $p_{1}=1+2i;p_{2}=1-2i$ Тоді, запишемо формулу для $a_{n}$:

$a_{n}=k_{1}*p_{1}+k_{2}*p_{2}=k_{1}(1+2i)+k_{2}(1-2i)$

2. Знайдемо коєфіцієнти $k_{1}$ і $k_{2}$ Для цього застосуємо формулу

$a_{n}=k_{1}*p_{1}+k_{2}*p_{2}=k_{1}(1+2i)+k_{2}(1-2i)$

до даних елементів $a_{0}=4,a_{1}=4$. Отримаємо систему лінійних рівнянь:

$\left\{{\begin{array}{lll}a_{0}=k_{1}+k_{2}=4\\a_{1}=k_{1}*(1+2i)+k_{2}*(1-2i)=4\end{array}}\right.$

Розв'язок цієї лінійної системи: $k_{1}=2,k_{2}=2$ Остаточний вигляд для $a_{n}=2*(1+2i)^{n}+2*(1-2i)^{n}$

Приклад розв'язання однорідного рекурентного співвідношення з кратними коренями

Нехай $a_{n}=4a_{n-1}-4a_{n-2}$, початкові значення $a_{1}=2,a_{2}=-4$. Знайти формулу для обчислення $a_{n}$.

1. Нехай $r^{n}$ розв'язок даного рівняння і $a_{n}=r^{n}$. Тоді, рівняння $a_{n}=4a_{n-1}-4a_{n-2}$ матиме вигляд

$r^{n}=4r^{n-1}-4r^{n-2}$.

Далі, розділимо отримане рівняння на $r^{n-2}$: $r^{2}=4r-4$. Отримали квадратне рівняння: $r^{2}-4r+4=0$ Знайдемо його корені:

$r=r_{1}=r_{2}=2$

Так як корені $r_{1}$ та $r_{2}$ збігаються, тоді формула для $a_{n}$ має такий вигляд:

$a_{n}=r^{n}(k_{1}+k_{2}*n)$

2. Знайдемо коєфіцієнти $k_{1}$ і $k_{2}$ Для цього застосуємо формулу $a_{n}=r^{n}(k_{1}+k_{2}*n)$ до даних елементів $a_{1}=2,a_{2}=-4$. Отримаємо систему лінійних рівнянь:

$\left\{{\begin{array}{lll}a_{1}=2*(k_{1}+k_{2})=2\\a_{2}=2^{2}*(k_{1}+k_{2}*2)=-4\end{array}}\right.$

Розв'язок цієї лінійної системи: $k_{1}=3,k_{2}=-2$ Остаточний вигляд для $a_{n}=2^{n}*(3-2*n)$

Алгоритм розв'язання неоднорідного рекурентного співвідношення

1. Знайти частковий розв'язок неоднорідного рекурентного співвідношення $a_{n}^{c}$. Це якраз найскладніше завдання, тому що не існує єдиного алгоритму дій на цьому етапі.

2. Знайти розв'язок однорідного рекурентного співвідношення $a_{n}^{o}$ у загальному вигляді. Невідомі коефіцієнти будуть обчислені на наступному кроці.

3. Розв'язок неоднорідного рекурентного співвідношення записати у вигляді $a_{n}=a_{n}^{o}+a_{n}^{c}$. Застосувати формулу для $a_{n}$ елемента, до початкових елементів $a_{1},a_{2}$, значення яких вже відомі. Таким чином буде отримана система лінійних рівнянь. Розв'язок лінійної системи дозволяє знайти остаточний вираз для $a_{n}$.

Приклад розв'язання неоднорідного рекурентного співвідношення

Нехай $a_{n+2}-4a_{n+1}+3a_{n}=2^{n}$, початкові значення $a_{0}=7,a_{1}=10$. Знайти формулу для обчислення $a_{n}$.

1. Знайдемо частковий розв'язок неоднорідного рекурентного співвідношення у вигляді $a_{n}^{c}=A\cdot 2^{n}$, де $A$ — константа, яка буде знайдена. Тоді $a_{n+1}^{c}=A\cdot 2^{n+1}=2A\cdot 2^{n}$, $a_{n+2}^{c}=A\cdot 2^{n+2}=4A\cdot 2^{n}$. Підставимо у рекурентне рівняння:

$4A\cdot 2^{n}-4\cdot 2A\cdot 2^{n}+3\cdot A\cdot 2^{n}=2^{n}$

$4A-8A+3A=1$

$A=-1$

Отже, частковим розв'язком неоднорідного рекурентного співвідношення буде $a_{n}^{c}=-2^{n}$

2. Знайдемо розв'язок $a_{n}^{o}$ однорідного рекурентного співвідношення $a_{n+2}-4a_{n+1}+3a_{n}=0$ у загальному вигляді. Невідомі коефіцієнти будуть обчислені на наступному кроці.

${\begin{array}{lll}a_{n+2}&\to &t^{2}\\a_{n+1}&\to &t^{1}=t\\a_{n}&\to &t^{0}=1\end{array}}$

$t^{2}-4t+3=0$.

Знаходимо корені: $t_{1}=1,t_{2}=3$.

Так як корені різні, то тоді розв'язок рекурсії має вигляд:

$a_{n}=k_{1}t_{1}^{n}+k_{2}t_{2}^{n}=k_{1}+k_{2}*3^{n}$

3. Розв'язком неоднорідного рекурентного співвідношення буде $a_{n}=a_{n}^{o}+a_{n}^{c}=k_{1}+k_{2}*3^{n}-2^{n}$. Знайдемо невідомі коефіцієнти $k_{1},k_{2}$. Для цього застосуємо формулу для $a_{n}=k_{1}+k_{2}*3^{n}-2^{n}$ до початкових елементів $a_{0}=7,a_{1}=10$, значення яких вже відомі з умови. Таким чином отримаємо систему лінійних рівнянь:

$\left\{{\begin{array}{lll}a_{0}=&k_{1}+k_{2}*3^{0}-2^{0}&=7\\a_{1}=&k_{1}+k_{2}*3^{1}-2^{1}&=10\end{array}}\right.$

$\left\{{\begin{array}{ll}k_{1}+k_{2}-1&=7\\k_{1}+3k_{2}-2&=10\end{array}}\right.$

Розв'язок цієї лінійної системи $k_{1}=6,k_{2}=2$. Остаточний вираз для $a_{n}=6+2*3^{n}-2^{n}$.

Додаткові вправи

Розв'яжіть рекурентні співвідношення:

• $a_{n+2}-5a_{n+1}+4a_{n}=0$, початкові значення $a_{0}=3,a_{1}=9$.
• $a_{n+2}-6a_{n+1}+9a_{n}=0$, початкові значення $a_{0}=1,a_{1}=9$.
• $a_{n+2}+4a_{n}=0$, початкові значення $a_{0}=1,a_{1}=2$.
• $a_{n+2}-3a_{n+1}+2a_{n}=12\cdot 4^{n}$, початкові значення $a_{0}=1,a_{1}=9$. Відповідь: $a_{n}=2^{n+1}+2\cdot 4^{n}-3$.
• $a_{n+2}+3a_{n+1}-10a_{n}=8\cdot 3^{n}$, початкові значення $a_{0}=3,a_{1}=0$. Відповідь: $a_{n}=(-5)^{n}+2^{n}+3^{n}$.
• $a_{n+3}-a_{n+2}-8a_{n+1}+12a_{n}=0$, знайдіть загальний розв'язок. Відповідь: $a_{n}=2^{n}(C_{1}+nC_{2})+(-3)^{n}C_{3}$.
• Нехай $a_{n}$ вектор довжини ${n}$, який складається з нулів та одиниць. а) Скільки існує таких векторів? б) Скільки існує таких векторів, де нулі не стоять поруч? с) Скільки векторів у яких будь-які два сусідні елемента різні?

Написати програму

Задача 1

Рекурсивного обчислення $n!$.

Задача 2

Рекурсивного обчислення чисел Фібоначчі.

Задача 3

Розв'язати завдання з leetcode.com (Count Vowels Permutation). Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

• Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
• Each vowel 'a' may only be followed by an 'e'.
• Each vowel 'e' may only be followed by an 'a' or an 'i'.
• Each vowel 'i' may not be followed by another 'i'.
• Each vowel 'o' may only be followed by an 'i' or a 'u'.
• Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:  

Input: n = 1

Output: 5

Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:  

Input: n = 2

Output: 10

Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".