% Document MUST be built with XeLaTeX! \documentclass[11pt,a4paper]{article} \usepackage[margin=1.5cm]{geometry} % Поддръжка на български език % Thanks to https://tex.stackexchange.com/a/136926 \usepackage{fontspec} \defaultfontfeatures{Ligatures=TeX} \setmainfont{CMU Serif} \setsansfont{CMU Sans Serif} \usepackage[bulgarian,english]{babel} \usepackage{amsmath} % Математически символи \usepackage{amsfonts} % Още математически символи \usepackage{cancel} % Зачертаване \usepackage[dvipsnames]{xcolor} % Цветни кутийки + допълнителни цветове \usepackage{indentfirst} % Индентация на параграф след секция \usepackage{enumitem} \setlist[enumerate]{label=\arabic*.} \renewcommand{\thesection}{Лекция \arabic{section}} \renewcommand{\thesubsection}{\quad\arabic{section}.\arabic{subsection}} \usepackage[pdfauthor={Kamen Mladenov: syndamia.com, gitlab.com/Syndamia}, pdftitle={Discrete Math, Computer Science 2021, Winter Semester}, pdfsubject={Бележки по Дискретни Структури}, pdfkeywords={Съждителна логика, Множества, Релации, Функции, Изброителна комбинаторика, Комбинаторни конфигурации, Рекурентни уравнения}]{hyperref} \begin{document} \section{\underline{Съждителна логика}} \begin{tabular}{l|l} \hline \\[-0.9em] \textbf{Свойства на константите} & $p \land T \equiv p, \quad p \lor F \equiv p, \quad p \lor T \equiv T, \quad p \land F \equiv F$ \\[0.2em] \hline \\[-0.9em] \textbf{Свойства на отрицанието} & $p \land \neg p \equiv F, \quad p \lor \neg p \equiv T$ \\[0.2em] \hline \\[-0.9em] \textbf{Закон за двойното отрицание} & $\neg (\neg p) \equiv p$ \\[0.2em] \hline \\[-0.9em] \textbf{Идемпотентност} & $p \lor p \equiv p, \quad p \land p \equiv p$ \\[0.2em] \hline \\[-0.9em] \textbf{Комутативност} & $p \lor q \equiv q \lor p, \quad p \land q \equiv q \land p$ \\[0.2em] \hline \\[-0.9em] \textbf{Асоциативност} & $(p \lor q) \lor r \equiv p \lor (q \lor r), \quad (p \land q) \land r \equiv p \land (q \land r)$ \\[0.2em] \hline \\[-0.9em] \textbf{Дистрибутивност} & $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r), \quad p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ \\[0.2em] \hline \\[-0.9em] \textbf{Закони на De Morgan} & $\neg (p \lor q) \equiv \neg p \land \neg q, \quad \neg (p \land q) \equiv \neg p \lor \neg q$ \\[0.2em] \hline \\[-0.9em] \textbf{Поглъщане} & $p \lor (p \land q) \equiv p, \quad p \land (p \lor q) \equiv p$ \\[0.2em] \hline \\[-0.9em] \textbf{Свойство на импликацията} & $p \rightarrow q \equiv \neg p \lor q$ \\[0.2em] \hline \\[-0.9em] \textbf{Свойство на би-импликацията} & $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$ \\[0.2em] \hline \end{tabular} \section{\underline{Множества}} Множество, което не съдържа себе си, е обикновено. Множество, което съдържа себе си, е необикновено. \subsection{Аксиоми} \begin{enumerate} \item \emph{Аксиома за обема} \newline Две множества са равни тстк съдържат едни и същи елементи (редът е без значение) \item \emph{Аксиома за отделянето} \newline Ако $X$ е множество и $\pi$ е предикат с домейн $X$, то съвкупността $Y$ от елементите на $X$, които имат свойството $\pi$, е множество. \newline \newline $B = \left\{a \in A \mid \pi(a) \right\}$ \quad Казваме, че B е подмножество на A \item \emph{Аксиома за степенното множество} \newline За всяко множество $X$ съществува множество $2^X$ от всички негови подмножества, което наричаме степенното множество на $X$ \item \emph{Максимално по включване множество} \newline Множество, за което свойството (предикатът) е в сила, но то не е в сила за никое същинско негово надмножество. \begin{enumerate} \item $\sigma (B)$ и \item $\forall C\left( B \subset C \subseteq A \rightarrow \neg \sigma (C) \right)$ \end{enumerate} \emph{Минимално по включване множество} \newline Такова подмножество, за което свойството (предикатът) е в сила, но не е в сила за никое същинско негово подмножество. \begin{enumerate} \item $\sigma (B)$ и \item $\forall C\left( C \subset B \rightarrow \neg \sigma (C) \right)$ \end{enumerate} \end{enumerate} \subsection{Операции} \begin{enumerate} \item \emph{Симетрична разлика} \newline $A \triangle B = \left\{ a \mid a \in A \oplus a \in B \right\}$ \qquad\qquad Пример: $\left\{ a, b, c, d \right\} \triangle \left\{ a, b, x, y \right\} = \left\{ c, d, x, y \right\}$ \item \emph{Допълнение} на множество $A$ до универсум $U$ \newline $\overline{A^U} = \left\{ a \mid a \in U \land a \notin A \right\}$ \quad Ако $U$ се подразбира, пишем само $\overline{A}$ \end{enumerate} \subsection{Наредена двойка} (Дефиниция на Kuratowski) Всяко множество $\left\{\{a\}, \{a, b\}\right\}$ наричаме наредена двойка с първи елемент a и втори елемент b. Краткият запис е “$(a, b)$”. \subsection{Разбиване и покриване} \begin{enumerate} \item \emph{Покриване на $A$} \newline Всяка фамилия $X = \left\{X_1, X_2, ..., X_k \right\}, k \geq 0$, където \begin{enumerate} \item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \subseteq A$ \item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \neq \emptyset$ \item $\bigcup\limits_{i = 1}^{k} X_i = A$ \end{enumerate} Тоест, всяка фамилия, чието обединение на множества е даденото множество. \newline Пример: $A = \left\{ a, b, c, d \right\} \qquad X = \left\{ \{a, b, d\}, \{b, c\}, \{a, b, c, d\} \right\}$ \item \emph{Разбиване на $A$} \newline Всяка фамилия $X = \left\{X_1, X_2, ..., X_k \right\}, k \geq 0$, където \begin{enumerate} \item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \subseteq A$ \item $\forall i \in \left\{ 1, 2, ..., k \right\} : X_i \neq \emptyset$ \item $\bigcup\limits_{i = 1}^{k} X_i = A$ \item $\forall i \forall j (1 \leq i < j \leq k \rightarrow X_i \cap X_j = \emptyset)$ \end{enumerate} Тоест, покриване, при което няма общи елементи между множествата във фамилията. \newline Пример: $A = \left\{ a, b, c, d \right\} \qquad X = \left\{ \{a, c\}, \{b\}, \{c\} \right\}$ \end{enumerate} \subsection{Доказателство по индукция} \begin{enumerate} \item \emph{Обикновена индукция} \begin{enumerate} \item \emph{База}: Проверяваме за най-ниската възможна стойност \hfill $P(0), n \geq 0$ \item \emph{Индукционно предположение}: Допускаме че е вярно за произволна стойност \hfill $P(n)$ \item \emph{Индукционна стъпка}: Доказваме че е вярно за следващата произволна стойност, въз основа на индукционното предположение \hfill $P(n + 1)$ \end{enumerate} \item \emph{Силна индукция} \begin{enumerate} \item \emph{База}: Проверяваме за най-ниската възможна стойност \hfill $P(0), n \geq 0$ \item \emph{Индукционно предположение}: Допускаме, че е вярно за всички стойности от най-ниската до произволно $n$ \hfill $P(0), P(1), ..., P(n)$ \item \emph{Индукционна стъпка}: Доказваме че е вярно за следващата произволна стойност, въз основа на индукционното предположение \hfill $P(n + 1)$ \end{enumerate} \end{enumerate} \section{\underline{Релации}} Релация над декартовото произведение $A_1 \times A_2 \times ... \times A_n$ се нарича всяко множество $R \subseteq A_1 \times A_2 \times ... \times A_n$ \subsection{Свойства на релации от вида $R \subseteq A^2$} \begin{enumerate} \item \emph{Рефлексивност} \qquad\qquad $\forall a \in A : aRa$ \newline \emph{Антирефлексивност} \qquad $\forall a \in A : \neg aRa$ \item \emph{Симетричност} \qquad\qquad\qquad $\forall a, b \in A, a \neq b : aRb \rightarrow bRa$ \newline \emph{Антисиметричност} \qquad\qquad $\forall a, b \in A, a \neq b : aRb \rightarrow \neg bRa$ \newline \emph{Силна антисиметричност} \quad $\forall a, b \in A, a \neq b : aRb \oplus bRa$ \item \emph{Транзитивност} \qquad $\forall a, b, c \in A : aRb \land bRc \rightarrow aRc$ \end{enumerate} \subsubsection{Затваряне на релации} \begin{enumerate} \item \emph{Рефлексивно затваряне} $R'$ \begin{enumerate} \item $R' \subseteq A^2$ \item $R \subseteq R'$ \item $R'$ е рефлексивна \end{enumerate} \end{enumerate} Аналогично за симетрично и транзитивно затваряне \subsubsection{Типове релации} \begin{enumerate} \item \emph{Релация на еквивалентност}: рефлексивна, симетрична, транзитивна \newline \emph{Класове на еквивалентност}: $[a] = \{ b \in A \mid aRb \}$ \quad Дефакто са разбивания на $R$ \item \emph{Релация на частична наредба}: рефлексивна, антисиметрична, транзитивна \newline \emph{Минимален елемент}: \; $a$ е минимален, ако $\neg \exists b \in A, a \neq b : bRa$ \newline \emph{Максимален елемент}: $a$ е максимален, ако $\neg \exists b \in A, a \neq b : aRb$ \newline \newline \emph{Релация на частична строга наредба}: антирефлексивна, антисиметрична, транзитивна \newline \emph{Диаграма на Hasse}: Чертаем диаграма на релацията, така че всички стрелки да сочат нагоре, изпускаме примките, изпускаме посоките на стрелките, изпускаме транзитивните стрелки. \newline Няма контури в частичните наредби! \item \emph{Релация на линейна наредба}: рефлексивна, силно антисиметрична, транзитивна \newline \emph{Линейно разширение}: Частична наредба $R$, линейна наредба $R'$, $R \subseteq R' \implies R'$ е линейно разширение на $R$ \newline \newline \emph{Релация на линейна строга наредба}: антирефлексивна, силно антисиметрична, транзитивна \end{enumerate} \subsubsection{Верига и контур} \begin{itemize} \item \emph{Верига}: всяка редица $a_{i_0}, a_{i_1}, ..., a_{i_k} \;\text{, където }\\ i_0,...,i_k \in \{1,...,n\}, \, a_{i_j} \, R \, a_{i_{j + 1}} \;\text{ и }\; a_{i_j} \neq a_{i_{j + 1}} \;\text{ за }\; 0 \leq j < k$ \newline \newline Дефакто, редица от елементи, където всеки два съседни елемента са в релация. \newline Веригите НЕ минават през примки! \item \emph{Контур}: всяка верига, за която е вярно и, че $a_{i_0} = a_{i_k} \text{ за } k > 0$ \newline \newline Дефакто, редица от елементи, където всеки два съседни елемента са в релация и първия и последния също са в релация. \end{itemize} \section{\underline{Функции}} \begin{itemize} \item \emph{Тотална функция}: Всяка релация $f \subseteq X \times Y$, където за всяко $x$ има точно едно $y : (x, y) \in f$ \item \emph{Частична функция}: Всяка релация $f \subseteq X \times Y$, където за всяко $x$ има не повече от едно $y : (x, y) \in f$ \end{itemize} \subsection{Свойства} \begin{enumerate} \item \emph{Инекция}: Всеки елемент на $Y$ е образ най-много на един елемент на $X$ \newline $\forall x_1, x_2 \in X : x_1 \neq x_2 \implies f(x_1) \neq f(x_2)$ \item \emph{Сюрекция}: Всеки елемент на $Y$ е образ на поне един елемент на $X$ \newline $\forall y \in Y \exists x \in X : f(x) = y$ \item \emph{Биекция}: Ако имаме инекция и сюрекция (взаимозначно съответствие) \end{enumerate} \subsubsection{Изброимост} \begin{itemize} \item \emph{Крайно множество}: Ако $A$ е празно, то имаме кардиналност 0. \newline Иначе, трябва да съществува $n$, за което съществува биекция $f : A \rightarrow \{1, 2, ..., n\}$ \item \emph{Безкрайно множество}: Ако не е крайно \newline \emph{Изброимо безкрайно мнжоество}: Ако е равномощно на $\mathbb{N}$ \hfill $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{N}^2, \mathbb{Z}^2, ...$ \newline \emph{Неизброимо безкрайно множество}: Ако не е изброимо безкрайно \hfill $\mathbb{R}, \mathbb{C}, 2^{\mathbb{N}}, \mathbb{R}^2, 2^{\mathbb{R}}, ...$ \end{itemize} \subsubsection{Принцип на Дирихле} За крайни $X$ и $Y$, $|X| > |Y|$, то не съществува инекция $f : X \rightarrow Y$ Ако имаме $m$ обекта в $n$ чекмеджета, то има поне едно чекмедже с $\left\lceil \frac{m}{n} \right\rceil$ обекта. \subsection{Рестрикция на функция} Нека $f : X \rightarrow Y$ и $X' \subseteq X$. Рестрикция на $f$ върху $X'$ е $f' : X' \rightarrow Y,\; \forall x \in X' : f'(x) = f(x)$ Бележи се $\left. f \right|_{X'}$ \qquad (Дефакто работим с част от елементите на домейна) \section{\underline{Изброителна комбинаторика}} \subsection{Принципи} \begin{enumerate} \item \emph{Принцип на Дирихле} \item \emph{Принцип на разбиването} \newline Кардиналността е сума от кардиналностите на дяловете на разбиване. \newline За множество $X$ и негови разбивания $\left\{ Y_1, ..., Y_k \right\}$, имаме $|A| = |Y_1| + ... + |Y_k| = \sum\limits_{i = 1}^{k} |Y_i|$ \newline \newline \emph{Принцип на изваждането} (следствие от Принцип на разбиването) \newline За множество $A$ и универсум $U$, имаме $|A| = |U| - \left| \overline{A} \right|$ \item \emph{Принцип на умножението}: $|A \times B| = |A| \cdot |B|$ \item \emph{Принцип на биекцията}: $|A| = |B|$ тстк съществува биекция $f : A \rightarrow B$ \item \emph{Принцип на делението} \newline За $k = $ брой класове на еквивалентност, $\left| [a] \right| = m$, имаме $m = \frac{|A|}{k}$ \item \emph{Принцип на включването и изключването} \newline Кардиналността е сума от дяловете на покритие със изваждане на техни сечения. \begin{align*} |A_1 \cup ... \cup A_n| & = \sum\limits_{1 \leq i \leq n} |A_i| - \sum\limits_{1 \leq i < j \leq n} |A_i \cap A_j| + ... + (-1)^{n-1} \cdot |A_1 \cap ... \cap A_n| \\ |\overline{A_1} \cap ... \cap \overline{A_n}| & = |U| - \sum\limits_{1 \leq i \leq n} |A_i| + \sum\limits_{1 \leq i < j \leq n} |A_i \cap A_j| - ... + (-1)^{n-1} \cdot |A_1 \cap ... \cap A_n| \end{align*} \end{enumerate} \section{\underline{Комбинаторни конфигурации}} Дадено е опорно множество $А = {a1, a2, ..., an}$ чрез което ще изграждаме комбинаторни конфигурации. Общоприето е, че $n$ е брой елементи в $A$, $m$ е брой елементи в конфигурация. \begin{enumerate} \item \emph{Множество от конфигурации с наредба, с повтаряне} \newline $\text{К}_\text{Н, П}(n, m) = A^m \equiv \widetilde{V}_n^m \qquad\qquad \left| \text{К}_\text{Н, П}(n, m) \right| = |A^m| = n^m$ \item \emph{Множество от конфигурации с наредба, без повтаряне} \newline $\text{К}_\text{Н}(n, m) \equiv V_n^m \qquad\qquad \left| \text{К}_\text{Н}(n, m) \right| = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n - m + 1) = n^{\underline{m}}$ \newline\newline \emph{Пермутации с повторения}: частен случай, когато $n = m$. $\left| \text{К}_\text{Н}(n, m) \right| = n!$ \item \emph{Множество от конфигурации без наредба, без повтаряне}: просто комбинации/подмножество \newline $\text{К}(n, m) \equiv C^n_m \qquad\qquad \left| \text{К}(n, m) \right| = \frac{\left| \text{К}_\text{Н}(n, m) \right|}{m!} = \frac{n!}{(n-m)!m!} = \frac{n^{\underline{m}}}{m!} = \binom{n}{m}$ \end{enumerate} \begin{tabular}{l||l|l|l} \hline \\[-0.9em] & Комбинации & Вариации & Пермутации \\[0.2em] Различаваме по: & Съставни елементи & Съставни елементи и ред & Ред \\[0.2em] \hline \hline \\[-0.9em] Без повторениe & $C^k_n = \frac{n!}{k!(n-k)!} = \binom{n}{k}$ & $V^k_n = \frac{n!}{(n-k)!} = n^{\underline{k}}$ & $P_n = n!$ \\[0.2em] \hline \\[-0.9em] С повторение & $\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n-1)!}$ & $\widetilde{V}^k_n = n^k$ & $\widetilde{P}^{n_1, n_2, ..., n_m}_n = \frac{n!}{n_1!n_2!...n_m!}$ \\[0.2em] \hline \end{tabular} \subsection{Свойства на биномни коефициенти} \noindent \begin{align*} & \binom{n}{k} = \frac{n!}{k!(n-k)!} \qquad \binom{n}{k} = \binom{n}{n - k} \qquad \binom{n}{k} + \binom{n}{k + 1} = \binom{n + 1}{k + 1} \qquad \binom{n}{k} = \binom{n - 1}{k} + \binom{n - 1}{k - 1} \\ & \binom{n}{0} = \binom{n}{n} = 1 \qquad \binom{n}{1} = \binom{n}{n-1} = n \\ & \textbf{Нютонов бином } \quad (x + y)^n = \sum_{k = 0}^n \binom{n}{k} \cdot n^k \cdot y^{(n - k)} \\ & \textbf{От комбинаторни разсъждения } \quad \binom{2n}{n} = \sum^n_{k = 0} \binom{n}{k}^2 \qquad \binom{n + m}{m} = \sum^m_{k = 0} \binom{n + k - 1}{k} \end{align*} \subsection{Характеристичен вектор} Булева n-торка, която характеризира/определя дадено множество $X$, където: Ако $n \in X$, то $a_n = 1$ \qquad Ако $n \notin X$, то $a_n = 0$ \subsubsection{Свойства (за булеви вектора с $n$ единици и $m$ нули)} \begin{itemize} \item Брой: $\binom{n+m}{n}$ \item Брой, като след всяка единица има нула: $\binom{m}{n}$ \item Брой, като няма съседни единици: $\binom{m + 1}{n}$ \end{itemize} \subsection{Свойства на суми} \noindent \begin{align*} \sum_{k = 0}^n k = \frac{n(n + 1)}{2} \qquad \sum_{k = 0}^n k^2 = \frac{n(n + 1)(2n + 1)}{6} \qquad \sum_{k = 0}^n k^3 = \frac{n^2(n + 1)^2}{4} \qquad \sum_{k = 0}^n a = a(n+1) \end{align*} \section{\underline{Рекурентни уравнения}} Уравнение, при което дясната му страна включва и самото уравнение и имаме начално условие(ия) \begin{align*} & \text{Пример: } L(n) = \begin{cases} L(n-1) + n, & \text{ ако } n \in \mathbb{N}^+ \\ 1, & \text{ ако } n = 0 \end{cases} \end{align*} \subsection{Алгоритъм за решаване на линейно рекурентно уравнение с константни коефициенти и крайна история} \noindent \begin{align*} & F_n = \begin{cases} F_{n-1} + F_{n-2}, & \text{ ако } n \geq 2 \\ 1, & \text{ ако } n = 1 \\ 0, & \text{ ако } n = 0 \end{cases} \qquad \text{ е такова валидно уравнение} \\ & \text{Обаче, следните уравнения не могат да се решат с този метод:} \\ & T_n = \begin{cases} n \cdot T_{n-1} & \text{ ако } n \geq 1 \\ 1, & \text{ ако } n = 0 \end{cases} \qquad \text{ защото не е с константи коефициенти} \\ & S_n = \begin{cases} S_{n-1} + S_{n-2} + ... + S_1 + S_0, & \text{ ако } n \geq 1 \\ 1, & \text{ ако } n = 0 \end{cases} \qquad \text{ защото не е с крайна история} \end{align*} За илюстриране на метода, нека да разгледаме $a_n = c_1 a_{n-1} + c_2 a_{n-2} + ... + c_k a_{n-k}$ \begin{enumerate} \item \emph{Характеристично уравнение} \newline Заместваме $a_n$ с $x^n$, $a_{n-1}$ с $x^{n-1}$ и так. нат. \hfill $x^n = c_1 x^{n-1} + c_2 x^{n-2} + ... + c_k x^{n-k}$ \newline След това, делим всичко на $x^{(n-k)}$ \hfill $x^k = c_1 x^{k-1} + c_2 x^{k-2} + ... + c_k$ \qquad\- \newline Алтернативно, може да се запише и като \hfill $x^k - c_1 x^{k-1} - c_2 x^{k-2} - ... - c_k = 0$ \, \- \item \emph{Общо решение} \newline Намираме корените на хар. уравнение. \hfill Нека те да са мултимножеството $\{ \alpha_1, \alpha_2, ..., \alpha_k \}_{\text{М}}$ \newline Съставяме уравнението \hfill $a_n = A_1 \cdot \alpha_1^n + A_2 \cdot \alpha_2^n + ... + A_k \cdot \alpha_k^n$ \newline\newline Ако имаме еднакви корени, умножаваме с $n^r$, където $r \in \mathbb{N}$ е r-тия повтарящ се корен. \newline Тоест, ако да имаме 5 корена, за които $\alpha_1 = \alpha_2 = \alpha_3 \neq \alpha_4 \neq \alpha_5$, ще изглежда така: \newline\newline \- \hfill $a_n = A_1 \alpha_1^n \cdot n^0 + A_2 \alpha_2^n \cdot n^1 + A_3 \alpha_3^n \cdot n^2 + A_4 \alpha_4^n + A_5 \alpha_5^n$ \item \emph{Точно решение} (Само ако началните условия са ни дадени) \newline Вземаме първите $k$ на брой начални условия (ако се наложи допълваме, тоест изчисляваме всички стойности до $a_k$). \newline С тях, съставяме система линейни уравнения за $a_1, a_2, a_3, ...$ \begin{equation*} \left| \begin{array}{ccccccccc} a_1 & = & A_1 \cdot \alpha_1^1 & + & A_2 \cdot \alpha_2^1 & + & ... & + & A_k \cdot \alpha_k^1 \\ \vdots \\ a_k & = & A_1 \cdot \alpha_1^k & + & A_2 \cdot \alpha_2^k & + & ... & + & A_k \cdot \alpha_k^k \end{array} \right. \end{equation*} Чрез нея, намираме стойностите на $A_1, ..., A_k$ и заместваме в Общото решение \end{enumerate} \subsection{Решаване на нехомогенно рекурентно уравнение с константни коефициенти и крайна история} Нека $b_1, ..., b_l$ са различни стойности, а $p_1(n), ..., p_l(n)$ са полиноми на $n$. Уравненията са от типа \begin{equation*} a_n = \underbrace{c_1 a_{n-1} + ... + c_k a_{n-k}}_{\text{xомогенна част}} + \underbrace{p_1(n) \cdot b_1^n + ... + p_l(n) \cdot b_l^n}_{\text{нехомогенна част}} \end{equation*} \begin{enumerate} \item \emph{Характеристично уравнение} \newline Съставя се като при \textbf{7.1}, като просто си представим, че нехомогенната част (тази с $p_l(n)$-вете) не съществува. \item \emph{Общо решение} \newline След като намерим мултимножеството от корени на хомогенната част, разглеждаме нехомогенната. \newline Абстрахираме се от всякакви коефициенти и разглеждаме хомогенната част като сборове от комбинации на $n^g \cdot h^n$. \newline Образуваме мултимножеството от корени на нехомогенната част, като добавяме съответните $h$ $g+1$ пъти. \begin{align*} \text{Пример: } & 2n^2 + 3^n + 19n^3 7^n \; \text{ свеждаме до } \; n^2 1^n + n^0 3^n + n^3 7^n \\ & \text{Корените ни са, три 1-ци, една 3-ка, четири 7-ци: } \{1, 1, 1, 3, 7, 7, 7, 7\}_{\text{М}} \end{align*} Накрая обединяваме двете мултимножества и продължаваме както при \textbf{7.1}. \item \emph{Точно решение} \newline Следваме същите стъпки като \textbf{7.1} \end{enumerate} \end{document}