Изменения

Пусть <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 </tex> до <tex dpi="130">m\}</tex>. Мы считаем что нет объектов веса <tex dpi="130"">0</tex>, так как в противном случае существует бесконечное количество последовательностей любого веса. Тогда , '''количество последовательностей''' веса <tex dpi="130">n</tex> можно вычислить как <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-i}</tex>. Причем <tex dpi="150"">S_{0} = 1</tex>, так как есть единственный способ составить пустую последовательность.|proof=Докажем по индукции. '''База <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> и ни к какой последовательности меньшего веса мы не добавляем один и тот де элемент дважды.

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">SP=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">n</tex> можно вычислить как <tex dpi="150">S_P_{n}=s_p_{n, n}</tex>, где <tex dpi="150">s_p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}}{i} s_p_{n-ik, k-1}</tex> {{---}} количество таких множеств, что они содержат объекты, вес которых не больше чем <tex dpi="130">k</tex>.

Пусть <tex dpi="130">A=\{0, 1\}</tex>, <tex>SP=PSet(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">S_P_{n}=s_p_{n, n}</tex>, где <tex tex dpi="150">s_p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_p_{n-ik, k-1}</tex>.

:<tex dpi="150">S_P_{0}=s_p_{0, 0} = 1</tex>.:<tex dpi="150">S_P_{1}=s_p_{1, 1} = s_p_{1, 0} + 2s_2p_{0, 0} = 2s_2p_{0, 0} = 2</tex>.:<tex dpi="150">S_P_{2}=s_p_{2, 2} = s_p_{2, 1} + 0 \cdot s_p_{0, 1} = s_p_{2, 0} + 2s_2p_{1, 0} + s_p_{0, 0}= s_p_{0, 0} = 1</tex>.:<tex dpi="150">{S_P_{3}=s_p_{3, 3} = s_p_{3, 2} + 0 \cdot s_p_{0, 2} = s_p_{3, 1} + 0 \cdot s_p_{0, 1} = s_p_{3, 0} + 2s_2p_{2, 0} + 0 \cdot s_p_{1, 0} + 0 \cdot s_p_{0, 0}= 0}</tex>.:Для <tex dpi="150">n > 2</tex>, <tex dpi="150">S_P_{n} = 0</tex> .

Пусть <tex dpi="130">A=\mathbb{N}</tex>, <tex dpi="130">SP=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 1\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда, :<tex dpi="150">S_P_{n}=s_p_{n, n}</tex>, где <tex tex dpi="150">s_p_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_p_{n-ik, k-1} = s_p_{n, k-1} + s_p_{n - k, k}</tex>, что, как не сложно заметить, соответствует формуле, полученной методом [[Нахождение количества разбиений числа на слагаемые#Алгоритм за O(N^2)|динамического программирования]].

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">SM=MSet(A)</tex> {{---}} множество всех мультимножеств <ref>[[wikipedia:Multiset|Wikipedia {{---}} Мультимножества]]</ref> из элементов <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">n</tex> можно вычислить как <tex dpi="150">S_M_{n}=s_m_{n, n}</tex>, где <tex dpi="150">s_m_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{w_{k}+i-1}{i} s_m_{n-ik, k-1}</tex> {{---}} количество таких мультимножеств, что они содержат объекты, вес которых не больше чем <tex dpi="130">k</tex>.

:Тогда, <tex dpi="150">S_M_{n}=s_m_{n, n}</tex>, где <tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}</tex>:<tex dpi="150">S_M_{0}=s_m_{0, 0} = 1</tex>.:<tex dpi="150">S_M_{1}=s_m_{1, 1} = s_m_{1, 0} + 2s_2m_{0, 0} = 2s_2m_{0, 0} = 2</tex>.:<tex dpi="150">S_M_{2}=s_m_{2, 2} = s_m_{2, 1} + 0 \cdot s_m_{0, 1} = s_m_{2, 0} + 2s_2m_{1, 0} + 3s_3m_{0, 0}= 3s_3m_{0, 0} = 3</tex>.:<tex dpi="150">S_M_{3}=s_m_{3, 3} = s_m_{3, 2} + 0 \cdot s_m_{0, 2} = s_m_{3, 1} + 0 \cdot s_m_{0, 1} = s_m_{3, 0} + 2s_2m_{2, 0} + 3s_3m_{1, 0} + 4s_4m_{0, 0}= 4s_4m_{0, 0} = 4</tex>.

:<tex dpi="150">{S_M_{n}=s_m_{n, n} = s_m_{n, n-1} + 0 \cdot s_m_{0, n-1} = s_m_{n, n-2} + 0 \cdot s_m_{0, n-2} = \ldots = s_m_{n, 0} + 2s_2m_{n - 1, 0} + \ldots + ns_nm_{1, 0} + (n+1) s_m_{0,0} = (n + 1) s_m_{0,0} = n+1}</tex>.

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

Пусть <tex dpi="130">T_{n}</tex> {{---}} количество таких деревьев с <tex dpi="130">n</tex> вершинами, <tex dpi="130">T_{0} = 1</tex>. <tex dpi="130">SD=Pair(T, T)</tex> {{---}} множество всех пар из данных деревьев. Чтобы получить двоичное дерево из <tex dpi="130">n</tex> вершин, достаточно взять <tex dpi="130">1</tex> вершину и подвесить к ней левого и правого сына с суммарным количеством вершин <tex dpi="130">n-1</tex>. Тогда::<tex dpi="150">T_{n}=S_D_{n-1}=\sum_{i=0}^{n-1}T_{i}T_{n-i-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]].

Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{z}\}</tex> {{---}} множество из различных объектов, <tex dpi="130">C=Cycle(A)</tex> {{---}} множество всех циклов <ref>[[wikipedia:Periodic sequence|Wikipedia {{---}} Циклы]]</ref> из элементов <tex dpi="130">A</tex>, <tex dpi="130">W=\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса <tex dpi="130">\{1 \ldots m\}</tex>.