286
правок
Изменения
Новая страница: «==Последовательности== {{Утверждение |statement= Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> {{---}} множество ...»
==Последовательности==
{{Утверждение
|statement=
Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> {{---}} множество из различных объектов, <tex>S=Seq(A)</tex> {{---}} множество всех последовательностей из элементов <tex>A</tex>, <tex>W=\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса <tex>\{1 \ldots m\}</tex>. Тогда '''количество последовательностей''' веса <tex>n</tex> можно вычислить как <tex>S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}</tex>.
}}
===Подсчет битовых векторов длины <tex>n</tex>===
Пусть <tex>A=\{0, 1\}</tex>, <tex>W=\{2, 0 \ldots 0\}</tex>, <tex>S=Seq(A)</tex> {{---}} множество всех [[Комбинаторные объекты#Битовые вектора|битовых векторов]]. Тогда <tex>S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=2S_{n-1}=2^{n}</tex>.
===Подсчет последовательностей из маленьких и больших элементов===
Пусть <tex>A=\{1, 2\}</tex>, <tex>W=\{1, 1, 0 \ldots 0\}</tex>, <tex>S=Seq(A)</tex> {{---}} множество всех последовательностей из маленьких и больших элементов <tex>S=Seq(A)</tex>. Тогда <tex>S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=S_{n-1}+S_{n-2}=F_{n}</tex>, где <tex>F_{n}</tex> {{---}} <tex>n</tex>-ое число Фибоначчи <ref>[[wikipedia:Fibonacci number|Wikipedia {{---}} Числа Фибоначчи]]</ref>.
===Подсчет подвешенных непомеченных деревьев с порядком на детях===
Пусть <tex>G_{n}</tex> {{---}} количество деревьев с <tex>n</tex> вершинами, <tex>G_{0} = 1</tex>. <tex>S=Seq(A)</tex> {{---}} множество всех последовательностей из деревьев. <tex>S_{n}</tex> {{---}} количество последовательностей с суммарным количество вершин <tex>n</tex>. Чтобы получить дерево из <tex>n</tex> вершин достаточно взять <tex>1</tex> вершину и подвесить к ней последовательность деревьев с суммарным количеством вершин <tex>n-1</tex>. Тогда <tex>S_{n}=\sum_{i=1}^{n} G_{i} S_{n-1}=C_{n}</tex>, где <tex>C_{n}</tex> {{---}} <tex>n</tex>-ое [[Числа Каталана|число Каталана]], а <tex>G_{n}=S_{n-1}</tex>.
[[File:Ordered_Rooted_Trees.png|600px]]
==Множества==
{{Утверждение
|statement=
Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> {{---}} множество из различных объектов, <tex>S=PSet(A)</tex> {{---}} множество всех множеств объектов, составленных из элементов <tex>A</tex>, <tex>W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex>\{1 \ldots k\}</tex>, составленных из элементов <tex>A</tex>, <tex>w_{0} = 1</tex>. Тогда '''количество множеств''' из объектов суммарного веса <tex>n</tex> можно вычислить как <tex dpi="130">S_{n}=s_{n, n}</tex>, где <tex dpi="130">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{n}{w_{k}} s_{n-ik, k-1}</tex> {{---}} количество таких множеств, что они содержат объекты суммарного веса <tex>\leqslant k</tex>.
}}
===Количество множеств из элементов <tex>0</tex> или <tex>1</tex>===
Пусть <tex>A={0, 1}</tex>, <tex>S=PSet(A)</tex> {{---}} множество всех множеств из <tex>A</tex>, <tex>W=\{2, 0 \ldots 0\}</tex>, <tex>w_{0} = 1</tex>. Тогда <tex tex dpi="130">S_{n}=s_{n, n}</tex>, где <tex tex dpi="130">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}</tex>
:<tex dpi="130">S_{0}=s_{0, 0} = 1</tex>
:<tex dpi="130">S_{1}=s_{1, 1} = 2s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex>
:<tex dpi="130">S_{2}=s_{2, 2} = s_{2, 1} + s_{0, 1} = s_{2, 0} + 2s_{1, 0} + s_{0, 0}= s_{0, 0} = 1</tex>
:<tex>\{\}</tex>
:<tex>\{0\}, \{1\}</tex>
:<tex>\{0, 1\}</tex>
===Количество разбиений на слагаемые===
Пусть <tex>A=\mathbb{N}</tex>, <tex>S=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex>W=\{1 \ldots 1\}</tex>, <tex>w_{0} = 1</tex>. Тогда <tex dpi="130">S_{n}=s_{n, n}</tex>, где <tex tex dpi="130">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1} = s_{n, k-1} + s_{n - k, k}</tex>, что, как не сложно заметить, соответсвует формуле, полученной методом динамического программирования.
==Примeчания==
<references/>
{{Утверждение
|statement=
Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> {{---}} множество из различных объектов, <tex>S=Seq(A)</tex> {{---}} множество всех последовательностей из элементов <tex>A</tex>, <tex>W=\{w_{1},w_{2}, \ldots ,w_{m}\}</tex> {{---}} количество объектов веса <tex>\{1 \ldots m\}</tex>. Тогда '''количество последовательностей''' веса <tex>n</tex> можно вычислить как <tex>S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}</tex>.
}}
===Подсчет битовых векторов длины <tex>n</tex>===
Пусть <tex>A=\{0, 1\}</tex>, <tex>W=\{2, 0 \ldots 0\}</tex>, <tex>S=Seq(A)</tex> {{---}} множество всех [[Комбинаторные объекты#Битовые вектора|битовых векторов]]. Тогда <tex>S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=2S_{n-1}=2^{n}</tex>.
===Подсчет последовательностей из маленьких и больших элементов===
Пусть <tex>A=\{1, 2\}</tex>, <tex>W=\{1, 1, 0 \ldots 0\}</tex>, <tex>S=Seq(A)</tex> {{---}} множество всех последовательностей из маленьких и больших элементов <tex>S=Seq(A)</tex>. Тогда <tex>S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=S_{n-1}+S_{n-2}=F_{n}</tex>, где <tex>F_{n}</tex> {{---}} <tex>n</tex>-ое число Фибоначчи <ref>[[wikipedia:Fibonacci number|Wikipedia {{---}} Числа Фибоначчи]]</ref>.
===Подсчет подвешенных непомеченных деревьев с порядком на детях===
Пусть <tex>G_{n}</tex> {{---}} количество деревьев с <tex>n</tex> вершинами, <tex>G_{0} = 1</tex>. <tex>S=Seq(A)</tex> {{---}} множество всех последовательностей из деревьев. <tex>S_{n}</tex> {{---}} количество последовательностей с суммарным количество вершин <tex>n</tex>. Чтобы получить дерево из <tex>n</tex> вершин достаточно взять <tex>1</tex> вершину и подвесить к ней последовательность деревьев с суммарным количеством вершин <tex>n-1</tex>. Тогда <tex>S_{n}=\sum_{i=1}^{n} G_{i} S_{n-1}=C_{n}</tex>, где <tex>C_{n}</tex> {{---}} <tex>n</tex>-ое [[Числа Каталана|число Каталана]], а <tex>G_{n}=S_{n-1}</tex>.
[[File:Ordered_Rooted_Trees.png|600px]]
==Множества==
{{Утверждение
|statement=
Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> {{---}} множество из различных объектов, <tex>S=PSet(A)</tex> {{---}} множество всех множеств объектов, составленных из элементов <tex>A</tex>, <tex>W=\{w_{1},w_{2}, \ldots ,w_{k}\}</tex> {{---}} количество объектов веса <tex>\{1 \ldots k\}</tex>, составленных из элементов <tex>A</tex>, <tex>w_{0} = 1</tex>. Тогда '''количество множеств''' из объектов суммарного веса <tex>n</tex> можно вычислить как <tex dpi="130">S_{n}=s_{n, n}</tex>, где <tex dpi="130">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{n}{w_{k}} s_{n-ik, k-1}</tex> {{---}} количество таких множеств, что они содержат объекты суммарного веса <tex>\leqslant k</tex>.
}}
===Количество множеств из элементов <tex>0</tex> или <tex>1</tex>===
Пусть <tex>A={0, 1}</tex>, <tex>S=PSet(A)</tex> {{---}} множество всех множеств из <tex>A</tex>, <tex>W=\{2, 0 \ldots 0\}</tex>, <tex>w_{0} = 1</tex>. Тогда <tex tex dpi="130">S_{n}=s_{n, n}</tex>, где <tex tex dpi="130">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}</tex>
:<tex dpi="130">S_{0}=s_{0, 0} = 1</tex>
:<tex dpi="130">S_{1}=s_{1, 1} = 2s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex>
:<tex dpi="130">S_{2}=s_{2, 2} = s_{2, 1} + s_{0, 1} = s_{2, 0} + 2s_{1, 0} + s_{0, 0}= s_{0, 0} = 1</tex>
:<tex>\{\}</tex>
:<tex>\{0\}, \{1\}</tex>
:<tex>\{0, 1\}</tex>
===Количество разбиений на слагаемые===
Пусть <tex>A=\mathbb{N}</tex>, <tex>S=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex>W=\{1 \ldots 1\}</tex>, <tex>w_{0} = 1</tex>. Тогда <tex dpi="130">S_{n}=s_{n, n}</tex>, где <tex tex dpi="130">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1} = s_{n, k-1} + s_{n - k, k}</tex>, что, как не сложно заметить, соответсвует формуле, полученной методом динамического программирования.
==Примeчания==
<references/>
