195
правок
Изменения
м
progress...
<tex dpi="350">c_n=\sum_{k=0}^{n}a_k b_{n-k}</tex>
{{Утверждение|statement=<tex dpi="350">C(t)=A(t) \cdot B(t)</tex> ''(Последнее равенство верно|proof=Верно, потому что коэффициенты производящей функции описываются описываются равенством выше)''}}
===Последовательности комбинаторных классов===
{{Утверждение
|statement=<tex dpi="350">Seq_k(A)(t)=A(t)^k</tex>
|proof=Докажем по индукции:
'''База <tex dpi="350">k=1</tex>'''.
:Для <tex dpi="350">k=1</tex> верно, потому что <tex dpi="350">Seq_1(A)=A \Rightarrow Seq_1(A)(t)=A(t)=A(t)^1</tex>.
'''Переход'''.
:Пусть для <tex dpi="350">k=n</tex> верно <tex dpi="350">Seq_n(A)(t)=A(t)^n</tex>. Докажем для
<tex dpi="350">k=n+1</tex> <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^{n+1}</tex>. Рассмотрим <tex dpi="350">Seq_{n+1}(A)</tex> как <tex dpi="350">Pair(Seq_n(A), A)</tex>. Тогда <tex dpi="350">Seq_{n+1}(A)(t)=A(t)^n*A(t)=A(t)^{n+1}</tex>.
}}
----
