195
правок
Изменения
м
progress...
==Метод производящих функций==
Непомеченные комбинаторные объекты
Каждый комбинаторный объект состоит из атомов.
У атомов определен вес.
</tex dpi="130">w(\bullet)=1</tex>
</tex dpi="130">w(\circ)=0</tex>
Определение:
Комбинаторным объектом <tex dpi="130"">Z</tex> называется комбинаторный объект, состоящий из одного атома веса <tex dpi="130"">1</tex>.
<tex dpi="150"Z={\bullet}></text>
Комбинаторным объектом <tex dpi="130"">\varepsilon</tex> называется комбинаторный объект, состоящий из одного атома веса <tex dpi="130"">0</tex>.
<tex dpi="150"\varepsilon={\circ}></text>
Такие большие группы часто анализируют с помощью [[Производящая функция|производящих функций]]. Один из популярных методов {{---}} метод символов <ref>[[wikipedia:Symbolic method (combinatorics) | Wikipedia {{---}} Symbolic method]]</ref>. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества.
{{Утверждение
|statement=
<tex dpi="150">Seq(A)(t)=\frac{1}{1-A(t)}</tex>.
|proof=
<tex dpi="130"">S_{0} = 1</tex>, так как есть единственный способ составить пустую последовательность.
Докажем по индукции.
'''База <tex dpi="130"">n = 1</tex>'''.
:<tex dpi="130"">S_{1}=w_{1} S_{0}=w_{1}</tex>, что верно, так как единственный способ составить последовательность веса <tex dpi="130"">1</tex> {{---}} это взять любой элемент веса <tex dpi="130"">1</tex>.
'''Переход'''.
:Пусть для <tex dpi="130"">j < n</tex> верно. Докажем для <tex dpi="130"">n</tex>. Возьмем произвольный элемент из <tex dpi="130"">A</tex> веса <tex dpi="130"">i \leqslant n</tex>, и допишем его к последовательности элементов веса <tex dpi="130"">n-i</tex>. Образуется новая последовательность веса <tex dpi="130"">n</tex>. Причем никакая последовательность не будет учтена дважды, так как прежде не было последовательностей веса <tex dpi="130"">n</tex> и ни к какой последовательности меньшего веса мы не добавляем один и тот же элемент дважды.
}}
При непомеченных объектах рассмотренные классы имеют следующие производящие функции:
