Конструирование комбинаторных объектов и их подсчёт — различия между версиями
Mervap (обсуждение | вклад) |
Mervap (обсуждение | вклад) (+MSet_v_2) |
||
Строка 3: | Строка 3: | ||
{{Утверждение | {{Утверждение | ||
|statement= | |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 dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{n}\}</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">n</tex> можно вычислить как: |
+ | |||
+ | <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}</tex>. | ||
}} | }} | ||
− | ===Подсчет битовых векторов длины <tex>n</tex>=== | + | ===Подсчет битовых векторов длины <tex dpi="150">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 dpi="130">A=\{0, 1\}</tex>, <tex dpi="130">W=\{2, 0 \ldots 0\}</tex>, <tex dpi="130">S=Seq(A)</tex> {{---}} множество всех [[Комбинаторные объекты#Битовые вектора|битовых векторов]]. |
+ | |||
+ | Тогда, <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=2S_{n-1}=2^{n}</tex>. | ||
===Подсчет Seq из маленьких и больших элементов=== | ===Подсчет Seq из маленьких и больших элементов=== | ||
− | Пусть <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 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=Seq(A)</tex>. |
+ | |||
+ | Тогда, <tex dpi="150">S_{n}=\sum_{i=1}^{n} w_{i} S_{n-1}=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>T_{n}</tex> {{---}} количество деревьев с <tex>n</tex> вершинами, <tex>T_{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} T_{i} S_{n-1}=C_{n}</tex>, где <tex>C_{n}</tex> {{---}} <tex>n</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="150">T_{n}=S_{n-1}</tex>. | ||
+ | :<tex dpi="150">S_{n}=\sum_{i=1}^{n} T_{i} S_{n-1}=C_{n}</tex>, где <tex dpi="150">C_{n}</tex> {{---}} <tex dpi="150">n</tex>-ое [[Числа Каталана|число Каталана]] | ||
− | [[File:Ordered_Rooted_Trees.png| | + | [[File:Ordered_Rooted_Trees.png|700px]] |
==Множества== | ==Множества== | ||
Строка 21: | Строка 29: | ||
{{Утверждение | {{Утверждение | ||
|statement= | |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=" | + | Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{n}\}</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">A</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">\leqslant k</tex>. |
}} | }} | ||
− | ===Количество | + | ===Количество PSet из элементов <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 dpi="130">A={0, 1}</tex>, <tex>S=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_{n}=s_{n, n}</tex>, где <tex tex dpi="150">s_{n, k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} s_{n-ik, k-1}</tex> |
− | :<tex dpi=" | + | :<tex dpi="150">S_{0}=s_{0, 0} = 1</tex> |
− | :<tex dpi=" | + | :<tex dpi="150">S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex> |
− | :<tex dpi=" | + | :<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \times s_{0, 1} = s_{2, 0} + 2s_{1, 0} + s_{0, 0}= s_{0, 0} = 1</tex> |
− | :<tex dpi=" | + | :<tex dpi="150">{S_{3}=s_{3, 3} = s_{3, 2} + 0 \times s_{0, 2} = s_{3, 1} + 0 \times s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 0 \times s_{1, 0} + 0 \times s_{0, 0}= 0}</tex> |
− | :Для <tex dpi=" | + | :Для <tex dpi="150">n > 2</tex>, <tex dpi="150">S_{n} = 0</tex> |
− | :<tex>\{\}</tex> | + | :<tex dpi="150">\{\}</tex> |
− | :<tex>\{0\}, \{1\}</tex> | + | :<tex dpi="150">\{0\}, \{1\}</tex> |
− | :<tex>\{0, 1\}</tex> | + | :<tex dpi="150">\{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=" | + | Пусть <tex dpi="130">A=\mathbb{N}</tex>, <tex dpi="130">S=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 1\}</tex>, <tex dpi="130">w_{0} = 1</tex>. Тогда, |
+ | :<tex dpi="150">S_{n}=s_{n, n}</tex>, где <tex tex dpi="150">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>, что, как не сложно заметить, соответствует формуле, полученной методом динамического программирования. | ||
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | Пусть <tex>A=\{a_{1},a_{2}, \ldots ,a_{n}\}</tex> {{---}} множество из различных объектов, <tex>S=MSet(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=" | + | Пусть <tex dpi="130">A=\{a_{1},a_{2}, \ldots ,a_{n}\}</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">A</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>. |
}} | }} | ||
===Количество MSet из элементов <tex>0</tex> или <tex>1</tex>=== | ===Количество MSet из элементов <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 dpi="130">A={0, 1}</tex>, <tex dpi="130">S=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=" | + | :Тогда, <tex dpi="150">S_{n}=s_{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=" | + | :<tex dpi="150">S_{0}=s_{0, 0} = 1</tex> |
− | :<tex dpi=" | + | :<tex dpi="150">S_{1}=s_{1, 1} = s_{1, 0} + 2s_{0, 0} = 2s_{0, 0} = 2</tex> |
− | :<tex dpi=" | + | :<tex dpi="150">S_{2}=s_{2, 2} = s_{2, 1} + 0 \times s_{0, 1} = s_{2, 0} + 2s_{1, 0} + 3s_{0, 0}= 3s_{0, 0} = 3</tex> |
+ | :<tex dpi="150">S_{3}=s_{3, 3} = s_{3, 2} + 0 \times s_{0, 2} = s_{3, 1} + 0 \times s_{0, 1} = s_{3, 0} + 2s_{2, 0} + 3s_{1, 0} + 4s_{0, 0}= 4s_{0, 0} = 4</tex> | ||
+ | |||
+ | :<tex dpi="150">\{\}</tex> | ||
+ | :<tex dpi="150">\{0\}, \{1\}</tex> | ||
+ | :<tex dpi="150">\{0, 0\}, \{0, 1\}, \{1, 1\}</tex> | ||
+ | :<tex dpi="150">\{0, 0, 0\}, \{0, 0, 1\}, \{0, 1, 1\}, \{1, 1, 1\}</tex> | ||
+ | |||
+ | :<tex dpi="150">{S_{n}=s_{n, n} = s_{n, n-1} + 0 \times s_{0, n-1} = s_{n, n-2} + 0 \times s_{0, n-2} = \ldots = s_{n, 0} + 2s_{n - 1, 0} + \ldots + ns_{1, 0} + (n+1) s_{0,0} = (n + 1) s_{0,0} = n+1}</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">T_{n}=F_{n-1}</tex>. | ||
+ | :<tex dpi="150">F_{n}=f_{n, n}</tex>. | ||
+ | :<tex dpi="150">f{n,k}=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{T_{k}+i-1}{i} s_{n-ik, k-1}</tex> | ||
− | + | Количество таких деревьев с <tex dpi="130">n</tex> вершинами образуют последовательность <tex dpi="130"> 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811, 235381, 634847 \ldots</tex> <ref>[http://oeis.org/A000081| Number of unlabeled rooted trees with n node]</ref> | |
− | + | [[File:Rooted_Trees.png|700px]] | |
− | |||
− | |||
− | |||
==Примeчания== | ==Примeчания== | ||
<references/> | <references/> |
Версия 08:27, 26 декабря 2017
Содержание
Последовательности
Утверждение: |
Пусть — множество из различных объектов, — множество всех последовательностей из элементов , — количество объектов веса . Тогда количество последовательностей веса можно вычислить как:
. |
Подсчет битовых векторов длины
Пусть битовых векторов.
, , — множество всехТогда,
.Подсчет Seq из маленьких и больших элементов
Пусть
, , — множество всех последовательностей из маленьких и больших элементов .Тогда, [1].
, где — -ое число ФибоначчиПодсчет подвешенных непомеченных деревьев с порядком на детях
Пусть
— количество таких деревьев с вершинами, . — множество всех последовательностей из данных деревьев. — количество последовательностей с суммарным количество вершин . Чтобы получить дерево из вершин достаточно взять вершину и подвесить к ней последовательность деревьев с суммарным количеством вершин . Тогда:- .
- число Каталана , где — -ое
Множества
Утверждение: |
Пусть — множество из различных объектов, — множество всех множеств объектов, составленных из элементов , — количество объектов веса , составленных из элементов , . Тогда количество множеств из объектов суммарного веса можно вычислить как , где — количество таких множеств, что они содержат объекты суммарного веса . |
Количество PSet из элементов или
Пусть
, — множество всех множеств из , , . Тогда , где- Для ,
Количество разбиений на слагаемые
Пусть разбиений на слагаемые, , . Тогда,
, — множество всех- , где , что, как не сложно заметить, соответствует формуле, полученной методом динамического программирования.
Утверждение: |
Пусть — множество из различных объектов, — множество всех мультимножеств объектов, составленных из элементов , — количество объектов веса , составленных из элементов , . Тогда количество мультимножеств из объектов суммарного веса можно вычислить как , где — количество таких мультимножеств, что они содержат объекты суммарного веса не более . |
Количество MSet из элементов или
Пусть
, — множество всех множеств из , , .- Тогда, , где
Подсчет подвешенных непомеченных деревьев без порядка на детях
Пусть
— количество таких деревьев с вершинами, . — множество всех лесов из данных деревьев, так как лес можно интерпретировать как мультимножество из деревьев. — количество лесов с суммарным количество вершин . — количество лесов из вершин, таких что они содержат не более чем вершин. Чтобы получить дерево из вершин достаточно взять вершину и подвесить к ней лес деревьев с суммарным количеством вершин . Тогда:- .
- .
Количество таких деревьев с [2]