Изменения

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех последовательностей из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots m\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда '''количество последовательностей''' веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}</tex>.

Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех [[Комбинаторные объекты#Битовые вектора|битовых векторов]], <tex dpi="130">S_{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">SS_{0}=Seq(A)1</tex>, <tex dpi="130">S_{1}=1</tex>.

Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_{0} = 1</tex>. <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех последовательностей из данных деревьев. <tex dpi="130">S_{n}</tex> {{---}} количество последовательностей с суммарным количество вершин <tex dpi="130">n</tex>. Чтобы получить дерево из <tex dpi="130">n</tex> вершин достаточно взять <tex dpi="130">1</tex> вершину , и подвесить к ней последовательность деревьев с суммарным количеством вершин <tex dpi="130">n-1</tex>. Тогда:

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=PSet(A)</tex> {{---}} множество всех множеств составленных из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots k\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда '''количество множеств''' суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} s_{n-ik, k-1}</tex> {{---}} количество таких множеств, что они содержат объекты, вес которых не больше чем <tex dpi="130">k</tex>.

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">S=MSet(A)</tex> {{---}} множество всех мультимножеств из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots k\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда '''количество мультимножеств''' из объектов суммарного веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} s_{n-ik, k-1}</tex> {{---}} количество таких мультимножеств, что они содержат объекты, вес которых не больше чем <tex dpi="130">k</tex>.

Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_{0} = 1</tex>. <tex dpi="130">F=MSet(T)</tex> {{---}} множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. <tex dpi="130">F_{n}=f_{n,n}</tex> {{---}} количество лесов с суммарным количество вершин <tex dpi="130">n</tex>. <tex dpi="130">f_{n, k}</tex> {{---}} количество таких лесов из <tex dpi="130">n</tex> вершин, таких что они деревья в них содержат не более чем <tex dpi="130">k</tex> вершин. Чтобы получить дерево из <tex dpi="130">n</tex> вершин достаточно взять <tex dpi="130">1</tex> вершину и подвесить к ней лес деревьев с суммарным количеством вершин <tex dpi="130">n-1</tex>. Тогда:

<tex dpi="150">b_{n,k}=\sum_{i=1}^{n}w_{i}b_{n-i, k-1}</tex>, при чем причем <tex dpi="150">b_{n,1}=w_{n}</tex>.