Викиконспекты - Вклад участника [ru]

Очередь Майкла и Скотта

2018-10-14T13:23:34Z

KokorinIlya: /* Структура очереди */

'''Очередь Майкла и Скотта''' ''(Michael-Scott Queue)'' - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scott <ref>[http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf? Simple, Fast, and Practical Non-Blocking and BlockingConcurrent Queue Algorithms]</ref>.
== Структура очереди ==

Очередь построена на односвязном списке. Каждый элемент списка <tex>Node</tex> содержит ссылку на хранимые в нём данные и атомарный указатель на следующий элемент списка.

'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)

Если узел <tex>node</tex> является последним в списке, то <tex>node
next</tex> указывает на <tex>null</tex>.

Сама очередь состоит из двух атомарных указателей: <tex>H</tex> на голову и<tex>T</tex> на хвост. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Голова списка является фиктивным элементом ''(dummy)''. Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.

[[Файл:Структура_msqueue.PNG|500px|thumb|center|Структура очереди Майкла и Скотта]]

'''class''' Queue
dummy = '''new''' Node(null, '''new''' AtomicReference<Node>(null))
head = '''new''' AtomicReference<Node>(dummy)
tail = '''new''' AtomicReference<Node>(dummy)

Будем поддерживать следующий инвариант: в нашей очереди <tex>H</tex> указывает на узел, находящийся не правее узла, на который указывает <tex>T</tex>

==Однопоточная реализация==

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
if (H.next == null):
'''throw''' '''new''' EmptyException()
H = H.next
'''return''' H.data //H - новый фиктивный элемент

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, new AtomicReference<Node>(null))
T.next = newTail //Добавление новой вершины в очередь
T = T.next //Изменение хвоста списка

== Не lock-free многопоточная реализация ==

Будем при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex> использовать <tex>CAS</tex>.

=== Удаление элемента ===

Для удаления элемента необходимо переместить указатель <tex>H</tex> на следующую в списке вершину.

'''def''' pop(): '''Int'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на H, пока не получится
head = H.get()
if (head.next == null):
'''throw''' '''new''' EmptyException()
newHead = head.next.get()
if ('''CAS'''(H, head, nextHead)):
'''return''' newHead.data

=== Добавление элемента ===

Создадим новый узел списка, и добавим его в конец очереди.

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять T.next, пока не получится
tail = T.get()
curTail = tail.next
if ('''CAS'''(curTail, null, newTail)): //Поток пытается добавить элемент в конец очереди
'''break'''
'''while''' ('''true'''): //Поток пытается в CAS - цикле поменять указатель на T, пока не получится
tail = T.get()
nextTail = tail.next.get()
if ('''CAS'''(T, tail, nextTail)):
'''break'''

При данной реализации мы сталкиваемся со следующей проблемой

== Описание проблемы ==

Рассмотрим ситуацию, при которой два потока <tex>A</tex> и <tex>B</tex> добавляют в очередь элементы <tex>elem</tex> и <tex>elem'</tex>. Рассмотрим следующую последовательность действий:

# Поток <tex>A</tex> добавляет в очередь новую вершину, изменяя <tex>T.next</tex>, но не успевает изменить <tex>T</tex> так, чтобы он указывал на только что добавленную вершину.
# Планировщик операционной системы усыпляет поток <tex>A</tex>.
# Поток <tex>B</tex> собирается добавить новую вершину в очередь, но не может этого сделать, так как постоянно проваливает операцию <tex>CAS(T.next, null, newTail)</tex> (T.next не указывает на <tex>null</tex>, так как поток <tex>A</tex> на шаге <tex>1</tex> добавил в очередь новую вершину, но не передвинул <tex>T</tex>)
# Поток <tex>B</tex> не сможет добавить в очередь новую вершину (а следовательно, завершить операцию <tex>push</tex>), до тех пор, пока планировщик операционной системы не разбудит поток <tex>A</tex>, и поток <tex>A</tex> не завершит добавление (то есть не передвинет <tex>T</tex> на вершину, добавленную на шаге <tex>1</tex>.)

Следовательно, у такой очереди нет гарантии прогресса, и этот алгоритм не lock-free.

== Корректная lock-free реализация ==

=== Основная идея ===

Нельзя выполнить добавление элемента в очередь и перемещение <tex>T</tex> атомарно. В таком случае, пусть остальные потоки помогают перенести указатель на хвост очереди. Если поток видит непустой <tex>T.next</tex> (то есть если он провалил <tex>CAS(tail.next, null, newTail)</tex>), то он должен помочь перенести <tex>T</tex>, то есть выполнить <tex>CAS(T, tail, tail.next.get())</tex> однократно. Если <tex>CAS</tex> выполнен успешно, то хвост перемещён успешно (а значит, наш поток должен вернуться к добавлению нового элемента). Если же он выполнен неудачно, то это значит, что <tex>T</tex> уже не указывает на <tex>tail</tex>, а значит, другой поток уже успешно переместил хвост (а значит, наш поток должен вернуться к добавлению нового элемента).

=== Реализация <tex>push</tex> ===

'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //CAS-цикл
tail = T.get()
'''if''' ('''CAS'''(tail.next, '''null''', newTail)):
/*
Если T указывает на последний добавленный элемент и
получилось добавить ещё один элемент в хвост,
пробуем передвинуть T. Если не получилось передвинуть T,
значит, другой поток сделал это за нас, завершаем работу.
Если получилось - то мы сами передвинули T, завершаем работу
*/
'''CAS'''(T, tail, newTail)
'''return'''
else:
/*
Если T - не последний добавленный элемент элемент, то передвигаем T на последний элемент
Если этого сделать не получилось, значит, это сделал другой поток.
Если получилось - значит, наш поток передвинул T на текущий последний элемент.
В любом случае, возвращаемся в начало CAS-цикла, чтобы завершить добавление в очередь новой вершины.
*/
'''CAS'''(T, tail, tail.next.get())

== Корректная реализация <tex>pop</tex> ==

=== Проблема с <tex>pop</tex> ===

Если мы попытаемся воспользоваться написанной выше реализацией метода <tex>pop</tex>, инвариант очереди не будет соблюдён. В силу особенностей реализации метода <tex>push</tex>, в некоторые моменты <tex>T</tex> может указывать не на добавленный последним элемент, а на добавленный предпоследним. В таком случае, с помощью последовательности удалений можно добиться того, что <tex>H</tex> будет указывать на последний добавленный элемент, а <tex>T</tex> - на предпоследний. Таким образом, <tex>H</tex> будет указывать на вершину правее чем та, на которую указывает <tex>T</tex>, то есть инвариант очереди будет нарушен

=== Корректная реализация ===

Основная проблема предыдущей реализации состоит в том, что в методе <tex>pop</tex> при перемещении <tex>H</tex>, мы никак не следили за положением <tex>T</tex>. Эту проблему можно исправить следующим образом: пусть в методе <tex>pop</tex> рабочий поток будет помогать переместить указатель <tex>T</tex> на последний добавленный элемент (аналогично действиям рабочего потока в методе <tex>push</tex>).

Для определения того, указывает ли <tex>T</tex> на последний добавленный элемент, воспользуемся следующим соображением: если <tex>T</tex> указывает на последний добавленный элемент, то <tex>T.get().next == '''null'''</tex>, так как за последним добавленным элементом нет других элементов. В противном случае <tex>T</tex> указывает на предпоследний добавленный элемент, и его надо передвинуть на последний добавленный.

'''def''' pop(): '''Int'''
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): //CAS-цикл
head = H.get() //Сохраняем в локальные переменные текущие голову и хвост, а так же следующий за головным элемент
tail = T.get()
nextHead = head.next.get()
'''if''' (head == tail):
/*
Если head и tail совпадают, это ещё не означает, что очередь пуста.
Возможно, что мы просто не успели подвинуть tail. Если tail.next не null,
то мы просто не успели подвинуть tail при добавлении.
*/
'''if''' (nextHead == '''null'''):
// Следующего элемента нет, очередь пуста
'''throw''' '''new''' EmptyException()
'''else''':
/*
push не успел подвинуть T, наш поток должен помочь
tail == head => tail.next == head.next
*/
'''else''':
// Очередь гарантированно не пуста, следующий элемент существует
result = nextHead.data
'''if''' ('''CAS'''(H, head, nextHead)):
/*
Если получилось переставить голову, то фиктивным элементом стал
H.next, результат - данные, которые в нём лежали. Если не получилось -
возвращаемся в начало метода и пробуем ещё раз
*/
'''return''' result

==Примечания==

<references />
== Источники информации==
* Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230
[[Категория: Параллельное программирование]]

Файл:Структура msqueue.PNG

2018-10-14T13:20:25Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T18:22:48Z

KokorinIlya: /* Теорема о связи этих понятий */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_{k - 1} - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = k \cdot a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - k \cdot t</tex> (так как <tex>c_1 = k</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - k \cdot t}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots = \dfrac{C}{1 - k \cdot t}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots a_n \cdot t^n + \ldots) \cdot (1 - k \cdot t) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot t}</tex>
*: Таким образом, <tex> 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n + \ldots = \sum\limits_{n = 0}^{\infty}k^n \cdot t^n = \dfrac{1}{1 - k \cdot t}</tex>
*: Частным случаем этой формулы являются соотношения <tex>1 + t + t^2 + \ldots t^n + \cdots = \sum\limits_{n = 0}^{\infty}t^n =\dfrac{1}{1 - t}</tex> и <tex>1 - t + t^2 + \ldots (-1)^n \cdot t^n + \cdots = \sum\limits_{n = 0}^{\infty}(-1)^n \cdot t^n = \dfrac{1}{1 + t}</tex>

* Вычислим производящую функцию последовательности Фибоначчи <tex>f_0 = f_1 = 1, f_n = f_{n - 1} + f_{n - 2}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - t - t^2</tex> (так как <tex>c_1 = c_2 = 1</tex>), а <tex>deg(P) < 3</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{B + At}{1 - t - t^2}, A, B \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots </tex>, тогда <tex>f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots = \dfrac{C}{1 - t - t^2}</tex>, следовательно <tex>(f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots) \cdot (1 - t - t^2) = B + At</tex>
*: Пользуясь правилами перемножения формальных степенных рядов, получаем <tex>p_n = \sum\limits_{i = 0}^{n} f_i \cdot q_{n - i}</tex>, в частности, <tex>B = p_0 = f_0 \cdot q_0 = 1 \cdot 1 = 1</tex>, а <tex>A = p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 1 - 1 = 0</tex>
*: Таким образом, <tex>F(t) = \dfrac{1}{1 - t - t^2}</tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T17:50:56Z

KokorinIlya: /* Примеры применения теоремы */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = k \cdot a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - k \cdot t</tex> (так как <tex>c_1 = k</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - k \cdot t}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots = \dfrac{C}{1 - k \cdot t}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots a_n \cdot t^n + \ldots) \cdot (1 - k \cdot t) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot t}</tex>
*: Таким образом, <tex> 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n + \ldots = \sum\limits_{n = 0}^{\infty}k^n \cdot t^n = \dfrac{1}{1 - k \cdot t}</tex>
*: Частным случаем этой формулы являются соотношения <tex>1 + t + t^2 + \ldots t^n + \cdots = \sum\limits_{n = 0}^{\infty}t^n =\dfrac{1}{1 - t}</tex> и <tex>1 - t + t^2 + \ldots (-1)^n \cdot t^n + \cdots = \sum\limits_{n = 0}^{\infty}(-1)^n \cdot t^n = \dfrac{1}{1 + t}</tex>

* Вычислим производящую функцию последовательности Фибоначчи <tex>f_0 = f_1 = 1, f_n = f_{n - 1} + f_{n - 2}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - t - t^2</tex> (так как <tex>c_1 = c_2 = 1</tex>), а <tex>deg(P) < 3</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{B + At}{1 - t - t^2}, A, B \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots </tex>, тогда <tex>f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots = \dfrac{C}{1 - t - t^2}</tex>, следовательно <tex>(f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots) \cdot (1 - t - t^2) = B + At</tex>
*: Пользуясь правилами перемножения формальных степенных рядов, получаем <tex>p_n = \sum\limits_{i = 0}^{n} f_i \cdot q_{n - i}</tex>, в частности, <tex>B = p_0 = f_0 \cdot q_0 = 1 \cdot 1 = 1</tex>, а <tex>A = p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 1 - 1 = 0</tex>
*: Таким образом, <tex>F(t) = \dfrac{1}{1 - t - t^2}</tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T17:22:30Z

KokorinIlya: /* Примеры применения теоремы */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = k \cdot a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - k \cdot x</tex> (так как <tex>c_1 = k</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - k \cdot x}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots = \dfrac{C}{1 - k \cdot x}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots) \cdot (1 - k \cdot x) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot x}</tex>
*: Таким образом, <tex> 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n + \ldots = \sum\limits_{n = 0}^{\infty}k^n \cdot t^n = \dfrac{1}{1 - k \cdot x}</tex>
*: Частным случаем этой формулы являются соотношения <tex>1 + t + t^2 + \ldots t^n + \cdots = \sum\limits_{n = 0}^{\infty}t^n =\dfrac{1}{1 - x}</tex> и <tex>1 - t + t^2 + \ldots (-1)^n \cdot t^n + \cdots = \sum\limits_{n = 0}^{\infty}(-1)^n \cdot t^n = \dfrac{1}{1 + x}</tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T17:21:47Z

KokorinIlya: /* Примеры применения теоремы */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = k \cdot a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - k \cdot x</tex> (так как <tex>c_1 = k</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - k \cdot x}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots = \dfrac{C}{1 - k \cdot x}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots) \cdot (1 - k \cdot x) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot x}</tex>
*: Таким образом, <tex> 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n + \ldots = \sum\limits_{n = 0}^{\infty}(k \cdot t)^n = \dfrac{1}{1 - k \cdot x}</tex>
*: Частным случаем этой формулы являются соотношения <tex>1 + t + t^2 + \ldots t^n + \cdots = \sum\limits_{n = 0}^{\infty}(t)^n =\dfrac{1}{1 - x}</tex> и <tex>1 - t + t^2 + \ldots (-1)^n \cdot t^n + \cdots = \sum\limits_{n = 0}^{\infty}(-1)^n \cdot t^n = \dfrac{1}{1 + x}</tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T17:19:40Z

KokorinIlya: /* Примеры применения теоремы */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = k \cdot a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - k \cdot x</tex> (так как <tex>c_1 = k</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - k \cdot x}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots = \dfrac{C}{1 - k \cdot x}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots) \cdot (1 - k \cdot x) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot x}</tex>
*: Таким образом, <tex> 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n + \ldots = \dfrac{1}{1 - k \cdot x}</tex>
*: Частным случаем этой формулы являются соотношения <tex>1 + t + t^2 + \ldots t^n + \cdots = \dfrac{1}{1 - x}</tex> и <tex>1 - t + t^2 + \ldots (-1)^n \cdot t^n + \cdots = \dfrac{1}{1 + x}</tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T17:17:13Z

KokorinIlya: /* Примеры применения теоремы */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = k \cdot a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - k \cdot x</tex> (так как <tex>c_1 = k</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - k \cdot x}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots = \dfrac{C}{1 - k \cdot x}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots) \cdot (1 - k \cdot x) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot x}</tex>
*: Таким образом, <tex> 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n + \ldots = \dfrac{1}{1 - k \cdot x}</tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T17:16:18Z

KokorinIlya: /* Примеры применения теоремы */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = k \cdot a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - k \cdot x</tex> (так как <tex>c_1 = k</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - k \cdot x}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots = \dfrac{C}{1 - k \cdot x}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots) \cdot (1 - k \cdot x) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot x}</tex>
*: Таким образом, <tex> 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n = \dfrac{1}{1 - k \cdot x}</tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T17:09:33Z

KokorinIlya: /* Примеры применения теоремы */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - x</tex> (так как <tex>c_1 = 1</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - x}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots = \dfrac{C}{1 - x}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots) \cdot (1 - x) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - x}</tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T17:09:15Z

KokorinIlya: /* Примеры применения теоремы */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}

== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - x</tex> (так как <tex>c_1 = 1</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - x}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots = \dfrac{C}{1 - x}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots) \cdot (1 - x) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1<tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - x}<tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T16:54:13Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T16:50:28Z

KokorinIlya: /* Теорема о связи этих определений */

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T16:50:16Z

KokorinIlya: /* Теорема о связи */

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T16:50:00Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T16:49:26Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T16:46:58Z

KokorinIlya: /* Необходимые определения */

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T16:46:32Z

KokorinIlya: /* Необходимые определения */

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T16:43:25Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:43:21Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:38:48Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:35:47Z

KokorinIlya: /* Необходимые определения */

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:35:30Z

KokorinIlya: /* Источники информации */

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:32:43Z

KokorinIlya: /* Необходимые определения */

Производящая функция

2018-03-04T15:32:05Z

KokorinIlya:

{{Определение
|id=main
|definition=
'''Производящая функция''' (англ. ''generating function'') — это формальный степенной ряд:
<center>
<tex>G(z)=\sum\limits_{n=0}^\infty a_n z^n</tex>,
</center>
порождающий (производящий) последовательность <tex>(a_0, a_1, a_2, \ldots)</tex>.
}}
Метод производящих функций был разработан Эйлером в 1750-х годах.

__TOC__

== Применение ==
Производящая функция используется для:

* Компактной записи информации о последовательности.
* Нахождения зависимости <tex>a_n(n)</tex> для последовательности <tex>a_n</tex>, заданной рекуррентным соотношением. Например, для чисел Фибоначчи.
* Нахождения рекуррентного соотношения для последовательности {{---}} вид производящей функции может помочь найти формулу.
* Исследования асимптотического поведения последовательности.
* Доказательства тождеств с последовательностями.
* Решения задачи подсчета объектов в комбинаторике. Например, в доказательстве [[Нахождение количества разбиений числа на слагаемые|пентагональной теоремы]] или в задаче нахождения количества расстановок <tex>m</tex> ладей на доске <tex>n \times n</tex>.
* Вычисления бесконечных сумм.

== Примеры производящих функций ==
Рассмотрим производящие функции для различных комбинаторных последовательностей:

* <tex>\prod\limits_{ n = 1}^\infty(1-x^n)</tex> {{---}} производящая функция для разности количества разбиений числа <tex>n</tex> в четное и нечетное число различных слагаемых. Например, коэффициент при <tex>x^5</tex> равен <tex>+1</tex>, потому что существует два разбиения на четное число различных слагаемых <tex>(4+1; 3+2)</tex> и одно на нечетное (<tex>5</tex>). Правильность этого легко осознать, если понять, что каждая скобка представляет какое-то слагаемое и мы можем его взять (второе слагаемое {{---}} <tex>-x^k</tex>) или не взять (первое {{---}} <tex>1</tex>). Эта производящая функция используется в комбинаторном доказательстве пентагональной теоремы.

* <tex> \prod\limits_{n=1}^\infty \dfrac{1}{1-x^n}</tex> {{---}} производящая функция для последовательности <tex>p_n</tex>, где <tex>p_i</tex> {{---}} число разбиений числа <tex>i</tex> на слагаемые.

* <tex>\prod\limits_{ n = 1}^\infty(1+x^n)</tex> {{---}} производящая функция для последовательности <tex>d_n</tex>, где <tex>d_i</tex> {{---}} число разбиений на различные слагаемые.

* <tex>\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})</tex> {{---}} производящая функция для последовательности <tex>l_n</tex>, где <tex>l_i</tex> {{---}} число разбиений на нечётные слагаемые. С помощью метода производящих функций можно доказать, что производящие функции последовательностей равны, соответственно <tex>d_n = l_n </tex>: <tex>\prod\limits_{n=1}^\infty(1+x^{ n})=\prod\limits_{n=1}^\infty \dfrac{1-x^{2n}}{1-x^n}=\dfrac{1-x^2}{1-x}\dfrac{1-x^4}{1-x^2}\dfrac{1-x^6}{1-x^3}\ldots=</tex>

<tex>=\dfrac{1}{1-x}\dfrac{1}{1-x^3}\dfrac{1}{1-x^5}\ldots=\prod\limits_{n=1}^\infty(1+x^{ 2n - 1})</tex>

== Примеры решений задач методом производящих функций ==
=== Решение рекуррентных соотношений ===
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}}
[[Числа Каталана | числа Каталана]]. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последовательности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что <tex>z</tex> достаточно мало.

Пусть последовательность <tex>(a_0, a_1, a_2, \ldots)</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \geqslant 0</tex>) в замкнутом виде. Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:

# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>, равно <tex>k</tex>):
#: <tex>a_0=\ldots,</tex>
#: <tex>a_1=\ldots,</tex>
#: <tex>\ldots</tex>
#: <tex>a_{k-1}=\ldots,</tex>
#: <tex>a_{n}=\ldots, n \geqslant k.</tex>
# Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n \geqslant 0 </tex>.
# В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
# Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.

Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:

<tex>a_0= 1,</tex>

<tex>a_1= 2,</tex>

<tex>a_n= 6a_{ n - 1}-8a_{n-2}+n, n \geqslant 2</tex>

Запишем производящую функцию для этой последовательности и преобразуем правую часть:

<tex>G(z)=a_0+a_1z+\sum\limits_{n=2}^\infty(6a_{ n - 1}-8a_{n-2}+n) z^n</tex>

<tex>G(z)=a_0+a_1z+6\sum\limits_{n=2}^\infty a_ { n-1}
z^n - 8\sum\limits_{n=2}^\infty a_ { n-2}
z^n+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z\sum\limits_{n=1}^\infty a_ { n }
z^n - 8z^2\sum\limits_{n=0}^\infty a_ { n }
z^n+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=a_0+a_1z+6z(G(z)-a_0) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex>

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\sum\limits_{n=2}^\infty n z^n</tex>

Для того, чтобы замкнуть последнюю сумму воспользуемся очень важным приемом, который используется при преобразовании производящих функций. Фактически мы имеем дело с последовательностью <tex>nb_n</tex> (в нашем случае последовательность <tex>b_n= (1, 1, 1, \ldots)</tex>). Такая последовательность получается путём дифференцирования функции <tex>B(z)</tex>, производящей для <tex>b_n</tex>, с последующим умножением результата на <tex>z</tex>:

<tex>zB'(z)=z(\sum\limits_{n=0}^\infty b_n z^n)'=z\sum\limits_{ n = 1}^\infty nb_n z^{n-1}=\sum\limits_{n=0}^\infty nb_n z^n</tex>

Тогда замкнем последнее слагаемое следующим образом:

<tex>\sum\limits_{n=2}^\infty n z^n=z \sum\limits_{n=2}^\infty n z^{n-1}= z(\sum\limits_{ n = 2}^\infty z^n)'</tex>

<tex>\sum\limits_{n=2}^\infty z^n=\sum\limits_{n=0}^\infty z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}</tex>

<tex>z(\dfrac{ z ^ 2}{1-z})'=\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Таким образом, наше последнее слагаемое примет вид:

<tex>G(z)=1-4z+6zG(z) - 8z^2G(z)+\dfrac{z^2(2-z)}{(1-z)^2}</tex>

Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:

<tex>G(z)=\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}</tex>

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей <ref>[http://www.genfunc.ru/theory/pril04/ О разложении рациональной функции в ряд]</ref>:

<tex> G(z) =\dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}</tex>

Разложим первое слагаемое в ряд, используя расширенные биномиальные коэффициенты <ref>[http://www.genfunc.ru/theory/pril02/ Расширенные биномиальные коэффициенты]</ref>:

<tex>\dfrac{ 1}{(1-z)^2}=(1-z)^{-2}=\sum\limits_{n=0}^{\infty} {-2\choose n}(-z)^n=\sum\limits_{n=0}^{\infty} (-1)^n{n+1\choose 1}(-z)^n=\sum\limits_{n=0}^{\infty}(n+1)z^n</tex>

<tex>G(z)=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\sum\limits_{n=0}^{\infty} (n+1)z^n +\dfrac{7}{9}\sum\limits_{n=0}^{\infty} z^n - \dfrac{1}{2}\sum\limits_{n=0}^{\infty} 2^n z^n + \dfrac{7}{18}\sum\limits_{n=0}^{\infty} 4^n z^n</tex>

<tex>a_n=\dfrac{n+1}{3}+\dfrac{7}{9}-\dfrac{2^n}{2}+\dfrac{7 \cdot 4^n}{18}=\dfrac{7 \cdot 4^n+6n+20}{18}-2^{n-1}</tex>

=== Расчет дисперсии геометрического распределения ===
Метод производящих функций также используется для нахождения [[Дисперсия случайной величины | математического ожидания и дисперсии]] различных распределений в теории вероятностей. Например, в геометрическом распределении <ref>[http://ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5 Геометрическое распределение]</ref> для нахождения дисперсии <tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2</tex> нужно найти два мат. ожидания:

* <tex>\operatorname{E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} </tex>

* <tex>\operatorname{E}(\xi^2) = \sum\limits_{n=1}^{\infty}n^{2}p(1-p)^{n-1}</tex>

которые фактически являются производящими функциями последовательностей <tex>1, 2, 3\ldots</tex> и <tex>1, 4, 9\ldots</tex>:

* <tex>\operatorname{ E}(\xi)=\sum\limits_{n=1}^{\infty}n p(1-p)^{n-1} = </tex>

<tex>= \sum\limits_{n=0}^{\infty}(n+1) p(1-p)^{n} = </tex>

<tex>= \sum\limits_{n=0}^{\infty}n p(1-p)^{n} + \sum\limits_{n=1}^{\infty} p(1-p)^{n-1} = </tex>

<tex>= (1-p) \operatorname{E}(\xi) +1 \Rightarrow \operatorname{E}(\xi) = \dfrac{1}{p}</tex>

* <tex>\operatorname{E}(\xi^2) = p\sum\limits_{n=1}^{\infty}n^{2}(1-p)^{n-1} =</tex>

<tex>=p\sum\limits_{n=1}^{\infty}n(n+1)(1-p)^{n-1} - p\sum\limits_{n=1}^{\infty}n(1-p)^{n-1} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\sum\limits_{n=1}^{\infty}(1-p)^{n+1} + p\dfrac{\operatorname{d}}{\operatorname{d}p}\sum\limits_{n=1}^{\infty}(1-p)^{n} =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\sum\limits_{ n = 0}^{\infty}(1-p)^{n}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ 1}{1-(1-p)} \cdot(1-p)^2\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1}{1-(1-p)}\cdot(1-p)\right) =</tex>

<tex>= p\dfrac{\operatorname{d}^{2}}{\operatorname{d}p^{2}}\left(\dfrac{ (1 - p) ^ 2}{p}\right) +p\dfrac{\operatorname{d}}{\operatorname{d}p}\left(\dfrac{ 1 - p}{p}\right) =</tex>

<tex>= p\cdot\dfrac{2}{p^3} - p\cdot\dfrac{1}{p^2} = \dfrac{2}{p^{2}} - \dfrac{1}{p} = \dfrac{2-p}{p^{2}}</tex>.

Тогда:

<tex>\operatorname{D}(\xi)=\operatorname{E}(\xi^2)-(\operatorname{E}(\xi))^2= \dfrac{2-p}{p^{2}}-\dfrac{1}{p^2}=\dfrac{1-p}{p^2}</tex>

=== Пример задачи на нахождение производящей функции ===
{{Задача
| about =
| definition = Рассмотрим множество путей на прямой, состоящих из шагов длины <tex>1</tex> вправо и влево. Найдите производящую функцию для числа таких путей из <tex>n</tex> шагов, начинающихся в <tex>0</tex> и оканчивающихся в <tex>0</tex>.
}}
Заметим, что для того, чтобы закончить путь в <tex>0</tex>, необходимо совершить равное число шагов вправо и влево. Тогда задача сводится к тому, чтобы выбрать <tex>\dfrac{n}{2}</tex> позиций для, например, шагов вправо из всего <tex>n</tex> шагов. Тогда ответом будет сумма от нуля до бесконечности по <tex>n</tex> всех <tex>C^{n}_{2n}</tex>. То есть:
<tex>
g(x) = \sum\limits_{0}^{\infty} C^{n}_{2n} x^n
</tex>
Рассмотрим <tex>f(x) = \sum\limits_{0}^{\infty} C_n x^n </tex>, где <tex>C_n</tex> {{---}} [[Числа Каталана | число Каталана]]. Тогда, заметим что <tex>f'(x) = \sum\limits_{0}^{\infty} n C_n x^{n-1} </tex>. Так как <tex>C_n = \dfrac{1}{n+1} C_{2n}^n </tex>, то справедливо равенство:
<tex>
g(x) = (n+1)f(x) = xf'(x) + f(x)
</tex>

Мы знаем, что производящая функция для чисел Каталана равна <tex>f(x) = \dfrac{1-\sqrt{1-4x}}{2x}</tex>. Найдем <tex>f'(x)</tex>.

<tex>
f'(x) = \dfrac{\dfrac{4x}{\sqrt{1-4x}} - 2 + 2\sqrt{1-4x}}{4x^2} = \dfrac{1 - 2x - \sqrt{1-4x}}{2x^2 \sqrt{1-4x}}
</tex>

Соответственно, ответом будет производящая функция вида:

<tex>
g(x) = \dfrac{1 - 2x - \sqrt{1-4x}}{2x \sqrt{1-4x}} + \dfrac{1-\sqrt{1-4x}}{2x}
</tex>

{{Задача
| about =
| definition = Рассмотрим множество путей на прямой, состоящих из шагов длины <tex>1</tex> вправо и влево. Найдите производящую функцию для числа таких путей из <tex>n</tex> шагов, начинающихся и оканчивающихся в <tex>0</tex> и не заходящих в отрицательную полупрямую.
}}

Заметим, что задача аналогична [[Правильные скобочные последовательности | Правильной скобочной последовательности]]. Тогда производящей функцией для нашей задачи будет производящая функция для правильной скобочной последовательности, а именно:

<tex>
g(x) = \dfrac{1-\sqrt{1-4x}}{2x}
</tex>

== Приложения ==
=== Примеры простых производящих функций ===
На последнем шаге приведения производящей функции к замкнутому виду требуется разложить полученные слагаемые в ряд. Для этого можно воспользоваться таблицей основных производящих функций <ref>[http://www.genfunc.ru/theory/pril03/ Таблица производящих функций]</ref>.

Все суммы выполняются по переменной <tex>n</tex> от <tex>0</tex> до <tex>\infty</tex>. Элементы последовательности нумеруются от <tex>0</tex>.
{| class="wikitable" style="width:30cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| '''Последовательность''' || '''Производящая функция в виде ряда''' || '''Производящая функция в замкнутом виде'''
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0,\ldots)</tex> || <tex>1</tex> || <tex>1</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 0, \ldots, 0, 1, 0, 0\ldots)</tex> (<tex>m</tex> нулей в начале) || <tex>z^m</tex> || <tex>z^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, 1,\ldots)</tex> || <tex>\sum\limits z^n</tex> || <tex>\dfrac{1}{1-z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 0, 0, \ldots, 0, 1, 0, 0, \ldots 0, 1, 0, 0\ldots)</tex> (повторяется через <tex>m</tex>) || <tex>\sum\limits z^{nm}</tex> || <tex>\dfrac{1}{1-z^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -1, 1, -1,\ldots)</tex> || <tex>\sum\limits (-1)^nz^n</tex> || <tex>\dfrac{1}{1+z}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 3, 4,\ldots)</tex> || <tex>\sum\limits (n+1)z^n</tex> || <tex>\dfrac{1}{(1-z)^2}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 2, 4, 8, 16,\ldots)</tex> || <tex>\sum\limits 2^nz^n</tex> || <tex>\dfrac{1}{(1-2z)}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, r, r^2, r^3,\ldots)</tex> || <tex>\sum\limits r^nz^n</tex> || <tex>\dfrac{1}{(1-rz)}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>{m\choose 0}, {m\choose 1}, {m\choose 2}, {m\choose 3},\ldots</tex><tex>)</tex> || <tex>\sum\limits {m\choose n}</tex> <tex>z^n</tex> || <tex>(1+z)^m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m}\choose m}, {{m+1}\choose m}, {{m+2}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n-1}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^m}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(</tex><tex>1, {{m+1}\choose m}, {{m+2}\choose m}, {{m+3}\choose m},\ldots</tex><tex>)</tex> || <tex>\sum\limits {{m+n}\choose n}</tex> <tex>z^n</tex> || <tex>\dfrac{1}{(1-z)^{m+1}}</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(0, 1, -\dfrac{1}{2}, \dfrac{1}{3}, -\dfrac{1}{4},\ldots)</tex> || <tex>\sum\limits \dfrac{(-1)^{n+1}}{n}</tex> <tex>z^n</tex> || <tex>\ln(1+z)</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, 1, \dfrac{1}{2}, \dfrac{1}{6}, \dfrac{1}{24},\ldots)</tex> || <tex>\sum\limits \dfrac{1}{n!}</tex> <tex>z^n</tex> || <tex>e^z</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(1, -\dfrac{1}{2!}m^2, \dfrac{1}{4!}m^4, -\dfrac{1}{6!}m^6, \dfrac{1}{8!}m^8,\ldots)</tex> || <tex>\sum\limits \dfrac{1}{(2n)!}</tex> <tex>m^{(2n)}</tex> || <tex>\cos m</tex>
|-align="left" bgcolor=#FFFFFF
| <tex>(m, -\dfrac{1}{3!}m^3, \dfrac{1}{5!}m^5, -\dfrac{1}{7!}m^7, \dfrac{1}{9!}m^9,\ldots)</tex> || <tex>\sum\limits \dfrac{1}{(2n-1)!}</tex> <tex>m^{(2n-1)}</tex> || <tex>\sin m</tex>
|}

== Примечания ==
<references/>

== Источники информации ==
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://www.genfunc.ru/ Производящие функции]
* [http://en.wikipedia.org/wiki/Generating_function Wikipedia {{---}} Generating function]
* [[Нахождение количества разбиений числа на слагаемые|Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
* Graham, Knuth, and Patashnik: Concrete Mathematics

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Подсчёт числа объектов]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:31:27Z

KokorinIlya:

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Производящая функция <tex>F(t)</tex> называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> - многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}

== Теорема ==

{{Теорема
|id=th_main.
|statement=<tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg P(t) < k, \forall n \geqslant k p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg Q(t) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>\forall i: 1 \leqslant i \leqslant k: q_i = -c_i</tex>

<tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>\:</tex>

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg Q(t) = k, deg P(t) < k</tex>
}}

== Смотри также ==
[[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]

[[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо - Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:29:50Z

KokorinIlya: /* Смотри также */

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Производящая функция <tex>F(t)</tex> называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> - многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, ..., a_n, ... </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 ... a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>
}}

== Теорема ==

{{Теорема
|id=th_main.
|statement=<tex>a_0, a_1, ..., a_n, ... </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k</tex>.

Так как <tex>deg P(t) < k, \forall n \geqslant k p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + ... + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + ... + a_{0} \cdot 0 = 0</tex> (так как <tex>deg Q(t) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>\forall i: 1 \leqslant i \leqslant k: q_i = -c_i</tex>

<tex>a_n - c_1 \cdot a_{n - 1} - ... -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>\:</tex>

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + ... + a_k \cdot t^k + ... + a_n \cdot t^n + ...</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - ... - c_1 \cdot a_{k - 1} \cdot t^k - ... - c_1 \cdot a_{n - 1} \cdot t^n - ...</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - ... - c_2 \cdot a_{k - 2} \cdot t^k - ... - c_2 \cdot a_{n - 2} \cdot t^n - ...</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + ... - c_k \cdot a_0 \cdot t^k - ... - c_k \cdot a_{n - k} \cdot t^n + ...</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + ... + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + ...</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg Q(t) = k, deg P(t) < k</tex>
}}

== Смотри также ==
[[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]

[[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо - Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:29:38Z

KokorinIlya:

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Производящая функция <tex>F(t)</tex> называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> - многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, ..., a_n, ... </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 ... a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>
}}

== Теорема ==

{{Теорема
|id=th_main.
|statement=<tex>a_0, a_1, ..., a_n, ... </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k</tex>.

Так как <tex>deg P(t) < k, \forall n \geqslant k p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + ... + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + ... + a_{0} \cdot 0 = 0</tex> (так как <tex>deg Q(t) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>\forall i: 1 \leqslant i \leqslant k: q_i = -c_i</tex>

<tex>a_n - c_1 \cdot a_{n - 1} - ... -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>\:</tex>

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + ... + a_k \cdot t^k + ... + a_n \cdot t^n + ...</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - ... - c_1 \cdot a_{k - 1} \cdot t^k - ... - c_1 \cdot a_{n - 1} \cdot t^n - ...</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - ... - c_2 \cdot a_{k - 2} \cdot t^k - ... - c_2 \cdot a_{n - 2} \cdot t^n - ...</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + ... - c_k \cdot a_0 \cdot t^k - ... - c_k \cdot a_{n - k} \cdot t^n + ...</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + ... + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + ...</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg Q(t) = k, deg P(t) < k</tex>
}}

== Смотри также ==
[[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
[[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо - Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:27:45Z

KokorinIlya:

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Производящая функция <tex>F(t)</tex> называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> - многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, ..., a_n, ... </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 ... a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>
}}

== Теорема ==

{{Теорема
|id=th_main.
|statement=<tex>a_0, a_1, ..., a_n, ... </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k</tex>.

Так как <tex>deg P(t) < k, \forall n \geqslant k p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + ... + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + ... + a_{0} \cdot 0 = 0</tex> (так как <tex>deg Q(t) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>\forall i: 1 \leqslant i \leqslant k: q_i = -c_i</tex>

<tex>a_n - c_1 \cdot a_{n - 1} - ... -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>\:</tex>

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + ... + a_k \cdot t^k + ... + a_n \cdot t^n + ...</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - ... - c_1 \cdot a_{k - 1} \cdot t^k - ... - c_1 \cdot a_{n - 1} \cdot t^n - ...</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - ... - c_2 \cdot a_{k - 2} \cdot t^k - ... - c_2 \cdot a_{n - 2} \cdot t^n - ...</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + ... - c_k \cdot a_0 \cdot t^k - ... - c_k \cdot a_{n - k} \cdot t^n + ...</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + ... + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + ...</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg Q(t) = k, deg P(t) < k</tex>
}}

== Источники информации ==
С. А. Ландо - Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:23:37Z

KokorinIlya:

== Необходимые определения ==

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Производящая функция <tex>F(t)</tex> называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> - многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, ..., a_n, ... </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 ... a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>
}}

== Теорема ==

{{Теорема
|id=th_main.
|statement=<tex>a_0, a_1, ..., a_n, ... </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k</tex>.

Так как <tex>deg P(t) < k, \forall n \geqslant k p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + ... + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + ... + a_{0} \cdot 0 = 0</tex> (так как <tex>deg Q(t) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>\forall i: 1 \leqslant i \leqslant k: q_i = -c_i</tex>

<tex>a_n - c_1 \cdot a_{n - 1} - ... -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>\:</tex>

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + ... + a_k \cdot t^k + ... + a_n \cdot t^n + ...</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - ... - c_1 \cdot a_{k - 1} \cdot t^k - ... - c_1 \cdot a_{n - 1} \cdot t^n - ...</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - ... - c_2 \cdot a_{k - 2} \cdot t^k - ... - c_2 \cdot a_{n - 2} \cdot t^n - ...</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + ... - c_k \cdot a_0 \cdot t^k - ... - c_k \cdot a_{n - k} \cdot t^n + ...</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + ... + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + ...</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg Q(t) = k, deg P(t) < k</tex>
}}

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-04T15:23:01Z

KokorinIlya:

=== Необходимые определения ===

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Производящая функция <tex>F(t)</tex> называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> - многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, ..., a_n, ... </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 ... a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>
}}

=== Теорема ===

{{Теорема
|id=th_main.
|statement=<tex>a_0, a_1, ..., a_n, ... </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k</tex>.

Так как <tex>deg P(t) < k, \forall n \geqslant k p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + ... + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + ... + a_{0} \cdot 0 = 0</tex> (так как <tex>deg Q(t) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>\forall i: 1 \leqslant i \leqslant k: q_i = -c_i</tex>

<tex>a_n - c_1 \cdot a_{n - 1} - ... -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>\:</tex>

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + ... + a_k \cdot t^k + ... + a_n \cdot t^n + ...</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - ... - c_1 \cdot a_{k - 1} \cdot t^k - ... - c_1 \cdot a_{n - 1} \cdot t^n - ...</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - ... - c_2 \cdot a_{k - 2} \cdot t^k - ... - c_2 \cdot a_{n - 2} \cdot t^n - ...</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + ... - c_k \cdot a_0 \cdot t^k - ... - c_k \cdot a_{n - k} \cdot t^n + ...</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + ... + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + ...</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg Q(t) = k, deg P(t) < k</tex>
}}

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-02T22:35:13Z

KokorinIlya:

{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Производящая функция <tex>F(t)</tex> называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \frac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> - многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, ..., a_n, ... </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 ... a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>
}}

{{Теорема
|id=th_main.
|statement=<tex>a_0, a_1, ..., a_n, ... </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \frac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \frac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k</tex>.

Так как <tex>deg P(t) < k, \forall n \geqslant k p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + ... + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + ... + a_{0} \cdot 0 = 0</tex> (так как <tex>deg Q(t) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>\forall i: 1 \leqslant i \leqslant k: q_i = -c_i</tex>

<tex>a_n - c_1 \cdot a_{n - 1} - ... -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>\:</tex>

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + ... + a_k \cdot t^k + ... + a_n \cdot t^n + ...</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - ... - c_1 \cdot a_{k - 1} \cdot t^k - ... - c_1 \cdot a_{n - 1} \cdot t^n - ...</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - ... - c_2 \cdot a_{k - 2} \cdot t^k - ... - c_2 \cdot a_{n - 2} \cdot t^n - ...</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + ... - c_k \cdot a_0 \cdot t^k - ... - c_k \cdot a_{n - k} \cdot t^n + ...</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + ... + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + ...</tex>

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k)</tex>,

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg Q(t) = k, deg P(t) < k</tex>
}}

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-02T22:04:30Z

KokorinIlya:

Арифметические действия с формальными степенными рядами

2018-03-02T21:54:51Z

KokorinIlya: /* Простейшие операции */

==Простейшие операции==
Рассмотрим два [[Производящая функция|формальных степенных ряда]] <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex>.
{{Определение
|definition = '''Суммой''' (англ. ''addition'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(s) + B(s) = (a_0 + b_0) + (a_1 + b_1) s + (a_2 + b_2) s^2 + \dots</tex>.
}}
{{Определение
|id=def_mul
|definition = '''Произведением''' (англ. ''multiplication'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(s)B(s) = a_0 b_0 + (a_0 b_1 + a_1 b_0) s + (a_0 b_2 + a_1 b_1 + a_2 b_0) s^2 + \dots</tex>.
}}
Операции сложения и умножения формальных степенных рядов коммутативны и ассоциативны.

==Деление==
{{Определение
|id = div
|definition=
'''Обратным по умножению''' (англ. ''multiplicative inverse'') к формальному степенному ряду <tex>A(s)</tex> называется такой ряд <tex>B(s)</tex>, что <tex>A(s)B(s) = 1</tex>. Обозначение: <tex>B(s) = A^{-1}(s)</tex>.
}}

{{Лемма
|statement = Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + a_3 s^3 + \dots </tex> {{---}} формальный степенной ряд, причем <tex>A(0) \ne 0</tex>. Тогда существует единственный обратный по умножению к <tex>A(s)</tex> ряд <tex>B(s) = b_0 + b_1 s + b_2 s^2 + b_3 s^3 + \dots </tex>.
|proof =
:Распишем <tex>A(s)B(s)</tex> по формуле произведения рядов: <tex>A(s)B(s) = a_0 b_0 + (a_0 b_1 + a_1 b_0)s + (a_0 b_2 + a_1 b_1 + a_2 b_0) s^2 + \dots</tex>. Заметим, что условие <tex>A(s)B(s) = 1</tex> выполнено только в том случае, если <tex>a_0 b_0 = 1</tex>, а все остальные слагаемые полученного ряда равны нулю.
:Докажем по индукции, что такой ряд <tex>B</tex> единственен. Нам известно, что <tex>b_0 = \dfrac{1}{a_0}</tex>. Пусть теперь все коэффициенты ряда <tex>B</tex> вплоть до степени <tex>n - 1</tex> однозначно определены. Коэффициент при <tex>s^n</tex> определяется из условия <tex>a_0 b_n + a_1 b_{n - 1} + \dots + a_n b_0 = 0</tex>. Это линейное уравнение на <tex>b_n</tex>, причем коэффициент <tex>a_0</tex> при <tex>b_n</tex> отличен от нуля. Такое уравнение имеет единственное решение.
}}

{{Определение
|definition=
'''Делением''' (англ. ''division'') формальных степенных рядов <tex>A(s)</tex> и <tex>B(s)</tex> называется операция <tex>\dfrac{A(s)}{B(s)} = A(s) B(s)^{-1}</tex> (при условии существования у <tex>B(s)</tex> обратного).
}}

===Примеры===
#Допустим, надо построить обратный ряд для <tex>A(s) = 1 + s</tex>. Воспользуемся леммой:
#:<tex>b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1</tex>
#:<tex>a_0 b_1 + a_1 b_0 = 0 \Rightarrow b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{1 \cdot 1}{1} = -1</tex>
#:<tex>a_0 b_2 + a_1 b_1 + a_2 b_0 = 0 \Rightarrow b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{1 \cdot (-1) + 0}{1} = 1</tex>
#:<tex>\dots</tex>
#:<tex>b_n = - \dfrac{a_1 b_{n - 1}}{a_0} = -b_{n - 1}</tex>
#:<tex>B(s) = 1 - s + s^2 - s^3 + \dots</tex>
#Пусть теперь надо построить обратный ряд для <tex>A(s) = 1 - s - s^2</tex>:
#:<tex>b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1</tex>
#:<tex>b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{(-1) \cdot 1}{1} = 1</tex>
#:<tex>b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{(-1) \cdot 1 + (-1) \cdot 1}{1} = 2</tex>
#:<tex>b_3 = - \dfrac{a_1 b_2 + a_2 b_1}{a_0} = - \dfrac{(-1) \cdot 2 + (-1) \cdot 1}{1} = 3</tex>
#:<tex>\dots</tex>
#:<tex>b_n = - \dfrac{a_1 b_{n - 1} + a_2 b_{n - 2}}{a_0} = b_{n - 1} + b_{n - 2}</tex>
#:<tex>B(s) = 1 + s + 2 s^2 + 3 s^3 + \dots</tex>

==Композиция==
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex> {{---}} два формальных степенных ряда, причем <tex>B(0) = b_0 = 0</tex>.

{{Определение
|definition =
'''Композицией (подстановкой)''' (англ. ''composition'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(B(t)) = a_0 + a_1 b_1 t + (a_1 b_2 + a_2 b_1^2) t^2 + (a_1 b_3 + 2 a_2 b_1 b_2 + a_3 b_1^3) t^3 + \dots</tex>.
}}
Если, например, <tex>B(t) = -t</tex>, то <tex>A(B(t)) = A(-t) = a_0 -a_1 t + a_2 t^2 - a_3 t^3 + \dots</tex>.

Операция подстановки в случае, когда <tex>B(0) \ne 0</tex>, не определена. (При попытке подставить такой ряд для вычисления коэффициентов результата возникает необходимость суммирования бесконечных числовых рядов).

==Обратный ряд==
{{Определение
|definition=
'''Левым обратным''' (англ. ''left inverse'') по операции подстановки формальным степенным рядом для ряда <tex>B(t)</tex> называется такой ряд <tex>A(s)</tex>, что <tex>A(B(t)) = t</tex>. Аналогично, '''правым обратным''' (англ. ''right inverse'') формальным степенным рядом для <tex>B(t)</tex> называется такой <tex>C(u)</tex>, что <tex>B(C(u)) = u</tex>.
}}

{{Теорема
|about = об обратном формальном степенном ряде
|statement = Пусть ряд <tex>B(t) = b_0 + b_1 t + b_2 t^2 + b_3 t^3 + \dots</tex> таков, что <tex>B(0) = b_0 = 0</tex>, а <tex>b_1 \ne 0</tex>. Тогда существуют такие ряды <tex> A(s) = a_1 s + a_2 s^2 + a_3 s^3 + \dots</tex>, <tex>A(0) = 0</tex> и <tex>C(u) = c_1 u + c_2 u^2 + c_3 u^3 + \dots</tex>, <tex>C(0) = 0</tex>, что <tex>A(t)</tex> является левым обратным, а <tex>C(u)</tex> {{---}} правым обратным для <tex>B(s)</tex>. При этом, ряды <tex>A</tex> и <tex>C</tex> единственны.
|proof =
:Докажем по индукции существование и единственность левого обратного ряда. Доказательство для правого аналогично.
:Будем определять коэффициенты ряда <tex>A</tex> последовательно. Поскольку <tex>A(B(t)) = t</tex>, <tex>a_1 b_1 = 1</tex>, откуда <tex>a_1 = \dfrac{1}{b_1}</tex>. Все остальные коэффициенты результирующего ряда при этом равны нулю.
:Предположим теперь, что коэффициенты <tex>a_1, a_2, \dots, a_n</tex> уже определены. Коэффициент <tex>a_{n+1}</tex> определяется из условия <tex>a_{n+1} b_1^{n+1} + \dots = 0</tex>, где точками обозначен некоторый многочлен от <tex>a_1, \dots, a_n</tex> и <tex>b_1, \dots, b_n</tex>. Тем самым, условие представляет собой линейное уравнение на <tex>a_{n+1}</tex>, причем коэффициент <tex>b_1^{n+1}</tex> при <tex>a_{n+1}</tex> отличен от нуля. Такое уравнение имеет единственное решение, и теорема доказана.
}}
===Пример===
Найдем левый обратный ряд для <tex>B(t) = t + t^2</tex>:
:<tex>a_0 = 0</tex>
:<tex>a_1 = \dfrac{1}{b_1} = 1</tex>
:<tex>a_1 b_2 + a_2 b_1^2 = 0 \Rightarrow a_2 = - \dfrac{a_1 b_2}{b_1^2} = - \dfrac{1 \cdot 1}{1^2} = -1</tex>
:<tex>a_1 b_3 + 2 a_2 b_1 b_2 + a_3 b_1^3 = 0 \Rightarrow a_3 = - \dfrac{a_1 b_3 + 2 a_2 b_1 b_2}{b_1^3} = - \dfrac{1 \cdot 0 + 2 \cdot (-1) \cdot 1}{1^3} = 2</tex>
:<tex>\dots</tex>
:<tex>A(s) = s - s^2 + 2 s^3 + \dots</tex>

==Сдвиги==
===Сдвиг вправо===
Сдвиг ряда вправо на <tex>k</tex> получается домножением его на <tex>s^k</tex>. Например, пусть исходный ряд <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex>. Сдвинем его на <tex>k</tex> вправо: <tex>B(s) = s^k \cdot A(s) = a_0 s^k + a_1 s^{k + 1} + a_2 s^{k + 2} + \dots = 0 + 0 s + 0 s^2 + \dots + a_0 s^k + a_1 s^{k + 1} + \dots</tex>.

===Сдвиг влево===
Сдвинуть ряд влево на <tex>k</tex> можно, вычтя из него первые <tex>k</tex> слагаемых и затем разделив его на <tex>s^k</tex>. Например, сдвинем ряд <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> на <tex>k</tex> влево: <tex>B(s) = \dfrac{A(s) - (a_0 + a_1 s + a_2 s^2 + \dots + a_{k - 1} s^{k - 1})}{s^k} = a_k + a_{k + 1} s + a_{k + 2} s^2 + \dots</tex>.

Сдвиги могут быть полезны для упрощения вычисления производящих функций.
Например, попробуем получить функцию для чисел Фибоначчи, используя сдвиги. Пусть формальный степенной ряд для нее равен <tex>F(s) = f_0 + f_1 s + f_2 s^2 + \dots</tex>, при этом <tex>f_0 = f_1 = 1</tex>, <tex>f_n = f_{n - 2} + f_{n - 1}, n > 1</tex>. Рассмотрим сумму этого ряда и ряда, полученного из него сдвигом на <tex>1</tex> вправо: <tex>F(s) + s \cdot F(s) = (f_0 + f_1 s + f_2 s^2 + f_3 s^3 + \dots) + (0 + f_0 s + f_1 s^2 + f_2 s^3 + \dots) = (f_0 + 0) + (f_1 + f_0) s + (f_2 + f_1) s^2 + (f_3 + f_2) s^3 + \dots = f_1 + f_2 s + f_3 s^2 + f_4 s^3 + \dots</tex>. Заметим, что результат равен сдвигу <tex>F(s)</tex> на <tex>1</tex> влево. Составим и решим уравнение: <tex>F(s) + s \cdot F(s) = \dfrac{F(s) - 1}{s}</tex>; <tex>F(s)(s^2 + s - 1) = -1</tex>; <tex>F(s) = \dfrac{1}{1 - s - s^2}</tex>.

==См. также==
* [[Производящая функция]]
* [[Производящие функции нескольких переменных]]
* [[Разложение рациональной функции в ряд]]

==Источники информации==
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-02T21:42:44Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-02T21:22:48Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-02T21:06:59Z

KokorinIlya:

Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

2018-03-02T21:06:13Z

KokorinIlya:

Совершенное паросочетание в кубическом графе

2017-12-04T13:12:32Z

KokorinIlya: /* Теорема Петерсона (Petersen) */

==Лемма о сравнимости по модулю 2==
{{Лемма
|id = lemma1
|statement =
Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], <tex>U \in V(G)</tex>, <tex>|U|</tex> нечётно, <tex>m</tex> {{---}} число рёбер, соединяющих вершины множества <tex>U</tex> с вершинами из <tex>V(G) \setminus U</tex>. Тогда <tex>m \equiv k \pmod 2</tex>
|proof =
[[Файл:Сравнимость.png|300px|thumb|left|Иллюстрация к лемме]]
<tex>m = (\sum\limits_{v \in U} d_G(v)) - 2e(G(U))</tex>, где <tex>e(G(U))</tex> {{---}} количество рёбер, соединяющих вершину из <tex>U</tex> с другой вершиной из <tex>U</tex>.

тогда <tex>m = k|U| - 2e(G(U))</tex>.

<tex>2e(G(U))</tex> чётно, поэтому <tex>m \equiv k|U| \pmod 2</tex>. Так как <tex> |U|</tex> нечётно, <tex>m \equiv k \pmod 2</tex>.
}}

==Теорема Петерсона (Petersen)==
{{Определение
|id=cube_graf_def
|definition= '''Кубический граф''' (англ. ''Cubic graph'') {{---}} [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл| граф]], в котором все вершины имеют степень три. Другими словами, кубический граф является <tex>3</tex>-регулярным.}}

{{Теорема
|id=th1
|author=Петерсон
|statement = Пусть <tex>G</tex>{{---}}[[Отношение связности, компоненты связности#connected_graph | связный]] кубический граф, в котором не более <tex>2</tex> [[Мост, эквивалентные определения | мостов]]. Тогда в <tex>G</tex> есть [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].
|proof =
Предположим, что совершенного паросочетания в <tex>G</tex> нет, тогда можно выбрать [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]] <tex>S \subset V(G)</tex>.

Пусть <tex>U_1, \ldots, U_n</tex> {{---}} все нечётные компоненты связности графа <tex>G \setminus S</tex>. <tex>m_i</tex> {{---}} количество ребёр <tex>G</tex>, связывающих вершины <tex>U_i</tex> с вершинами <tex>S</tex>.

По предыдущей лемме, все <tex>m_i</tex> нечётны. Так как не более чем два ребра графа <tex>G</tex> {{---}} мосты, то не более, чем два числа из <tex>m_1, \ldots, m_n</tex> равны <tex>1</tex>, остальные числа не менее <tex>3</tex>.

Так как <tex>S</tex> {{---}} множество Татта, то <tex>odd(G \setminus S) > |S|</tex>. Так как количество вершин кубического графа <tex>G</tex> чётно, мы имеем <tex>S \neq \emptyset, odd(G \setminus S) \equiv S \pmod 2</tex>, следовательно, <tex>n = odd(G \setminus S) \geqslant |S| + 2</tex>. Тогда

<tex>\sum\limits_{v \in S} d_G(v) \geqslant \sum\limits_{i = 1}^n m_i \geqslant 3n - 4 \geqslant 3(|S| + 2) - 4 = 3|S|
+ 2 > 3|S| = \sum\limits_{v \in S} d_G(v)</tex>, что, очевидно, невозможно.

Найдено противоречие, следовательно, множество Татта выбрать невозможно, следовательно, в <tex>G</tex> есть совершенное паросочетание.
}}

[[Файл:Петерсен 3 моста.png|300px|thumb|left|Кубический граф с тремя мостами, в котором не существует совершенного паросочетания.]]
Заметим, что утверждение теоремы не может быть усилено до большего числа мостов, так как для случая с тремя мостами существует контрпример.

==Теорема Фринка (Frink)==
{{Теорема
|id=th2.
|author=Фринк
|statement=

Пусть <tex>G = (V, E)</tex> {{---}} двусвязный кубический граф.
Возьмём ребро <tex>p = (c, d)</tex>. Пусть вершины <tex>a</tex> и <tex>b</tex> смежны с вершиной <tex>c</tex>, а вершины <tex>e</tex> и <tex>f</tex> смежны с вершиной <tex>d</tex> (рисунок <tex>1 (a)</tex>).
Как минимум одно из двух сокращений графа <tex>G</tex>, состоящее из удаления вершин <tex>c, d</tex> и пересоединения вершин <tex>a, b, e, f</tex> рёбрами <tex>(a, e), (b, f)</tex> или <tex>(a, f), (b, e)</tex> (рисунок <tex>1 (b), (c)</tex>, рисунок <tex>2</tex>) сохранит двусвязность графа.

|proof=
Обозначим компоненты графа <tex>G(V - \{c, d\})</tex> как <tex>A, B, E, F</tex>, которые содержат вершины <tex>a, b, e, f</tex> соответственно. Так как <tex>G</tex> не имеет мостов (соответственно <tex>p</tex> не является мостом) должно существовать ребро, соединяющее одну из компонент <tex>A</tex> или <tex>B</tex>, с одной из компонент <tex>E</tex> или <tex>F</tex>. Без потери общности предположим, что <tex>A</tex> соединено с <tex>E</tex>. Заметим, что рёбра <tex>(b, c), (d, f)</tex> так же не являются мостами, значит возможны три случая (с учётом изоморфизма) (рисунок <tex>3</tex>):
* компонента <tex>B</tex> соединена с <tex>F</tex>,
* компонента <tex>B</tex> соединена с <tex>E</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>,
* компонента <tex>A</tex> соединена с <tex>B</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>.
Во всех трёх случаях если <tex>G(V - \{c, d\})</tex> расширить рёбрами <tex>(a, f), (b, e)</tex> (получим граф <tex>G'</tex>), добавленные рёбра будут лежать на некотором [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл| цикле]] в <tex>G'</tex> (рисунок <tex>4</tex>). Так же для любой пары вершин <tex>u, v</tex> <math>\in</math> <tex>\{a, b, e, f\}</tex> существует цикл в <tex>G'</tex>, содержащий данные вершины. Чтобы доказать, что <tex>G'</tex> двусвязен, нужно показать, что каждое ребро <tex>r</tex> из <tex>G'</tex> лежит на некотором цикле в <tex>G'</tex>. Пусть цикл <tex>C</tex> в <tex>G</tex> содержит <tex>r</tex> (такой цикл существует, так как <tex>G</tex> двусвязен). Если <tex>C</tex> не проходит через вершины <tex>c, d</tex> тогда <tex>C</tex> так же является циклом в <tex>G'</tex>, иначе построим цикл <tex>C'</tex> графа <tex>G'</tex> из <tex>C</tex> следующим образом:
* если путь <tex> x - c - d - y </tex> <math>\in</math> <tex> C </tex>, <tex> x </tex> <math>\in</math> <tex> \{a, b\} </tex>, <tex> y </tex> <math>\in</math> <tex> \{e, f\} </tex>, удалим этот путь и добавим любой другой из <tex> x </tex> в <tex> y </tex> в <tex> G' </tex>, не содержащий <tex>r</tex> (такой путь всегда существует, так как <tex> x </tex> и <tex> y </tex> принадлежат некоторому циклу в <tex> G' </tex>),
* если путь <tex> a - c - b </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> a </tex> в <tex> b </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>,
*если путь <tex> e - d - f </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> e </tex> в <tex> f </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>.

<tex>C'</tex> это набор циклов (так как <tex>C'</tex> получен из <tex>C</tex> путём преобразования некоторых путей) и содержит <tex>r</tex>. Из этого следует, что каждое ребро графа <tex>G'</tex> лежит на некотором цикле, то есть граф не содержит мостов. Значит <tex>G'</tex> двусвязен.
}}

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm1.png|thumb|500px|Рисунок 1. Сокращение двусвязного кубического графа. <tex>(a)</tex> Нужно удалить вершины <tex>c, d</tex>. <tex>(b)</tex> первый тип сокращения {{---}} вершина <tex>a</tex> соединена с <tex>e</tex>, вершина <tex>b</tex> соединена с <tex>f</tex>. <tex>(c)</tex> второй тип сокращений {{---}} вершина <tex>a</tex> соединена с <tex>f</tex>, вершина <tex>b</tex> соединена с <tex>e</tex>.]]
|[[Файл:Frinks_algorithm2.PNG|thumb|500px|Рисунок 2. Особые случаи сокращения графа. <tex>(a)</tex> ребро <tex>(c, d)</tex>, которое нужно удалить, кратное. Сокращение удаляет вершины <tex>c, d</tex> из графа и соединяет <tex>a</tex> и <tex>e</tex> новым ребром. <tex>(b)</tex> ребро <tex>(c, d)</tex> инцидентно двум двойным рёбрам <tex>(a, c)</tex> и <tex>(d, e)</tex>. Сокращение удаляет вершины <tex>c, d</tex> и добавляет новое кратное ребро <tex>(a, e)</tex>. <tex>(c)</tex> Ребро <tex>(c, d)</tex> инцидентно одному ребру <tex>(d, e)</tex>. Сокращение удаляет вершины <tex>c, d</tex> и добавляет два новых ребра <tex>(a, e)</tex> и <tex>(b, e)</tex>. <tex>(d)</tex> Ребро <tex>(c, d)</tex> тройной кратности. Сокращение удаляет вершины <tex>c, d</tex>. ]]
|}

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm3.PNG|thumb|500px|Рисунок 3. Все возможные соединения двусвязных компонент графа <tex>G[V - \{c,d\}]</tex>. <tex>(a)</tex> Компонента <tex>A</tex> соединена с компонентой <tex>E</tex>, компонента <tex>B</tex> соединена с компонентой <tex>F</tex>. <tex>(b)</tex> Компонента <tex>E</tex> соединена с компонентами <tex>A, B, F</tex>. <tex>(c)</tex> Компонента <tex>A</tex> соединена с компонентами <tex>B, E</tex>, компонента <tex>E</tex> соединена с компонентой <tex>F</tex>. ]]
|[[Файл:Frinks_algorithm4.PNG|thumb|500px|Рисунок 4. Возможные соединения двусвязный компонент <tex>A, B, E, F</tex> после удаления ребра <tex>(c, d)</tex> и добавления рёбер <tex>(a, f)</tex> и <tex>(b, e)</tex>.]]
|}

==Алгоритм поиска совершенного паросочетания (Frink's algorithm)==
Будем сокращать данный граф <tex>G</tex> вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины.
Когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений, то есть будем восстанавливать граф (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешимо за <tex>O(1)</tex>. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm5.PNG|thumb|400px|Рисунок 5. Базовые случаи восстановления графа.]]
|[[Файл:Frinks_algorithm6.PNG|thumb|400px|Рисунок 6. Особые случаи восстановления графа.]]
|}

==Псевдокод алгоритма Фринка==
*<tex>G</tex> {{---}} двусвязный кубический граф,
*<tex>M</tex> {{---}} совершенное паросочетание <tex>G</tex>,
*функция <tex>\mathtt{bridgeless}</tex> возвращает <tex>true</tex> если у графа нет моста или <tex>false</tex> в противном случае,
*функция <tex>\mathtt{alternatingCycle}</tex> принимает три параметра: граф, совершенное паросочетание и ребро. Возвращает альтернативный цикл, включающий в себя данное ребро и обновляет совершенное паросочетание,
*функция <tex>\mathtt{reductions}</tex> сокращает граф,
*функция <tex>\mathtt{simpleReversion}</tex> восстанавливает граф,
*функция <tex>\mathtt{reductedGraph}</tex> принимает три параметра: граф, удаляемые вершины, добавляемые рёбра. Возвращает новый граф, у которого удалены выбранные вершины, вместе c инцидентными рёбрами и добавлены другие рёбра, переданные в параметрах. При этом исходный граф не меняется.

'''function''' frinkMatching<tex>(G)</tex>:
'''if''' <tex>|V| = 0</tex>
'''return''' <tex>\varnothing</tex>
<tex>v - w = E[0]</tex>
<tex>R = </tex> reductions<tex>(G, v - w)</tex>
'''if''' bridgeless<tex>(</tex>reductedGraph<tex>(G, \{v, w\}, R[0]))</tex>
<tex>r = R[0]</tex>
'''else'''
<tex>r = R[1]</tex>
<tex>M =</tex> frinkMatching<tex>(</tex>reductedGraph<tex>(G,\{v, w\}, r))</tex>
'''if''' <tex>|r \cap M| = 2 </tex>
<tex>C =</tex> alternatingCycle<tex>(G, M, r[0])</tex>
<tex>M = M \oplus C</tex>
<tex>M = (M - r)\ \cup </tex> simpleReversion<tex>(G, v, w, r, M)</tex>
'''return''' <tex>M</tex>

==Время работы алгоритма Фринка==
Операция сокращения должна на каждом шаге проверять граф на наличие мостов за <tex>O(n)</tex>, кроме того, при возникновении четвёртого базового случая требуется найти альтернативный цикл за <tex>O(n)</tex>. В алгоритме <tex>O(n)</tex> операций сокращения и восстановления графа, причем каждая из этих операций требует <tex>O(n)</tex> времени. Таким образом, весь этот алгоритм исполняется за время <tex>O(n^2)</tex>.

==См. также==

* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]

== Источники информации ==
* [https://www.lektorium.tv/course/22771 Лекториум {{---}} Дополнительные главы теории паросочетаний]
* [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Wikipedia {{---}} Кубический граф]
* Piotr Stanczyk {{---}} THEORY AND PRACTICE OF COMPUTING MAXIMUM MATCHINGS IN GRAPHS стр. 21-28.
* Карпов В. Д. - Теория графов, стр 42

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

Совершенное паросочетание в кубическом графе

2017-12-02T23:33:31Z

KokorinIlya: /* Теорема Петерсона (Petersen) */

==Лемма о сравнимости по модулю 2==
{{Лемма
|id = lemma1
|statement =
Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], <tex>U \in V(G)</tex>, <tex>|U|</tex> нечётно, <tex>m</tex> {{---}} число рёбер, соединяющих вершины множества <tex>U</tex> с вершинами из <tex>V(G) \setminus U</tex>. Тогда <tex>m \equiv k \pmod 2</tex>
|proof =
[[Файл:Сравнимость.png|300px|thumb|left|Иллюстрация к лемме]]
<tex>m = (\sum\limits_{v \in U} d_G(v)) - 2e(G(U))</tex>, где <tex>e(G(U))</tex> {{---}} количество рёбер, соединяющих вершину из <tex>U</tex> с другой вершиной из <tex>U</tex>.

тогда <tex>m = k|U| - 2e(G(U))</tex>.

<tex>2e(G(U))</tex> чётно, поэтому <tex>m \equiv k|U| \pmod 2</tex>. Так как <tex> |U|</tex> нечётно, <tex>m \equiv k \pmod 2</tex>.
}}

==Теорема Петерсона (Petersen)==
{{Определение
|id=cube_graf_def
|definition= '''Кубический граф''' (англ. ''Cubic graph'') {{---}} [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл| граф]], в котором все вершины имеют степень три. Другими словами, кубический граф является <tex>3</tex>-регулярным.}}

{{Теорема
|id=th1
|author=Петерсон
|statement = Пусть <tex>G</tex>{{---}}[[Отношение связности, компоненты связности#connected_graph | связный]] кубический граф, в котором не более <tex>2</tex> [[Мост, эквивалентные определения | мостов]]. Тогда в <tex>G</tex> есть [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].
|proof =
Предположим, что совершенного паросочетания в <tex>G</tex> нет, тогда можно выбрать [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]] <tex>S \subset V(G)</tex>.

Пусть <tex>U_1, \ldots, U_n</tex> {{---}} все нечётные компоненты связности графа <tex>G \setminus S</tex>. <tex>m_i</tex> {{---}} количество ребёр <tex>G</tex>, связывающих вершины <tex>U_i</tex> с вершинами <tex>S</tex>.

По предыдущей лемме, все <tex>m_i</tex> нечётны. Так как не более чем два ребра графа <tex>G</tex> {{---}} мосты, то не более, чем два числа из <tex>m_1, \ldots, m_n</tex> равны <tex>1</tex>, остальные числа не менее <tex>3</tex>.

Так как <tex>S</tex> {{---}} множество Татта, то <tex>odd(G \setminus S) > |S|</tex>. Так как количество вершин кубического графа <tex>G</tex> чётно, мы имеем <tex>S \neq \emptyset, odd(G \setminus S) \equiv S \pmod 2</tex>, следовательно, <tex>n = odd(G \setminus S) \geqslant |S| + 2</tex>. Тогда

<tex>\sum\limits_{v \in S} d_G(v) \geqslant \sum\limits_{i = 1}^n m_i \geqslant 3n - 4 \geqslant 3(|S| + 2) - 4 = 3|S|
+ 2 > 3|S| = \sum\limits_{v \in S} d_G(v)</tex>, что, очевидно, невозможно.

Найдено противоречие, следовательно, множество Татта выбрать невозможно, следовательно, в <tex>G</tex> есть совершенное паросочетание.
}}

[[Файл:Петерсен 3 моста.png|300px|thumb|right|Кубический граф с тремя мостами, в котором не существует совершенного паросочетания.]]
Заметим, что утверждение теоремы не может быть усилено до большего числа мостов, так как для случая с тремя мостами существует контрпример.

==Теорема Фринка (Frink)==
{{Теорема
|id=th2.
|author=Фринк
|statement=

Пусть <tex>G = (V, E)</tex> {{---}} двусвязный кубический граф.
Возьмём ребро <tex>p = (c, d)</tex>. Пусть вершины <tex>a</tex> и <tex>b</tex> смежны с вершиной <tex>c</tex>, а вершины <tex>e</tex> и <tex>f</tex> смежны с вершиной <tex>d</tex> (рисунок <tex>1 (a)</tex>).
Как минимум одно из двух сокращений графа <tex>G</tex>, состоящее из удаления вершин <tex>c, d</tex> и пересоединения вершин <tex>a, b, e, f</tex> рёбрами <tex>(a, e), (b, f)</tex> или <tex>(a, f), (b, e)</tex> (рисунок <tex>1 (b), (c)</tex>, рисунок <tex>2</tex>) сохранит двусвязность графа.

|proof=
Обозначим компоненты графа <tex>G(V - \{c, d\})</tex> как <tex>A, B, E, F</tex>, которые содержат вершины <tex>a, b, e, f</tex> соответственно. Так как <tex>G</tex> не имеет мостов (соответственно <tex>p</tex> не является мостом) должно существовать ребро, соединяющее одну из компонент <tex>A</tex> или <tex>B</tex>, с одной из компонент <tex>E</tex> или <tex>F</tex>. Без потери общности предположим, что <tex>A</tex> соединено с <tex>E</tex>. Заметим, что рёбра <tex>(b, c), (d, f)</tex> так же не являются мостами, значит возможны три случая (с учётом изоморфизма) (рисунок <tex>3</tex>):
* компонента <tex>B</tex> соединена с <tex>F</tex>,
* компонента <tex>B</tex> соединена с <tex>E</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>,
* компонента <tex>A</tex> соединена с <tex>B</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>.
Во всех трёх случаях если <tex>G(V - \{c, d\})</tex> расширить рёбрами <tex>(a, f), (b, e)</tex> (получим граф <tex>G'</tex>), добавленные рёбра будут лежать на некотором [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл| цикле]] в <tex>G'</tex> (рисунок <tex>4</tex>). Так же для любой пары вершин <tex>u, v</tex> <math>\in</math> <tex>\{a, b, e, f\}</tex> существует цикл в <tex>G'</tex>, содержащий данные вершины. Чтобы доказать, что <tex>G'</tex> двусвязен, нужно показать, что каждое ребро <tex>r</tex> из <tex>G'</tex> лежит на некотором цикле в <tex>G'</tex>. Пусть цикл <tex>C</tex> в <tex>G</tex> содержит <tex>r</tex> (такой цикл существует, так как <tex>G</tex> двусвязен). Если <tex>C</tex> не проходит через вершины <tex>c, d</tex> тогда <tex>C</tex> так же является циклом в <tex>G'</tex>, иначе построим цикл <tex>C'</tex> графа <tex>G'</tex> из <tex>C</tex> следующим образом:
* если путь <tex> x - c - d - y </tex> <math>\in</math> <tex> C </tex>, <tex> x </tex> <math>\in</math> <tex> \{a, b\} </tex>, <tex> y </tex> <math>\in</math> <tex> \{e, f\} </tex>, удалим этот путь и добавим любой другой из <tex> x </tex> в <tex> y </tex> в <tex> G' </tex>, не содержащий <tex>r</tex> (такой путь всегда существует, так как <tex> x </tex> и <tex> y </tex> принадлежат некоторому циклу в <tex> G' </tex>),
* если путь <tex> a - c - b </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> a </tex> в <tex> b </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>,
*если путь <tex> e - d - f </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> e </tex> в <tex> f </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>.

<tex>C'</tex> это набор циклов (так как <tex>C'</tex> получен из <tex>C</tex> путём преобразования некоторых путей) и содержит <tex>r</tex>. Из этого следует, что каждое ребро графа <tex>G'</tex> лежит на некотором цикле, то есть граф не содержит мостов. Значит <tex>G'</tex> двусвязен.
}}

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm1.png|thumb|500px|Рисунок 1. Сокращение двусвязного кубического графа. <tex>(a)</tex> Нужно удалить вершины <tex>c, d</tex>. <tex>(b)</tex> первый тип сокращения {{---}} вершина <tex>a</tex> соединена с <tex>e</tex>, вершина <tex>b</tex> соединена с <tex>f</tex>. <tex>(c)</tex> второй тип сокращений {{---}} вершина <tex>a</tex> соединена с <tex>f</tex>, вершина <tex>b</tex> соединена с <tex>e</tex>.]]
|[[Файл:Frinks_algorithm2.PNG|thumb|500px|Рисунок 2. Особые случаи сокращения графа. <tex>(a)</tex> ребро <tex>(c, d)</tex>, которое нужно удалить, кратное. Сокращение удаляет вершины <tex>c, d</tex> из графа и соединяет <tex>a</tex> и <tex>e</tex> новым ребром. <tex>(b)</tex> ребро <tex>(c, d)</tex> инцидентно двум двойным рёбрам <tex>(a, c)</tex> и <tex>(d, e)</tex>. Сокращение удаляет вершины <tex>c, d</tex> и добавляет новое кратное ребро <tex>(a, e)</tex>. <tex>(c)</tex> Ребро <tex>(c, d)</tex> инцидентно одному ребру <tex>(d, e)</tex>. Сокращение удаляет вершины <tex>c, d</tex> и добавляет два новых ребра <tex>(a, e)</tex> и <tex>(b, e)</tex>. <tex>(d)</tex> Ребро <tex>(c, d)</tex> тройной кратности. Сокращение удаляет вершины <tex>c, d</tex>. ]]
|}

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm3.PNG|thumb|500px|Рисунок 3. Все возможные соединения двусвязных компонент графа <tex>G[V - \{c,d\}]</tex>. <tex>(a)</tex> Компонента <tex>A</tex> соединена с компонентой <tex>E</tex>, компонента <tex>B</tex> соединена с компонентой <tex>F</tex>. <tex>(b)</tex> Компонента <tex>E</tex> соединена с компонентами <tex>A, B, F</tex>. <tex>(c)</tex> Компонента <tex>A</tex> соединена с компонентами <tex>B, E</tex>, компонента <tex>E</tex> соединена с компонентой <tex>F</tex>. ]]
|[[Файл:Frinks_algorithm4.PNG|thumb|500px|Рисунок 4. Возможные соединения двусвязный компонент <tex>A, B, E, F</tex> после удаления ребра <tex>(c, d)</tex> и добавления рёбер <tex>(a, f)</tex> и <tex>(b, e)</tex>.]]
|}

==Алгоритм поиска совершенного паросочетания (Frink's algorithm)==
Будем сокращать данный граф <tex>G</tex> вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины.
Когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений, то есть будем восстанавливать граф (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешимо за <tex>O(1)</tex>. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm5.PNG|thumb|400px|Рисунок 5. Базовые случаи восстановления графа.]]
|[[Файл:Frinks_algorithm6.PNG|thumb|400px|Рисунок 6. Особые случаи восстановления графа.]]
|}

==Псевдокод алгоритма Фринка==
*<tex>G</tex> {{---}} двусвязный кубический граф,
*<tex>M</tex> {{---}} совершенное паросочетание <tex>G</tex>,
*функция <tex>\mathtt{bridgeless}</tex> возвращает <tex>true</tex> если у графа нет моста или <tex>false</tex> в противном случае,
*функция <tex>\mathtt{alternatingCycle}</tex> принимает три параметра: граф, совершенное паросочетание и ребро. Возвращает альтернативный цикл, включающий в себя данное ребро и обновляет совершенное паросочетание,
*функция <tex>\mathtt{reductions}</tex> сокращает граф,
*функция <tex>\mathtt{simpleReversion}</tex> восстанавливает граф,
*функция <tex>\mathtt{reductedGraph}</tex> принимает три параметра: граф, удаляемые вершины, добавляемые рёбра. Возвращает новый граф, у которого удалены выбранные вершины, вместе c инцидентными рёбрами и добавлены другие рёбра, переданные в параметрах. При этом исходный граф не меняется.

'''function''' frinkMatching<tex>(G)</tex>:
'''if''' <tex>|V| = 0</tex>
'''return''' <tex>\varnothing</tex>
<tex>v - w = E[0]</tex>
<tex>R = </tex> reductions<tex>(G, v - w)</tex>
'''if''' bridgeless<tex>(</tex>reductedGraph<tex>(G, \{v, w\}, R[0]))</tex>
<tex>r = R[0]</tex>
'''else'''
<tex>r = R[1]</tex>
<tex>M =</tex> frinkMatching<tex>(</tex>reductedGraph<tex>(G,\{v, w\}, r))</tex>
'''if''' <tex>|r \cap M| = 2 </tex>
<tex>C =</tex> alternatingCycle<tex>(G, M, r[0])</tex>
<tex>M = M \oplus C</tex>
<tex>M = (M - r)\ \cup </tex> simpleReversion<tex>(G, v, w, r, M)</tex>
'''return''' <tex>M</tex>

==Время работы алгоритма Фринка==
Операция сокращения должна на каждом шаге проверять граф на наличие мостов за <tex>O(n)</tex>, кроме того, при возникновении четвёртого базового случая требуется найти альтернативный цикл за <tex>O(n)</tex>. В алгоритме <tex>O(n)</tex> операций сокращения и восстановления графа, причем каждая из этих операций требует <tex>O(n)</tex> времени. Таким образом, весь этот алгоритм исполняется за время <tex>O(n^2)</tex>.

==См. также==

* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]

== Источники информации ==
* [https://www.lektorium.tv/course/22771 Лекториум {{---}} Дополнительные главы теории паросочетаний]
* [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Wikipedia {{---}} Кубический граф]
* Piotr Stanczyk {{---}} THEORY AND PRACTICE OF COMPUTING MAXIMUM MATCHINGS IN GRAPHS стр. 21-28.
* Карпов В. Д. - Теория графов, стр 42

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

Файл:Петерсен 3 моста.png

2017-12-02T23:30:40Z

KokorinIlya:

Факторизация графов

2017-11-29T21:27:06Z

KokorinIlya: /* 2-факторизация */

{{Определение
|definition ='''Фактором ''' ''(англ. factor)'' [[Основные определения теории графов|графа]] <tex>G</tex> называется [[Остовные деревья: определения, лемма о безопасном ребре|остовный подграф]] графа <tex>G</tex>, имеющий хотя бы одно ребро.
}}

{{Определение
|definition = Граф <tex>G</tex> — сумма факторов <tex>G_i</tex>, если графы <tex>G_i</tex> не имеют попарно общих рёбер, а <tex>G</tex> является их объединением. Такое разложение называется '''факторизацией ''' ''(англ. factorization)'' графа <tex>G</tex>.
}}

{{Определение
|definition = '''<tex>n</tex>-фактор''' — [[Основные определения теории графов|регулярный]] остовный подграф степени <tex>n</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>n</tex>-факторов, то их объединение называется <tex>n</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>n</tex>-факторизуемым.
}}

== 1-факторизация ==
{{Теорема
|statement=
[[Основные определения теории графов|Полный]] граф <tex>K_{2n}</tex> <tex>1</tex>-факторизуем.
|proof=
[[Файл: Факторизация K6.png|thumb|360px|right|<tex>1</tex>-факторизация графа <tex>K_6</tex>]]
Нам нужно только указать разбиение множества рёбер <tex>E</tex> графа на <tex>(2n - 1)</tex> <tex>1</tex>-фактора. Для этого обозначим вершины графа <tex>G</tex> через <tex>v_1, v_2, \dots, v_{2n}</tex> и определим множества рёбер <tex>X_i = (v_iv_{2n}) \cup (v_{i - j}v_{i + j}; j = 1, 2, \dots, n - 1)</tex>, <tex>i = 1, 2, \dots, 2n - 1 </tex>, где каждый из индексов <tex>i - j</tex> и <tex>i + j</tex> является одним из чисел <tex>1, 2, \dots, 2n - 1</tex>; здесь сумма и разность берутся по модулю <tex>2n - 1</tex>. Легко видеть, что набор <tex>X_i</tex> даёт необходимое разбиение множества <tex>X</tex>, а сумма подграфов <tex>G_i</tex>, порождённых множествами <tex>X_i</tex>, является <tex>1</tex>-факторизацией графа <tex>K_{2n}</tex>.
}}
== 2-факторизация ==

{{Утверждение
|statement =
Если граф <tex>2</tex>-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) [[Основные определения теории графов|циклов]].
|proof =
Начнём обход <tex>2</tex>-фактора с какой-то вершины. Пойдём по одному из её рёбер и попадаем в смежную ей вершину. Далее идём по рёбрам, по которым мы ещё не ходили. Мы входим в вершину по одному ребру и выходим по другому, так как степень каждой вершины равна <tex>2</tex>, пока не вернёмся в первую вершину. Это цикл, так как в каждой вершине мы были только один раз. Если есть вершины, которые мы не посетили, то снова начинаем обход с любой из таких вершин. В вершины прежних циклов попасть нельзя, так как мы уже проходили по рёбрам этих вершин. Значит, циклы не пересекаются по вершинам.
}}

{{Теорема
|id=regular2factor
|author=J. Petersen, 1981
|about = О наличии <tex>2</tex>-фактора в регулярном графе чётной степени.
|statement = Пусть <tex>G</tex> {{---}} [[Основные определения теории графов#defRegularGraph |регулярный граф]] чётной степени. Тогда в <tex>G</tex> есть <tex>2</tex>-фактор.
|proof =
Пусть <tex>G</tex> {{---}} <tex>2k</tex>-регулярный граф, пусть <tex>G</tex> [[Отношение связности, компоненты связности#connected_graph | связен]].

Согласно [[Эйлеровость графов#eulerTheorem | критерию эйлеровости]] граф <tex>G</tex> имеет эйлеров цикл <tex>v_0e_1 \cdots e_lv_l</tex>, где <tex>v_0 = v_l</tex>.

Будем строить граф <tex>H</tex> следующим образом: разделим каждую вершину графа <tex>G</tex> <tex>v</tex> на две, назовём их <tex>v^-</tex> и <tex>v^+</tex>. Заменим каждое ребро в эйлеровом обходе <tex>v_iv_{i+1}</tex> на ребро <tex>v_i^-v_{i+1}^+</tex>

[[Файл:2-фактор(1).png|300px|thumb|right|Пример регулярного графа чётной степени. В нём есть эйлеров цикл <tex>1</tex>{{---}}<tex>2</tex>{{---}}<tex>3</tex>{{---}}<tex>4</tex>{{---}}<tex>1</tex>]]

[[Файл:2-фактор(2).png|300px|thumb|right|Соответствующий ему граф <tex>H</tex>]]

Получившийся граф является <tex>k</tex>-регулярным, и по [[Рёберная раскраска двудольного графа#lem2 | лемме о существовании совершенного паросочетания в регулярном двудольном графе]] в нём есть совершенное паросочетание, то есть <tex>1</tex>-фактор.

Объединим вершины <tex>v^-</tex> и <tex>v^+</tex> обратно в вершину <tex>v</tex>. Так как в графе <tex>H</tex> каждой вершине было инцидентно <tex>1</tex> ребро, то после объединения в графе <tex>G</tex> каждой вершине будет инцидентно <tex>2</tex> ребра.

Если <tex>G</tex> несвязен, то аналогичные рассуждения можно провести для каждой его [[Отношение связности, компоненты связности#def2 | компоненты связности]], и, таким образом, найти <tex>2</tex>-фактор в каждой его компоненте связности. Тогда каждой вершине каждой его компоненты связности будет инцидентно <tex>2</tex> ребра, значит, каждой вершине <tex>G</tex> будет инцидентно <tex>2</tex> ребра, значит, в <tex>G</tex> существует <tex>2</tex>-фактор.
}}

[[Файл:Факторизация K7 разбиение.png|300px|thumb|right| Пример графа, имеющего <tex>3</tex> различных <tex>2</tex>-фактора, то есть разбиваемого на <tex>3</tex> рёберно непересекающихся [[Гамильтоновы графы#defCycle|гамильтоновых цикла]]]]

Заметим, что если <tex>2</tex>-фактор связен, то он является [[Гамильтоновы графы|гамильтоновым циклом]].

{{Теорема
|statement =
Граф <tex>K_{2n+1}</tex> можно представить в виде суммы <tex>n</tex> гамильтоновых циклов.
|proof =
[[Файл: Факторизация K7.png|thumb|360px|right|<tex>2</tex>-факторизация графа <tex>K_7</tex>. Рёбра, отмеченные пунктиром, не пересекают другие рёбра при правильной [[Укладка графа на плоскости|укладке графа]].]]Для того чтобы в графе <tex>K_{2n+1}</tex> построить <tex>n</tex> гамильтоновых циклов, непересекающихся по рёбрам, перенумеруем сначала его вершины <tex>v_1, v_2, \dots, v_{2n+1}</tex>. На множестве вершин <tex>v_1, v_2, \dots, v_{2n}</tex> зададим <tex>n</tex> непересекающихся простых цепей <tex>P_i=v_i v_{i-1} v_{i+1} v_{i-2} \dots v_{i+n-1}v_{i-n}</tex> следующим образом: <tex>j</tex>-ой вершине цепи <tex>P_i</tex> является вершина <tex>v_k</tex>, где <tex>k=i+(-1)^{j+1}\dfrac{j}{2}</tex>, все индексы приводятся к числам <tex>1, 2, \dots, 2n </tex> по модулю <tex>2n</tex>. Гамильтонов цикл <tex>Z_i</tex> можно получить, соединив вершину <tex>v_{2n+1}</tex> с концевыми вершинами цепи <tex>P_i</tex>.
}}

== Замечания ==
* Факторизация графов используется как один из способов построения покрывающих наборов, используемых при создании тестов для программ с большим количеством параметров.
* <tex>1</tex>-факторизация <tex>k</tex>-регулярного графа является рёберной [[Раскраска графа|<tex>k</tex>-раскраской графа]].
== См. также ==
* [[Гамильтоновы графы]]
* [[Остовные деревья: определения, лемма о безопасном ребре|Остовные деревья]]
* [[Основные определения теории графов]]

== Источники информации ==
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* [http://en.wikipedia.org/wiki/Graph_factorization Wikipedia — Graph factorization]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

Факторизация графов

2017-11-29T21:24:49Z

KokorinIlya: /* 2-факторизация */

{{Определение
|definition ='''Фактором ''' ''(англ. factor)'' [[Основные определения теории графов|графа]] <tex>G</tex> называется [[Остовные деревья: определения, лемма о безопасном ребре|остовный подграф]] графа <tex>G</tex>, имеющий хотя бы одно ребро.
}}

{{Определение
|definition = Граф <tex>G</tex> — сумма факторов <tex>G_i</tex>, если графы <tex>G_i</tex> не имеют попарно общих рёбер, а <tex>G</tex> является их объединением. Такое разложение называется '''факторизацией ''' ''(англ. factorization)'' графа <tex>G</tex>.
}}

{{Определение
|definition = '''<tex>n</tex>-фактор''' — [[Основные определения теории графов|регулярный]] остовный подграф степени <tex>n</tex>. Если граф <tex>G</tex> представляет собой сумму <tex>n</tex>-факторов, то их объединение называется <tex>n</tex>-факторизацией, а сам граф <tex>G</tex> назыается <tex>n</tex>-факторизуемым.
}}

== 1-факторизация ==
{{Теорема
|statement=
[[Основные определения теории графов|Полный]] граф <tex>K_{2n}</tex> <tex>1</tex>-факторизуем.
|proof=
[[Файл: Факторизация K6.png|thumb|360px|right|<tex>1</tex>-факторизация графа <tex>K_6</tex>]]
Нам нужно только указать разбиение множества рёбер <tex>E</tex> графа на <tex>(2n - 1)</tex> <tex>1</tex>-фактора. Для этого обозначим вершины графа <tex>G</tex> через <tex>v_1, v_2, \dots, v_{2n}</tex> и определим множества рёбер <tex>X_i = (v_iv_{2n}) \cup (v_{i - j}v_{i + j}; j = 1, 2, \dots, n - 1)</tex>, <tex>i = 1, 2, \dots, 2n - 1 </tex>, где каждый из индексов <tex>i - j</tex> и <tex>i + j</tex> является одним из чисел <tex>1, 2, \dots, 2n - 1</tex>; здесь сумма и разность берутся по модулю <tex>2n - 1</tex>. Легко видеть, что набор <tex>X_i</tex> даёт необходимое разбиение множества <tex>X</tex>, а сумма подграфов <tex>G_i</tex>, порождённых множествами <tex>X_i</tex>, является <tex>1</tex>-факторизацией графа <tex>K_{2n}</tex>.
}}
== 2-факторизация ==

{{Утверждение
|statement =
Если граф <tex>2</tex>-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) [[Основные определения теории графов|циклов]].
|proof =
Начнём обход <tex>2</tex>-фактора с какой-то вершины. Пойдём по одному из её рёбер и попадаем в смежную ей вершину. Далее идём по рёбрам, по которым мы ещё не ходили. Мы входим в вершину по одному ребру и выходим по другому, так как степень каждой вершины равна <tex>2</tex>, пока не вернёмся в первую вершину. Это цикл, так как в каждой вершине мы были только один раз. Если есть вершины, которые мы не посетили, то снова начинаем обход с любой из таких вершин. В вершины прежних циклов попасть нельзя, так как мы уже проходили по рёбрам этих вершин. Значит, циклы не пересекаются по вершинам.
}}

{{Теорема
|id=regular2factor
|author=J. Petersen, 1981
|about = О наличии <tex>2</tex>-фактора в регулярном графе чётной степени.
|statement = Пусть <tex>G</tex> {{---}} [[Основные определения теории графов#defRegularGraph |регулярный граф]] чётной степени. Тогда в <tex>G</tex> есть <tex>2</tex>-фактор.
|proof =
Пусть <tex>G</tex> {{---}} <tex>2k</tex>-регулярный граф, пусть <tex>G</tex> [[Отношение связности, компоненты связности#connected_graph | связен]].

Согласно [[Эйлеровость графов#eulerTheorem | критерию эйлеровости]] граф <tex>G</tex> имеет эйлеров цикл <tex>v_0e_1 \cdots e_lv_l</tex>, где <tex>v_0 = v_l</tex>.

Будем строить граф <tex>H</tex> следующим образом: разделим каждую вершину графа <tex>G</tex> <tex>v</tex> на две, назовём их <tex>v^-</tex> и <tex>v^+</tex>. Заменим каждое ребро в эйлеровом обходе <tex>v_iv_{i+1}</tex> на ребро <tex>v_i^-v_{i+1}^+</tex>

[[Файл:2-фактор(1).png|300px|thumb|right|Пример регулярного графа чётной степени. В нём есть эйлеров цикл <tex>1</tex>{{---}}<tex>2</tex>{{---}}<tex>3</tex>{{---}}<tex>4</tex>{{---}}<tex>1</tex>]]

[[Файл:2-фактор(2).png|300px|thumb|right|Соответствующий ему граф <tex>H</tex>]]

Получившийся граф является <tex>k</tex>-регулярным, и по [[Рёберная раскраска двудольного графа#lem2 | лемме о существовании совершенного паросочетания в регулярном двудольном графе]] в нём есть совершенное паросочетание, то есть <tex>1</tex>-фактор.

Объединим вершины <tex>v^-</tex> и <tex>v^+</tex> обратно в вершину <tex>v</tex>. Так как в графе <tex>H</tex> каждой вершине было инцидентно <tex>1</tex> ребро, то после объединения в графе <tex>G</tex> каждой вершине будет инцидентно <tex>2</tex> ребра.

Если <tex>G</tex> несвязен, то аналогичные рассуждения можно провести для каждой его [[Отношение связности, компоненты связности#def2 | компоненты связности]], и, таким образом, найти <tex>2</tex>-фактор в каждой его компоненте связности. Тогда каждой вершине каждой его компоненты связности будет инцидентно <tex>2</tex> ребра, значит, каждой вершине <tex>G</tex> будет инцидентно <tex>2</tex> ребра, значит, в <tex>G</tex> существует <tex>2</tex>-фактор.
}}

[[Файл:Факторизация K7 разбиение.png|300px|thumb|left| Пример графа, имеющего <tex>3</tex> различных <tex>2</tex>-фактора, то есть разбиваемого на <tex>3</tex> рёберно непересекающихся [[Гамильтоновы графы#defCycle|гамильтоновых цикла]]]]

Заметим, что если <tex>2</tex>-фактор связен, то он является [[Гамильтоновы графы|гамильтоновым циклом]].

{{Теорема
|statement =
Граф <tex>K_{2n+1}</tex> можно представить в виде суммы <tex>n</tex> гамильтоновых циклов.
|proof =
[[Файл: Факторизация K7.png|thumb|360px|right|<tex>2</tex>-факторизация графа <tex>K_7</tex>. Рёбра, отмеченные пунктиром, не пересекают другие рёбра при правильной [[Укладка графа на плоскости|укладке графа]].]]Для того чтобы в графе <tex>K_{2n+1}</tex> построить <tex>n</tex> гамильтоновых циклов, непересекающихся по рёбрам, перенумеруем сначала его вершины <tex>v_1, v_2, \dots, v_{2n+1}</tex>. На множестве вершин <tex>v_1, v_2, \dots, v_{2n}</tex> зададим <tex>n</tex> непересекающихся простых цепей <tex>P_i=v_i v_{i-1} v_{i+1} v_{i-2} \dots v_{i+n-1}v_{i-n}</tex> следующим образом: <tex>j</tex>-ой вершине цепи <tex>P_i</tex> является вершина <tex>v_k</tex>, где <tex>k=i+(-1)^{j+1}\dfrac{j}{2}</tex>, все индексы приводятся к числам <tex>1, 2, \dots, 2n </tex> по модулю <tex>2n</tex>. Гамильтонов цикл <tex>Z_i</tex> можно получить, соединив вершину <tex>v_{2n+1}</tex> с концевыми вершинами цепи <tex>P_i</tex>.
}}

== Замечания ==
* Факторизация графов используется как один из способов построения покрывающих наборов, используемых при создании тестов для программ с большим количеством параметров.
* <tex>1</tex>-факторизация <tex>k</tex>-регулярного графа является рёберной [[Раскраска графа|<tex>k</tex>-раскраской графа]].
== См. также ==
* [[Гамильтоновы графы]]
* [[Остовные деревья: определения, лемма о безопасном ребре|Остовные деревья]]
* [[Основные определения теории графов]]

== Источники информации ==
* Харари Фрэнк '''Теория графов''' Пер. с англ. и предисл. В. П. Козырева. Под ред. Г.П.Гаврилова. Изд. 2-е. — М.: Едиториал УРСС, 2003. — 296 с. — ISBN 5-354-00301-6
* [http://en.wikipedia.org/wiki/Graph_factorization Wikipedia — Graph factorization]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]

Теорема о существовании совершенного паросочетания в графе, полученном из регулярного удалением ребёр

2017-11-29T20:11:51Z

KokorinIlya:

{{Теорема
|id = th_main.
|author = J. Plesnik, 1972
|statement = Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], с чётным числом вершин, причём <tex>\lambda(G) \geqslant k - 1</tex>, а граф <tex>G'</tex> получен из <tex>G</tex> удалением не более <tex>k - 1</tex> рёбер. Тогда в графе <tex>G'</tex> есть совершенное паросочетание.
|proof =
Пусть <tex>G' = G \setminus F</tex>, где <tex>F \subset E(G)</tex>, тогда <tex>|F| \leqslant k - 1</tex>

Предположим, что в <tex>G'</tex> нет [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенного паросочетания]]., тогда выберем [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]] <tex>S \subset V(G')</tex>, тогда <tex>odd(G' \subset S) > |S|</tex>

Так как <tex>|V(G)|</tex> чётно, то и <tex>odd(G' \setminus S) + |S|</tex> тоже чётно. Из этого следует, что <tex>odd(G' \setminus S) \equiv |S| \pmod 2 </tex>. Из этого факта и того, что <tex>odd(G' \setminus S) > |S|</tex> следует, что <tex>odd(G' \setminus S) \geqslant |S| + 2 ~~~ \textbf{(1)}</tex>

Пусть в графе <tex>G' \setminus S</tex> всего <tex>t</tex> компонент связности, <tex>n</tex> из которых нечётны. Тогда пусть <tex>U_1, \cdots, U_n</tex> {{---}} нечётные компоненты связности <tex>G' \setminus S</tex>, тогда <tex>|odd(G' \setminus S)| = n</tex>, а <tex>U_{n+1}, \cdots, U_t</tex> {{---}} его чётные компоненты связности. Для каждого <tex>i \in [1 \cdots t]</tex> определим три множества:

[[Файл:Плешник 1.png|300px|thumb|right|Чёрные ребра {{---}} рёбра из <tex>A_i</tex>, красные рёбра {{---}} рёбра из <tex>B_i</tex>, синие рёбра {{---}} рёбра из <tex>C_i</tex>. Обратите внимание, что только чёрные рёбра есть в графе <tex>G'</tex>, синие и красные {{---}} рёбра из <tex>F</tex>]]

<tex>A_i</tex> {{---}} рёбра из <tex>E(G')</tex>, соединяющие <tex>U_i</tex> с <tex>S</tex>, <tex>\alpha_i</tex> {{---}} их количество, то есть <tex>\alpha_i = |A_i|</tex>

<tex>B_i</tex> {{---}} рёбра из <tex>F</tex>, соединяющие <tex>U_i</tex> с <tex>S</tex>, <tex>\beta_i</tex> {{---}} их количество, то есть <tex>\beta_i = |B_i|</tex>

<tex>C_i</tex> {{---}} рёбра из <tex>F</tex>, соединяющие <tex>U_i</tex> с остальными компонентами связности графа <tex>G' \setminus S</tex>, <tex>\gamma_i</tex> {{---}} их количество, то есть <tex>\gamma_i = |C_i|</tex>.

Тогда определим <tex>m_i = \alpha_i + \beta_i + \gamma_i</tex>. Тогда <tex>m_i</tex> {{---}} это количество рёбер графа <tex>G</tex>, соединяющих <tex>U_i</tex> с <tex>V(G) \setminus U_i</tex>.

По лемме [[Совершенное паросочетание в кубическом графе#lemma1 | о сравнимости по модулю 2]] для нечётных компонент связности <tex>G' \setminus S</tex> (то есть <tex>i \in [1 \cdots n]</tex>) <tex>m_i \equiv k \pmod 2</tex>.

<tex>m_i \geqslant \lambda(G)</tex> (так как граф потерял связность), а <tex>\lambda(G) \geqslant k - 1</tex>. Из этого факта и того, что <tex>m_i \equiv k \pmod 2</tex> следует, что <tex>m_i \geqslant k</tex>. Отсюда получаем неравенство:

<tex>\sum\limits_{i=1}^n m_i = \sum\limits_{i=1}^n (\alpha_i + \beta_i + \gamma_i) = \sum\limits_{i=1}^n \alpha_i + \sum\limits_{i=1}^n \beta_i + \sum\limits_{i=1}^n \gamma_i \geqslant kn ~~~ \textbf{(2)}</tex>

Заметим, что все множества рёбер <tex>A_i \subset E(G')</tex> и <tex>B_j \subset F</tex> не пересекаются(так как <tex>E(G') = E(G) \setminus F</tex>) и ведут во множество <tex>S</tex>. Поэтому сумма <tex>\sum\limits_{i=1}^t |A_i| + \sum\limits_{i=1}^t |B_i| = \sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i</tex> не превосходит суммарную степень вершин в <tex>S</tex>. Во множестве <tex>S</tex> находится всего <tex>|S|</tex> вершин, степень каждой не превосходит <tex>k</tex>. Поэтому суммарная степень вершин в <tex>S</tex> не превосходит <tex>k|S|</tex>. Отсюда получаем неравенство:

<tex>\sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i \leqslant k|S| ~~~ \textbf{(3.1)}</tex>

Заметим, что множества рёбер <tex>B_i</tex> и <tex>C_j</tex>, не пересекаются, так как <tex>B_i</tex> ведут из <tex>U_i</tex> в <tex>S</tex>, а <tex>C_j</tex> ведут из <tex>U_j</tex> в <tex>U_k</tex>, (<tex>k \neq j</tex>). Так как <tex>B_i \subset F</tex> и <tex>C_j \subset F</tex>, то сумма <tex>\sum\limits_{i=1}^t |B_i| + \sum\limits_{i=1}^t |C_i| = \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i</tex> не превосходит мощности <tex>F</tex>, откуда имеем:

<tex>2 \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant 2|F| \leqslant 2k - 2 ~~~ \textbf{(3.2)}</tex> (так как <tex>|F| \leqslant k - 1</tex>)

Сложив <tex>\textbf{(3.1)}</tex> и <tex>\textbf{(3.2)}</tex>, получаем

<tex>\sum\limits_{i=1}^t \alpha_i + 3\sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant k(|S| + 2) - 2 ~~~ \textbf{(3)}</tex>

Так как <tex>\sum\limits_{i=1}^n \alpha_i + \sum\limits_{i=1}^n \beta_i + \sum\limits_{i=1}^n \gamma_i \leqslant \sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant \sum\limits_{i=1}^t \alpha_i + 3\sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i</tex> из неравенств <tex>\textbf{(2)}</tex> и <tex>\textbf{(3)}</tex> получаем <tex>kn \leqslant k(|S| + 2) - 2</tex>

Тогда <tex>k(n - |S| - 2) \leqslant -2</tex>, следовательно, <tex>k(n - |S| - 2) \leqslant 0</tex>

<tex>k > 0</tex>, следовательно <tex>n - |S| - 2 \leqslant 0</tex>

и, следовательно, <tex>odd(G' \setminus S) = n < |S| + 2</tex>, что противоречит <tex>\textbf{(1)}</tex>. Таким образом, множество Татта найти нельзя, значит, в <tex>G'</tex> существует совершенное паросочетание.
}}

==Следствия==

Заметим, что [[Совершенное паросочетание в кубическом графе#th1 | Теорема Петерсона]] является следствием из этой теоремы, так как в графах Петерсена <tex>k = 3</tex>, <tex>\lambda(G) \leqslant 2 = k - 1</tex>, <tex>|V|</tex> чётно и <tex>|F| = 0 \leqslant k - 1</tex>

{{Утверждение
|id = statement2
|statement = Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], с чётным числом вершин, причём <tex>\lambda(G) \geqslant k - 1</tex>. Тогда для любого ребра <tex>e \in E(G)</tex> существует совершенное паросочетание графа <tex>G</tex>, содержащее <tex>e</tex>.
|proof =
Пусть <tex>e = uv</tex>, а <tex>e_1 \cdots e_{k-1}</tex> {{---}} остальные рёбра, инцидентные вершине <tex>u</tex>. Согласно теореме, в графе <tex>G \setminus \{ e_1 \cdots e_{k-1} \}</tex> есть совершенное паросочетание <tex>M</tex>. Так как <tex>u</tex> покрывается <tex>M</tex>, а <tex>e</tex> {{---}} единственное ребро <tex>G \setminus \{ e_1 \cdots e_{k-1} \}</tex>, инцидентное <tex>u</tex>, <tex>u \in M</tex>
}}

==См. также==
* [[Совершенное паросочетание в кубическом графе]]

==Источники информации==
* Карпов В. Д. - Теория графов, стр 43

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

Файл:Плешник 1.png

2017-11-29T20:09:19Z

KokorinIlya:

Совершенное паросочетание в кубическом графе

2017-11-29T19:56:33Z

KokorinIlya: /* Лемма о сравнимости по модулю 2 */

==Лемма о сравнимости по модулю 2==
{{Лемма
|id = lemma1
|statement =
Пусть <tex>G</tex> {{---}} <tex>k</tex>-[[Основные определения теории графов#defRegularGraph |регулярный граф]], <tex>U \in V(G)</tex>, <tex>|U|</tex> нечётно, <tex>m</tex> {{---}} число рёбер, соединяющих вершины множества <tex>U</tex> с вершинами из <tex>V(G) \setminus U</tex>. Тогда <tex>m \equiv k \pmod 2</tex>
|proof =
[[Файл:Сравнимость.png|300px|thumb|left|Иллюстрация к лемме]]
<tex>m = (\sum\limits_{v \in U} d_G(v)) - 2e(G(U))</tex>, где <tex>e(G(U))</tex> {{---}} количество рёбер, соединяющих вершину из <tex>U</tex> с другой вершиной из <tex>U</tex>.

тогда <tex>m = k|U| - 2e(G(U))</tex>.

<tex>2e(G(U))</tex> чётно, поэтому <tex>m \equiv k|U| \pmod 2</tex>. Так как <tex> |U|</tex> нечётно, <tex>m \equiv k \pmod 2</tex>.
}}

==Теорема Петерсона (Petersen)==
{{Определение
|id=cube_graf_def
|definition= '''Кубический граф''' (англ. ''Cubic graph'') {{---}} [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл| граф]], в котором все вершины имеют степень три. Другими словами, кубический граф является <tex>3</tex>-регулярным.}}

{{Теорема
|id=th1
|author=Петерсон
|statement = Пусть <tex>G</tex>{{---}}[[Отношение связности, компоненты связности#connected_graph | связный]] кубический граф, в котором не более <tex>2</tex> [[Мост, эквивалентные определения | мостов]]. Тогда в <tex>G</tex> есть [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#perfect_matching | совершенное паросочетание]].
|proof =
Предположим, что совершенного паросочетания в <tex>G</tex> нет, тогда можно выбрать [[Теорема Татта о существовании полного паросочетания#Tutt_set | множество Татта]] <tex>S \subset V(G)</tex>.

Пусть <tex>U_1, \ldots, U_n</tex> {{---}} все нечётные компоненты связности графа <tex>G \setminus S</tex>. <tex>m_i</tex> {{---}} количество ребёр <tex>G</tex>, связывающих вершины <tex>U_i</tex> с вершинами <tex>S</tex>.

По предыдущей лемме, все <tex>m_i</tex> нечётны. Так как не более чем два ребра графа <tex>G</tex> {{---}} мосты, то не более, чем два числа из <tex>m_1, \ldots, m_n</tex> равны <tex>1</tex>, остальные числа не менее <tex>3</tex>.

Так как <tex>S</tex> {{---}} множество Татта, то <tex>odd(G \setminus S) > |S|</tex>. Так как количество вершин кубического графа <tex>G</tex> чётно, мы имеем <tex>S \neq \emptyset, odd(G \setminus S) \equiv S \pmod 2</tex>, следовательно, <tex>n = odd(G \setminus S) \geqslant |S| + 2</tex>. Тогда

<tex>\sum\limits_{v \in S} d_G(v) \geqslant \sum\limits_{i = 1}^n m_i \geqslant 3n - 4 \geqslant 3(|S| + 2) - 4 = 3|S|
+ 2 > 3|S| = \sum\limits_{v \in S} d_G(v)</tex>, что, очевидно, невозможно.

Найдено противоречие, следовательно, множество Татта выбрать невозможно, следовательно, в <tex>G</tex> есть совершенное паросочетание.
}}

==Теорема Фринка (Frink)==
{{Теорема
|id=th2.
|author=Фринк
|statement=

Пусть <tex>G = (V, E)</tex> {{---}} двусвязный кубический граф.
Возьмём ребро <tex>p = (c, d)</tex>. Пусть вершины <tex>a</tex> и <tex>b</tex> смежны с вершиной <tex>c</tex>, а вершины <tex>e</tex> и <tex>f</tex> смежны с вершиной <tex>d</tex> (рисунок <tex>1 (a)</tex>).
Как минимум одно из двух сокращений графа <tex>G</tex>, состоящее из удаления вершин <tex>c, d</tex> и пересоединения вершин <tex>a, b, e, f</tex> рёбрами <tex>(a, e), (b, f)</tex> или <tex>(a, f), (b, e)</tex> (рисунок <tex>1 (b), (c)</tex>, рисунок <tex>2</tex>) сохранит двусвязность графа.

|proof=
Обозначим компоненты графа <tex>G(V - \{c, d\})</tex> как <tex>A, B, E, F</tex>, которые содержат вершины <tex>a, b, e, f</tex> соответственно. Так как <tex>G</tex> не имеет мостов (соответственно <tex>p</tex> не является мостом) должно существовать ребро, соединяющее одну из компонент <tex>A</tex> или <tex>B</tex>, с одной из компонент <tex>E</tex> или <tex>F</tex>. Без потери общности предположим, что <tex>A</tex> соединено с <tex>E</tex>. Заметим, что рёбра <tex>(b, c), (d, f)</tex> так же не являются мостами, значит возможны три случая (с учётом изоморфизма) (рисунок <tex>3</tex>):
* компонента <tex>B</tex> соединена с <tex>F</tex>,
* компонента <tex>B</tex> соединена с <tex>E</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>,
* компонента <tex>A</tex> соединена с <tex>B</tex> и компонента <tex>E</tex> соединена с <tex>F</tex>.
Во всех трёх случаях если <tex>G(V - \{c, d\})</tex> расширить рёбрами <tex>(a, f), (b, e)</tex> (получим граф <tex>G'</tex>), добавленные рёбра будут лежать на некотором [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл| цикле]] в <tex>G'</tex> (рисунок <tex>4</tex>). Так же для любой пары вершин <tex>u, v</tex> <math>\in</math> <tex>\{a, b, e, f\}</tex> существует цикл в <tex>G'</tex>, содержащий данные вершины. Чтобы доказать, что <tex>G'</tex> двусвязен, нужно показать, что каждое ребро <tex>r</tex> из <tex>G'</tex> лежит на некотором цикле в <tex>G'</tex>. Пусть цикл <tex>C</tex> в <tex>G</tex> содержит <tex>r</tex> (такой цикл существует, так как <tex>G</tex> двусвязен). Если <tex>C</tex> не проходит через вершины <tex>c, d</tex> тогда <tex>C</tex> так же является циклом в <tex>G'</tex>, иначе построим цикл <tex>C'</tex> графа <tex>G'</tex> из <tex>C</tex> следующим образом:
* если путь <tex> x - c - d - y </tex> <math>\in</math> <tex> C </tex>, <tex> x </tex> <math>\in</math> <tex> \{a, b\} </tex>, <tex> y </tex> <math>\in</math> <tex> \{e, f\} </tex>, удалим этот путь и добавим любой другой из <tex> x </tex> в <tex> y </tex> в <tex> G' </tex>, не содержащий <tex>r</tex> (такой путь всегда существует, так как <tex> x </tex> и <tex> y </tex> принадлежат некоторому циклу в <tex> G' </tex>),
* если путь <tex> a - c - b </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> a </tex> в <tex> b </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>,
*если путь <tex> e - d - f </tex> <math>\in</math> <tex> C </tex>, удалим этот путь и добавим любой другой из <tex> e </tex> в <tex> f </tex> в <tex> G' </tex>, не содержащий <tex>r</tex>.

<tex>C'</tex> это набор циклов (так как <tex>C'</tex> получен из <tex>C</tex> путём преобразования некоторых путей) и содержит <tex>r</tex>. Из этого следует, что каждое ребро графа <tex>G'</tex> лежит на некотором цикле, то есть граф не содержит мостов. Значит <tex>G'</tex> двусвязен.
}}

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm1.png|thumb|500px|Рисунок 1. Сокращение двусвязного кубического графа. <tex>(a)</tex> Нужно удалить вершины <tex>c, d</tex>. <tex>(b)</tex> первый тип сокращения {{---}} вершина <tex>a</tex> соединена с <tex>e</tex>, вершина <tex>b</tex> соединена с <tex>f</tex>. <tex>(c)</tex> второй тип сокращений {{---}} вершина <tex>a</tex> соединена с <tex>f</tex>, вершина <tex>b</tex> соединена с <tex>e</tex>.]]
|[[Файл:Frinks_algorithm2.PNG|thumb|500px|Рисунок 2. Особые случаи сокращения графа. <tex>(a)</tex> ребро <tex>(c, d)</tex>, которое нужно удалить, кратное. Сокращение удаляет вершины <tex>c, d</tex> из графа и соединяет <tex>a</tex> и <tex>e</tex> новым ребром. <tex>(b)</tex> ребро <tex>(c, d)</tex> инцидентно двум двойным рёбрам <tex>(a, c)</tex> и <tex>(d, e)</tex>. Сокращение удаляет вершины <tex>c, d</tex> и добавляет новое кратное ребро <tex>(a, e)</tex>. <tex>(c)</tex> Ребро <tex>(c, d)</tex> инцидентно одному ребру <tex>(d, e)</tex>. Сокращение удаляет вершины <tex>c, d</tex> и добавляет два новых ребра <tex>(a, e)</tex> и <tex>(b, e)</tex>. <tex>(d)</tex> Ребро <tex>(c, d)</tex> тройной кратности. Сокращение удаляет вершины <tex>c, d</tex>. ]]
|}

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm3.PNG|thumb|500px|Рисунок 3. Все возможные соединения двусвязных компонент графа <tex>G[V - \{c,d\}]</tex>. <tex>(a)</tex> Компонента <tex>A</tex> соединена с компонентой <tex>E</tex>, компонента <tex>B</tex> соединена с компонентой <tex>F</tex>. <tex>(b)</tex> Компонента <tex>E</tex> соединена с компонентами <tex>A, B, F</tex>. <tex>(c)</tex> Компонента <tex>A</tex> соединена с компонентами <tex>B, E</tex>, компонента <tex>E</tex> соединена с компонентой <tex>F</tex>. ]]
|[[Файл:Frinks_algorithm4.PNG|thumb|500px|Рисунок 4. Возможные соединения двусвязный компонент <tex>A, B, E, F</tex> после удаления ребра <tex>(c, d)</tex> и добавления рёбер <tex>(a, f)</tex> и <tex>(b, e)</tex>.]]
|}

==Алгоритм поиска совершенного паросочетания (Frink's algorithm)==
Будем сокращать данный граф <tex>G</tex> вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины.
Когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений, то есть будем восстанавливать граф (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешимо за <tex>O(1)</tex>. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.

{|align="center"
|-valign="center"
|[[Файл:Frinks_algorithm5.PNG|thumb|400px|Рисунок 5. Базовые случаи восстановления графа.]]
|[[Файл:Frinks_algorithm6.PNG|thumb|400px|Рисунок 6. Особые случаи восстановления графа.]]
|}

==Псевдокод алгоритма Фринка==
*<tex>G</tex> {{---}} двусвязный кубический граф,
*<tex>M</tex> {{---}} совершенное паросочетание <tex>G</tex>,
*функция <tex>\mathtt{bridgeless}</tex> возвращает <tex>true</tex> если у графа нет моста или <tex>false</tex> в противном случае,
*функция <tex>\mathtt{alternatingCycle}</tex> принимает три параметра: граф, совершенное паросочетание и ребро. Возвращает альтернативный цикл, включающий в себя данное ребро и обновляет совершенное паросочетание,
*функция <tex>\mathtt{reductions}</tex> сокращает граф,
*функция <tex>\mathtt{simpleReversion}</tex> восстанавливает граф,
*функция <tex>\mathtt{reductedGraph}</tex> принимает три параметра: граф, удаляемые вершины, добавляемые рёбра. Возвращает новый граф, у которого удалены выбранные вершины, вместе c инцидентными рёбрами и добавлены другие рёбра, переданные в параметрах. При этом исходный граф не меняется.

'''function''' frinkMatching<tex>(G)</tex>:
'''if''' <tex>|V| = 0</tex>
'''return''' <tex>\varnothing</tex>
<tex>v - w = E[0]</tex>
<tex>R = </tex> reductions<tex>(G, v - w)</tex>
'''if''' bridgeless<tex>(</tex>reductedGraph<tex>(G, \{v, w\}, R[0]))</tex>
<tex>r = R[0]</tex>
'''else'''
<tex>r = R[1]</tex>
<tex>M =</tex> frinkMatching<tex>(</tex>reductedGraph<tex>(G,\{v, w\}, r))</tex>
'''if''' <tex>|r \cap M| = 2 </tex>
<tex>C =</tex> alternatingCycle<tex>(G, M, r[0])</tex>
<tex>M = M \oplus C</tex>
<tex>M = (M - r)\ \cup </tex> simpleReversion<tex>(G, v, w, r, M)</tex>
'''return''' <tex>M</tex>

==Время работы алгоритма Фринка==
Операция сокращения должна на каждом шаге проверять граф на наличие мостов за <tex>O(n)</tex>, кроме того, при возникновении четвёртого базового случая требуется найти альтернативный цикл за <tex>O(n)</tex>. В алгоритме <tex>O(n)</tex> операций сокращения и восстановления графа, причем каждая из этих операций требует <tex>O(n)</tex> времени. Таким образом, весь этот алгоритм исполняется за время <tex>O(n^2)</tex>.

==См. также==

* [[Использование обхода в глубину для поиска цикла]]
* [[Использование обхода в глубину для поиска мостов]]
* [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях]]

== Источники информации ==
* [https://www.lektorium.tv/course/22771 Лекториум {{---}} Дополнительные главы теории паросочетаний]
* [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 Wikipedia {{---}} Кубический граф]
* Piotr Stanczyk {{---}} THEORY AND PRACTICE OF COMPUTING MAXIMUM MATCHINGS IN GRAPHS стр. 21-28.
* Карпов В. Д. - Теория графов, стр 42

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о паросочетании]]

Файл:Сравнимость.png

2017-11-29T19:54:45Z

KokorinIlya:

Файл:Татт 2.png

2017-11-29T19:33:00Z

KokorinIlya: загружена новая версия «Файл:Татт 2.png»

Теорема Татта о существовании регулярного графа заданного размера с заданным обхватом

2017-11-29T19:20:58Z

KokorinIlya: /* Теорема */

{{Определение
|id = defMain.
|definition = '''Обхват''' ''(англ. girth)'' графа <tex>G</tex> (обозначается <tex>g(G)</tex>) {{---}} это длина наименьшего простого цикла в графе <tex>G</tex>
}}

==Лемма о существовании вершины на заданном расстоянии==
{{Лемма
|statement= Пусть <tex> k, g \in \mathbb{N} </tex>, причём <tex> k \geqslant 3</tex>, <tex>G</tex>{{---}}граф, <tex>|V(G)| > \dfrac{k(k-1)^{g-1} - 2}{k - 2} </tex>, <tex>\forall v \in V(G) : d_G(v) \leqslant k;</tex> <tex> x, y \in V(G), d_G(x), d_G(y) \leqslant k - 1</tex>, тогда существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.
|proof =
[[Файл:Лемма к Татту.png|300px|thumb|left|Иллюстрация к теореме для <tex>k = 4</tex>. У вершины <tex>x</tex>(чёрной) не более <tex>k - 1 = 3</tex> соседей (синих вершин), у каждой из <tex>k - 1</tex> синих вершин не более <tex>k - 1</tex> нерассмотренных соседей (красных вершин), то есть красных вершин не более <tex>(k - 1)^2</tex>, и так далее]]
Так как <tex>d_G(x), d_G(y) \leqslant k - 1 </tex>, а степени остальных вершин графа не более <tex>k</tex>, то на расстоянии не более <tex>g - 1</tex> от <tex>y</tex> находится не более чем <tex>1 + (k - 1) + \ldots + (k - 1)^{g - 1} = \sum\limits_{n=0}^{g - 1} (k - 1)^n = \dfrac{(k-1)^{g} - 1}{k - 2}</tex> вершин графа, а на расстоянии не более <tex>g - 2</tex> от <tex>x</tex> находится не более чем <tex>1 + (k - 1) + \ldots + (k - 1)^{g - 2} = \sum\limits_{n=0}^{g - 2} (k - 1)^n =\dfrac{(k-1)^{g - 1} - 1}{k - 2}</tex> вершин. Так как <tex>\dfrac{(k-1)^{g - 1} - 1}{k - 2} + \dfrac{(k-1)^{g} - 1}{k - 2} = \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, а <tex> |V(G)| > \dfrac{k(k-1)^{g-1} - 2}{k - 2}</tex>, то существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.
}}

==Теорема==

{{Теорема
|id = thMain.
|author = В. Татт
|statement = Пусть <tex> k, g, n \in \mathbb{N} </tex>, причём <tex> k, n \geqslant 3, n > \dfrac{k(k-1)^{g-1} - 2}{k - 2}, kn </tex> чётно. Тогда существует <tex>k</tex>-[[Основные определения теории графов#defRegularGraph | регулярный граф]] <tex>G</tex> c обхватом <tex>g(G) = g</tex> и количеством вершин <tex> |V| = n</tex>
|proof =
Пусть <tex>G_{set}(g, n, k)</tex> {{---}} семейство всех графов с <tex>n</tex> вершинами, обхватом <tex>g</tex> и максимальной степенью вершин не более <tex>k</tex>. При <tex>n > g</tex> очевидно, что <tex>G_{set}(g, n, k) \neq \emptyset</tex>: например, этому множеству принадлежит граф, состоящий из простого цикла на <tex>g</tex> вершинах и <tex>n - g</tex> изолированных вершин.

Пусть <tex>v_{<k}(G)</tex> {{---}} количество вершин степени меньше <tex>k</tex> в графе <tex>G</tex>, а <tex>dist_{<k}(G)</tex> {{---}} максимальное из расстояний между парами вершин степени менее <tex>k</tex> в графе <tex>G</tex>. (при <tex>v_{<k}(G) < 2</tex>, положим <tex>dist_{<k}(G) = 0</tex>). Выберем в <tex>G_{set}(g, n, k)</tex> граф следующим образом: сначала выберем все графы с максимальным количеством рёбер, затем из них выберем графы с максимальным <tex>v_{<k}</tex>, и, наконец, из оставшихся выберем граф <tex>G</tex> c максимальным <tex>dist_{<k}(G)</tex>. Если таких графов несколько, выберем любой.

Докажем, что <tex>G</tex> {{---}} регулярный граф степени <tex>k</tex>.

Предположим, что это не так и рассмотрим пару его максимально удаленных вершин степени менее <tex>k</tex>: пусть это будут вершины <tex>x</tex> и <tex>y</tex> (если вершина степени менее <tex>k</tex> в графе всего одна, то <tex>x =
y</tex>).

# [[Файл:Татт 1.png|300px|thumb|right|Расположение вершины <tex>z</tex> относительно вершин <tex>x</tex> и <tex>y</tex>]] Если <tex>dist_G(x, y) \geqslant g - 1</tex>, то соединим их ребром и получим граф <tex>G' = G \cup xy, G'\in G_{set}(g, n, k)</tex>, при этом <tex>|E(G')| > |E(G)|</tex> (так как в графе <tex>G'</tex> есть все те рёбра, которые есть в <tex>G</tex>, и ребро <tex>xy</tex>). Значит, граф <tex>G</tex> не может быть выбран из множества <tex>G_{set}(g, n, k)</tex>, так как у него не максимальное количество рёбер.
# Так <tex>d_G(x), d_G(y) \leqslant k - 1 </tex>, а степени остальных вершин графа не более <tex>k</tex>, то по лемме существует такая вершина <tex>z</tex>, что <tex>dist(x, z) \geqslant g - 1</tex> и <tex>dist(y, z) \geqslant g</tex>.
## <tex>d_G(z) < k</tex>. В таком случае, <tex>d_G(z) < k, d_G(y) < k, dist_G(y, z) \geqslant g</tex>, что невозможно, согласно пункту 1. В таком случае:
## <tex>d_G(z) = k \geqslant 3</tex>, следовательно, существует ребро <tex>zu \in E(G)</tex>, через которое проходят не все простые циклы длины <tex>g</tex> графа <tex>G</tex>, тогда <tex>g(G \setminus zu) = g(G) = g</tex>

[[Файл:Татт 2.png|300px|thumb|left|Получение графа <tex>G'</tex> из графа <tex>G</tex>]]

Пусть <tex>G' = G \setminus zu \cup zx</tex>. Тогда из

<tex> dist_G(y, u) \geqslant dist_G(y, z) - 1 \geqslant g - 1 > dist_G(x, y) = dist_{<k}(G) ~~~ \textbf{(1)} </tex>.

следует, что <tex>d_G(u) = k</tex>.

<tex>g(G') = g(G) = g, |E(G')| = |e(G)| - 1 + 1 = |E(G)| </tex>. Тогда

<tex> d_{G'}(x) = d_G(x) + 1 \leqslant k, d_{G'}(u) = d_G(u) - 1 = k - 1 ~~~ \textbf{(2)} </tex>.

Степени всех остальных вершин в <tex>G</tex> и <tex>G'</tex> совпадают. Тогда <tex>G' \in G_{set}(g, n, k)</tex>. Из <tex>\textbf{(2)}</tex> следует, что <tex>v_{<k}(G') \geqslant v_{<k}(G)</tex>. Тогда ввиду выбора графа <tex>G</tex> должно быть <tex>v_{<k}(G') = v_{<k}(G)</tex>, что возможно лишь при <tex>d_{G'}(x) = k</tex> и <tex>d_G(x) = k - 1</tex>. Так как <tex>kn</tex> чётно, вершина <tex>x</tex> не может быть единственной вершиной степени менее <tex>k</tex> в графе <tex>G</tex>, поэтому <tex>x \neq y</tex>.

Докажем, что <tex>dist_{G'}(y, u) > dist_{G}(y, x)</tex>. Действительно, рассмотрим путь <tex>P: y \leadsto u</tex>, который реализует расстояние между <tex>y</tex> и <tex>u</tex> в <tex>G'</tex>. Если <tex>P</tex> проходит только по рёбрам <tex>G</tex>, то, учитывая <tex>\textbf{(1)}</tex>, получаем

<tex> dist_{G'}(y, u) = dist_G(y, u) \geqslant g - 1 > dist_G(y, x) </tex>

Значит, <tex>P</tex> проходит по ребру <tex>zx</tex>. Следовательно, <tex>P</tex> содержит путь по рёбрам графа <tex>G</tex> от <tex>y</tex> до одной из вершин <tex>x</tex> или <tex>z</tex> и ребро <tex>xz</tex>. Тогда

<tex> dist_{G'}(y, u) = \min(dist_G(y, x), dist_G(y, z)) + 1 > dist_G(y, x) </tex>,

так как <tex>dist_G(y, z) \geqslant g > dist_G(y, x)</tex>. Таким образом

<tex> dist_{<k}(G') \geqslant dist_{G'}(y, u) > dist_G(y, x) dist_{<k}(G) </tex>

Получили противоречие с принципом выбора графа <tex>G</tex>, что доказывает, что <tex>G</tex> {{---}} <tex>k</tex>-регулярный.

}}

==См. также==
* [[Основные определения теории графов]]

==Источники информации==
* Карпов В. Д. - Теория графов, стр 108

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обходы графов]]

Файл:Татт 2.png

2017-11-29T19:15:39Z

KokorinIlya: