Изменения
→Количество PSet из элементов 0 и 1: w_1 = 2
{{Определение
|definition=
<tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex>, <tex dpi="130">B=\{b_{1},b_{2}, \ldots ,b_{z_{1}}\}</tex> {{---}} множества из различных объектов. <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{l}\}</tex> {{---}} количество объектов веса от <tex dpi="130">1</tex> до <tex dpi="130">l</tex>, составленных из элементов <tex dpi="130">A</tex>, а <tex dpi="130">U=\{u_{1},u_{2}, \ldots ,u_{l}\}</tex> {{---}} соответственно для <tex dpi="130">B</tex>.
}}
В дальнейшем, будем считать что нет объектов веса <tex dpi="130"">0</tex>, так как в противном случае существует бесконечное количество рассматриваемых комбинаторных объектов любого веса и подсчет теряет смысл, или подсчет сводится к рассматриваемому случаю. Отведем данный вес под пустое множество(то есть <tex dpi="130">w_{0}=1</tex>).
Пусть <tex dpi="130">A=\{1, 2\}</tex>, <tex dpi="130">W=\{1, 1, 0 \ldots 0\}</tex>, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех последовательностей из маленьких и больших элементов, <tex dpi="130">S_{1}=1</tex>.
Тогда, <tex dpi="150">S_{n}=\sum\limits_{i=1}^{n} w_{i} S_{n-1i}=S_{n-1}+S_{n-2}=F_{n}</tex>, где <tex dpi="150">F_{n}</tex> {{---}} <tex>n</tex>-ое число Фибоначчи <ref>[[wikipedia:Fibonacci number|Wikipedia {{---}} Числа Фибоначчи]]</ref>.
===Подсчет подвешенных непомеченных деревьев с порядком на детях===
:<tex dpi="150">P_{0}=p_{0, 0} = 1</tex>.
:<tex dpi="150">P_{1}=p_{1, 1} = \binom{12}{0}p_{1, 0} + \binom{2}{1}p_{0, 0} = 2p_{0, 0} = 2</tex>.
:<tex dpi="150">P_{2}=p_{2, 2} = \binom{0}{0} p_{2, 1} + \binom{0}{1}p_{0, 1} = \binom{2}{0}p_{2, 0} + \binom{2}{1}p_{1, 0} + \binom{2}{2}p_{0, 0}= p_{0, 0} = 1</tex>.
:<tex dpi="150">{P_{3}=p_{3, 3} = \binom{0}{0}p_{3, 2} + \binom{0}{1} p_{0, 2} = \binom{0}{0}p_{3, 1} + \binom{0}{1} p_{0, 1} = \binom{2}{0}p_{3, 0} + \binom{2}{1}p_{2, 0} + \binom{2}{2} p_{1, 0} + \binom{2}{3} p_{0, 0}= 0}</tex>.
:<tex dpi="150">\{0\}, \{1\}</tex>
:<tex dpi="150">\{0, 1\}</tex>
===Количество разбиений на слагаемые===
Пусть <tex dpi="130">A=\mathbb{N}</tex>, <tex dpi="130">P=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 1\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда,
:<tex dpi="150">P_{n}=p_{n, n}</tex>, где <tex tex dpi="150">p_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} p_{n-ik, k-1} = p_{n, k-1} + p_{n - k, k}</tex>, что, как несложно заметить, соответствует формуле, полученной методом [[Нахождение количества разбиений числа на слагаемые#Алгоритм за O(N^2)|динамического программирования]].
===Количество MSet из элементов 0 и 1===
Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex dpi="130">M=MSet(A)</tex> {{---}} множество всех множеств мультимножеств из <tex dpi="130">A</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>, <tex dpi="130">w_{0} = 1</tex>.
:Тогда, <tex dpi="150">M_{n}=m_{n, n}</tex>, где <tex dpi="150">m_{n, k}=\sum\limits_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i}m_{n-ik, k-1}</tex>
:<tex dpi="150">M_{0}=m_{0, 0} = 1</tex>.
