1632
правки
Изменения
м
== Уравнение Лагранжа и теорема Лагранжа ==
Рассмотрим уравнение <tex>l(s) = n(sl(s))</tex>. Чтобы привести к классическому виду, домножим обе части на <tex>s</tex> [[Категория: Дискретная математика и положим <tex>sl(s) = \tilde{l} (s) </tex>. Тогда уравнение примет вид <tex> \tilde{l} (s) = sn(\tilde{l} (s)) </tex> — '''уравнение Лагранжа''' (англ. '''Lagrange equation').алгоритмы]][[Категория: Производящая функция]]
rollbackEdits.php mass rollback
{{Определение
|definition=
[[Основные определения, связанные со строками#string | Слово]] <tex>w = \beta_1 \ldots \beta_m</tex> [[Основные определения, связанные со строками#deflanguage | языка]] <tex>L</tex> называется '''неразложимым''' (англ. ''indecomposable word'') в этом языке, если никакое его непустое подслово <tex> \beta_i \beta_{i+1} \ldots \beta_{i+l},\, 1 \leqslant i,\, i + l \leqslant m,\, l \geqslant 0,</tex> отличное от самого слова <tex>w,</tex> не принадлежит языку <tex>L</tex>.
}}
:4) если из любого слова языка <tex>L</tex> выкинуть подслово, входящее в язык <tex>L</tex>, то получится слово языка <tex>L</tex>
Обозначим через <tex>n(t) = n_0 + n_1 t + n_2 t^2 + \ldots</tex> [[Производящая функция | '''производящую функцию''']] '''для числа неразложимых слов языка''' <tex>L</tex>, через <tex>L(s) = l_0 + l_1 s + l_2 s^2 + \ldots</tex> — [[Язык Дика#def3 | '''производящую функцию для языка''' ]] <tex>L</tex> .
{{Теорема
}}
== Уравнение Лагранжа и теорема Лагранжа ==
Часто для нахождения числа слов определенной длины в заданном языке выгодно найти производящую функцию этого языка.
Посмотрим на равенство <tex>l(s) = n(sl(s))</tex>. Это функциональное уравнение, связывающее между собой производящие функции для числа слов в языке и числа неразложимых слов в нем. Хотелось бы уметь находить одну из этих функций, зная другую, то есть уметь решать это уравнение, если одна из функций задана. Это всегда возможно.
Рассмотрим уравнение <tex>l(s) = n(sl(s))</tex>. Чтобы привести к классическому виду, домножим обе части на <tex>s</tex> и положим <tex>sl(s) = \tilde{l} (s) </tex>. Тогда уравнение примет вид <tex> \tilde{l} (s) = sn(\tilde{l} (s)) </tex> — '''уравнение Лагранжа''' (англ. ''Lagrange equation'').
{{Теорема
|author=Лагранж
|about=(англ. ''the Lagrange theorem'')
|statement=
Пусть в уравнении <tex> \tilde{l} (s) = sn(\tilde{l} (s)) </tex> задана одна из производящих функций <tex> \tilde{l} (s) \, (\tilde{l_0} = 0,\, \tilde{l_1} \neq 0) </tex> или <tex>n(t) \,(n_0 \neq 0)</tex>. Тогда вторая производящая функция однозначно восстанавливается по ней.
|proof=
Уравнение <tex> \tilde{l} (s) = sn(\tilde{l} (s)) </tex> можно переписать в следующем виде:
<tex> \tilde{l_1}s + \tilde{l_2}s^2 + \ldots = n_0 s + n_1 s (\tilde{l_1}s + \tilde{l_2}s^2 + \tilde{l_3}s^3 + \ldots) +
n_2 s({\tilde{l_1^2}}s^2 + 2\tilde{l_1}\tilde{l_2}s^3 + \ldots) +
n_3s({\tilde{l_1^3}}s + \ldots) + \ldots </tex>
Докажем сначала, что если функция <tex> \tilde{l} (s)</tex> задана, то <tex>n(t)</tex> однозначно восстанавливается по ней. Доказательство проведем по индукции, приравнивая последовательно коэффициенты при одинаковых степенях <tex>s</tex> в левой и правой частях.
Коэффицент <tex>n_0</tex> определяется равенством <tex>n_0 = \tilde{l_1}</tex>. Предположим теперь, что коэффициенты <tex>n_0, n_1, \ldots, n_{k-1}</tex> уже определены. Тогда коэффициент <tex>n_k</tex> определяется из уравнения, составленного приравниванием коэффициентов при <tex>s^{k+1}</tex>:
<tex> n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. </tex>
Здесь через <tex>\lambda_i, \, i = 2, \ldots, k-1, </tex> обозначены коэффиценты при <tex>s^{k}</tex> в производящих функциях <tex> \tilde{l}^i (s) </tex>. Уравнение
<tex> n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. </tex>
— линейное уравнение относительно <tex> n_k </tex>. Коэффициент при <tex> n_k </tex> в нем равен <tex>\tilde{l}_1^k </tex> и, по
условию теоремы, отличен от нуля. Поэтому <tex>n_k</tex> однозначно определяется из уравнения
<tex> n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k. </tex>
С другой стороны, если задана функция <tex>n(t)</tex>, то мы должны положить <tex>\tilde{l}_1 = n_0</tex>. Коэффициенты <tex>\tilde{l}_k </tex> определяются теперь равенством
<tex> n_k\, \tilde{l}_1^k + n_{k-1}\, \lambda_{k-1} + \ldots + n_1\, \lambda_1 = \tilde{l}_k, </tex> так как все оэффициенты <tex>\lambda_i</tex> являются многочленами от
<tex> \tilde{l}_1, \ldots, \tilde{l}_{k-1} </tex>.
}}
'''Замечание'''
Если коэффициенты функции <tex>n</tex> —целые неотрицательные числа, то и коэффициенты функции <tex>\tilde{l}</tex> будут целыми и неотрицательными. Если коэффициенты функции <tex>\tilde{l}</tex> целые и неотрицательные, причем <tex>\tilde{l}_1 = 1,</tex> то и коэффициенты функции <tex>n</tex> оказываются целыми. Однако при этом среди них могут оказаться и отрицательные числа.
== См. также ==
*[[Производящая функция]]
*[[Язык Дика]]
*[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]]
== Источники информации ==
* С. А. Ландо: Лекции о производящих функциях
* Гросс М., Лантен А.: Теория формальных грамматик
