Конструирование комбинаторных объектов и их подсчёт — различия между версиями
Scuuter (обсуждение | вклад) м |
м (rollbackEdits.php mass rollback) |
||
(не показано 12 промежуточных версий 10 участников) | |||
Строка 4: | Строка 4: | ||
}} | }} | ||
− | В дальнейшем, будем считать что нет объектов веса <tex dpi="130"">0</tex>, так как в противном случае существует бесконечное количество рассматриваемых комбинаторных объектов любого веса и подсчет теряет смысл, или подсчет сводится к рассматриваемому случаю. Отведем данный вес под пустое множество(то есть <tex dpi="130">w_{0}=1</tex>). | + | В дальнейшем, будем считать что нет объектов веса <tex dpi="130"">0</tex>, так как в противном случае существует бесконечное количество рассматриваемых комбинаторных объектов любого веса и подсчет теряет смысл, или подсчет сводится к рассматриваемому случаю. Отведем данный вес под пустое множество (то есть <tex dpi="130">w_{0}=1</tex>). |
Строка 38: | Строка 38: | ||
Тогда, <tex dpi="150">S_{n}=\sum\limits_{i=1}^{n} w_{i} S_{n-i}=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">S_{n}=\sum\limits_{i=1}^{n} w_{i} S_{n-i}=S_{n-1}+S_{n-2}=F_{n}</tex>, где <tex dpi="150">F_{n}</tex> {{---}} <tex>n</tex>-ое число Фибоначчи <ref>[[wikipedia:Fibonacci number|Wikipedia {{---}} Числа Фибоначчи]]</ref>. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Множества (PSet)== | ==Множества (PSet)== | ||
Строка 67: | Строка 59: | ||
:<tex dpi="150">P_{0}=p_{0, 0} = 1</tex>. | :<tex dpi="150">P_{0}=p_{0, 0} = 1</tex>. | ||
− | :<tex dpi="150">P_{1}=p_{1, 1} = \binom{ | + | :<tex dpi="150">P_{1}=p_{1, 1} = \binom{2}{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_{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">{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>. | ||
Строка 75: | Строка 67: | ||
:<tex dpi="150">\{0\}, \{1\}</tex> | :<tex dpi="150">\{0\}, \{1\}</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">A=\mathbb{N}</tex>, <tex dpi="130">P=PSet(A)</tex> {{---}} множество всех [[Нахождение количества разбиений числа на слагаемые|разбиений на слагаемые]], <tex dpi="130">W=\{1 \ldots 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)|динамического программирования]]. | :<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)== | ==Мультимножества (MSet)== | ||
Строка 113: | Строка 103: | ||
:<tex dpi="150">{M_{n}=m_{n, n} = \binom{0}{0}m_{n, n-1} + \binom{0}{1} m_{0, n-1} = \binom{0}{0}m_{n, n-2} + \binom{0}{1} m_{0, n-2} = \ldots = \binom{1}{0}m_{n, 0} + \binom{2}{1}m_{n - 1, 0} + \ldots + \binom{n}{n-1}m_{1, 0} + \binom{n+1}{n} m_{0,0} = (n + 1) m_{0,0} = n+1}</tex>. | :<tex dpi="150">{M_{n}=m_{n, n} = \binom{0}{0}m_{n, n-1} + \binom{0}{1} m_{0, n-1} = \binom{0}{0}m_{n, n-2} + \binom{0}{1} m_{0, n-2} = \ldots = \binom{1}{0}m_{n, 0} + \binom{2}{1}m_{n - 1, 0} + \ldots + \binom{n}{n-1}m_{1, 0} + \binom{n+1}{n} m_{0,0} = (n + 1) m_{0,0} = n+1}</tex>. | ||
− | === | + | ==Помеченные унициклические графы== |
− | + | ||
− | + | {{Определение | |
− | + | |definition=<tex dpi="130">Унициклическим</tex> называется связный граф, содержащий один простой цикл и не содержащий петель и кратных рёбер. <tex dpi="150">U_{n}</tex> {{---}} '''количество унициклических графов''' из <tex dpi="130">n</tex> вершин, <tex dpi="130">n > 2</tex>. | |
− | + | }} | |
+ | |||
+ | {{Утверждение | ||
+ | |statement=<tex dpi="150">U_{n}=\sum\limits_{r=3}^{n}\binom{n}{r}\frac{r!}{2}n^{n-r-1}</tex>. | ||
+ | |proof=Для всех <tex dpi="130">r \in [3;n]</tex> найдем число способов выбрать вершины для цикла длины <tex dpi="130">r</tex>, их количество равняется <tex dpi="130">\binom{n}{r}</tex>. Найдём число способов упорядочить выбранные вершины: заметим что каждый цикл длины <tex dpi="130">r</tex> порождается <tex dpi="130">2r</tex> способами (у каждой перестановки существует <tex dpi="130">r - 1</tex> циклический сдвиг и одно зеркальное представление), поэтому существует <tex dpi="130">\frac{r!}{2r} = \frac{(r-1)!}{2}</tex> различных циклов. Найдём количество способов достроить полученный цикл до связного унициклического графа. Заметим, что при удалениии всех ребер цикла граф станет лесом из <tex dpi="130">r</tex> деревьев и <tex dpi="130">n</tex> вершин. Используя [[Коды Прюфера|кодирование Прюфера]], получим, что количество таких лесов равно <tex dpi="130">r {n}^{n-r-1}</tex>. Нахождение количества таких лесов аналогично нахождению [[Количество помеченных деревьев|количества помеченных деревьев]]. Значит, количество унициклических графов порядка <tex dpi="130">n</tex> равно <tex dpi="130">U_{n}=\sum\limits_{r=3}^{n}\binom{n}{r}\frac{r!}{2}n^{n-r-1}</tex>. | ||
+ | }} | ||
+ | |||
+ | ==Связные графы== | ||
+ | {{Определение | ||
+ | |definition= | ||
+ | <tex dpi="130">CONN_{n}</tex> - количество связных графов с <tex dpi="130">n</tex> вершинами. | ||
+ | }} | ||
+ | |||
+ | {{Лемма | ||
+ | |statement= | ||
+ | <tex dpi="150">G_{n} = 2^{\binom{n}{2}}</tex>, где <tex dpi="150">G_{n}</tex> {{---}} количество помеченных графов с <tex dpi="130">n</tex> вершинами. | ||
+ | }} | ||
+ | |||
+ | {{Утверждение | ||
+ | |statement= | ||
+ | <tex dpi="150">CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex>, {{---}} количество связных графов с <tex dpi="130">n</tex> вершинами. | ||
+ | |proof= | ||
+ | |||
+ | Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что <tex dpi="150">CONN_{n}=G_{n}-X_{n}</tex>, где <tex dpi="150">X_{n}</tex> {{---}} количество несвязных графов. Также <tex dpi="150">X_{n}=\dfrac{Y_{n}}{n}</tex>, где <tex dpi="150">Y_{n}</tex> {{---}} количество корневых<ref>[[wikipedia:Rooted_graph | Wikipedia {{---}} Корневой граф]]</ref> несвязных графов. | ||
− | + | Вычислим <tex dpi="150">Y_{n}</tex>. Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. <tex dpi="150">(k=1\ldots n-1)</tex>. Для каждого <tex dpi="150">k</tex> посчитаем количество таких графов. Количество способов выбрать <tex dpi="150">k</tex> вершин из <tex dpi="150">n</tex> равно <tex dpi="150">\binom{n}{k}</tex>. Оставшийся граф является произвольным, таким образом, количество помеченных графов в нем равно <tex dpi="150">G_{n-k}</tex>. Количество способов выделить корневую вершину в компоненте связности из <tex dpi="150">k</tex> вершин равно <tex dpi="150">k</tex>. Также количество связных графов в компоненте связности с корневой вершиной равно <tex dpi="150">CONN_{k}</tex>. | |
− | + | Итого, для фиксированного <tex dpi="150">k</tex> количество корневых несвязных графов равно | |
− | + | ||
+ | <tex dpi="150">Y_{n}=k\binom{n}{k}CONN_{k}G_{n-k}</tex>. | ||
+ | |||
+ | Значит, количество несвязных графов с <tex dpi="150">n</tex> вершинами равно | ||
+ | |||
+ | <tex dpi="150">X_{n}=\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}</tex> | ||
+ | |||
+ | Таким образом, количество связных графов с <tex dpi="130">n</tex> вершинами равно | ||
+ | |||
+ | <tex dpi="150">CONN_{n}=G_{n}-\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}G_{n-k}CONN_{k}</tex> | ||
+ | }} | ||
Строка 136: | Строка 159: | ||
|proof=Чтобы составить пару веса <tex dpi="130">n</tex> нужно взять один элемент веса <tex dpi="130">0 \leqslant i \leqslant n</tex> из <tex dpi="130">A</tex> и элемент веса <tex dpi="130">n-i</tex> из <tex dpi="130">B</tex> , что полностью соответствует данной формуле. | |proof=Чтобы составить пару веса <tex dpi="130">n</tex> нужно взять один элемент веса <tex dpi="130">0 \leqslant i \leqslant n</tex> из <tex dpi="130">A</tex> и элемент веса <tex dpi="130">n-i</tex> из <tex dpi="130">B</tex> , что полностью соответствует данной формуле. | ||
}} | }} | ||
− | |||
− | |||
− | |||
− | |||
==Циклы (Cycle)== | ==Циклы (Cycle)== | ||
Строка 250: | Строка 269: | ||
*[[Числа Каталана]] | *[[Числа Каталана]] | ||
*[[Генерация комбинаторных объектов в лексикографическом порядке]] | *[[Генерация комбинаторных объектов в лексикографическом порядке]] | ||
+ | *[[Подсчет деревьев]] | ||
+ | *[[Метод производящих функций]] | ||
==Примeчания== | ==Примeчания== |
Текущая версия на 19:15, 4 сентября 2022
Определение: |
, — множества из различных объектов. — количество объектов веса от до из , а — соответственно для . |
В дальнейшем, будем считать что нет объектов веса , так как в противном случае существует бесконечное количество рассматриваемых комбинаторных объектов любого веса и подсчет теряет смысл, или подсчет сводится к рассматриваемому случаю. Отведем данный вес под пустое множество (то есть ).
Последовательности (Seq)
Определение: |
— множество всех последовательностей из элементов . — количество последовательностей веса . |
Утверждение: |
. Причем . |
, так как есть единственный способ составить пустую последовательность. Докажем по индукции. База .
Переход.
|
Подсчет битовых векторов длины
Пусть битовых векторов.
, — множество всехТогда,
.Подсчет Seq из маленьких и больших элементов
Пусть
, , — множество всех последовательностей из маленьких и больших элементов, .Тогда, [1].
, где — -ое число ФибоначчиМножества (PSet)
Определение: |
— множество всех множеств, составленных из элементов . — количество множеств суммарного веса . |
Утверждение: |
, где — количество таких множеств, которые содержат объекты, вес которых не больше чем . Причем , а , . |
Изначально у нас есть только пустое множество веса , так как не набирать никакой вес есть один способ, а , , так как нельзя набрать положительный вес из ничего. . Рассмотрим очередной этап вычисления . Для данных и у нас уже имеется множество, которое необходимо дополнить. Мы можем сделать это добавляя от до элементов веса (при условии, что столько различных элементов имеется) в данное множество. Выбрать нужное количество элементов можно с помощью сочетаний. Следовательно, у нас образуется новые множества, которые будет необходимо дополнить элементами веса меньше (чтобы избежать повторений) суммарного веса , где — количество элементов веса которое мы добавили в данное множество. Довольно легко заметить, что данные операции полностью соответствуют описанной выше формуле. |
Количество PSet из элементов 0 и 1
Пусть
, — множество всех множеств из , . Тогда , где .- .
- .
- .
- .
- Для , .
Количество разбиений на слагаемые
Пусть разбиений на слагаемые, . Тогда,
, — множество всех- динамического программирования. , где , что, как несложно заметить, соответствует формуле, полученной методом
Мультимножества (MSet)
Определение: |
[2] из элементов . — количество мультимножеств из объектов суммарного веса . | — множество всех мультимножеств
Утверждение: |
, где — количество таких мультимножеств, которые содержат объекты, вес которых не больше чем . Причем , а , . |
Рассуждения аналогичны рассуждениям , так как не набирать никакой вес есть один способ, а , , так как нельзя набрать положительный вес из ничего. , однако теперь мы можем брать один и тот же элемент несколько раз. То есть для подсчета вместо обычных сочетаний нужно использовать сочетания с повторениями. |
Количество MSet из элементов 0 и 1
Пусть
, — множество всех мультимножеств из , .- Тогда, , где
- .
- .
- .
- .
- .
Помеченные унициклические графы
Определение: |
называется связный граф, содержащий один простой цикл и не содержащий петель и кратных рёбер. — количество унициклических графов из вершин, . |
Утверждение: |
. |
Для всех кодирование Прюфера, получим, что количество таких лесов равно . Нахождение количества таких лесов аналогично нахождению количества помеченных деревьев. Значит, количество унициклических графов порядка равно . | найдем число способов выбрать вершины для цикла длины , их количество равняется . Найдём число способов упорядочить выбранные вершины: заметим что каждый цикл длины порождается способами (у каждой перестановки существует циклический сдвиг и одно зеркальное представление), поэтому существует различных циклов. Найдём количество способов достроить полученный цикл до связного унициклического графа. Заметим, что при удалениии всех ребер цикла граф станет лесом из деревьев и вершин. Используя
Связные графы
Определение: |
- количество связных графов с вершинами. |
Лемма: |
, где — количество помеченных графов с вершинами. |
Утверждение: |
, — количество связных графов с вершинами. |
Рассмотрим соотношение количества связных и несвязных графов. Очевидно, что [3] несвязных графов. , где — количество несвязных графов. Также , где — количество корневыхВычислим . Заметим, что, так как граф является несвязным, то в нём найдётся компонента связности, внутри которой лежит корневая вершина, а остальной граф будет представлять собой одну или более компонент связности. Переберем количество вершин в компоненте связности, содержащей корневую вершину. . Для каждого посчитаем количество таких графов. Количество способов выбрать вершин из равно . Оставшийся граф является произвольным, таким образом, количество помеченных графов в нем равно . Количество способов выделить корневую вершину в компоненте связности из вершин равно . Также количество связных графов в компоненте связности с корневой вершиной равно .Итого, для фиксированного количество корневых несвязных графов равно. Значит, количество несвязных графов с вершинами равно
Таким образом, количество связных графов с вершинами равно |
Пары (Pair)
Определение: |
— множество всех пар объектов, составленных из элементов и . — количество пар из объектов суммарного веса . |
Утверждение: |
. |
Чтобы составить пару веса | нужно взять один элемент веса из и элемент веса из , что полностью соответствует данной формуле.
Циклы (Cycle)
Определение: |
[4] из элементов . — количество циклов веса . | — множество всех циклов
Утверждение: |
, где , — количество циклов веса длины , а — количество стабилизаторов для циклического сдвига на . |
Очевидно, что длина цикла веса лемме Бёрнсайда. | может быть от до . Посмотрим сколько существует циклов каждой длины. Это можно сделать по
Лемма: |
Найдем в общем случае. |
Доказательство: |
Пусть наибольший общий делитель. Заметим, что в -ой перестановке на -ой позиции стоит элемент . Также, заметим, что элемент переходит в элемент , где . Из этого следует, что длина цикла для -ой перестановки равна , где — наименьшее общее кратное. —Также заметим, что если вес нельзя равномерно распределить по всей длине цикла, то стабилизатор равен .
Где — число способов упорядочить набор из элементов суммарного веса и , причем . |
Задача об ожерельях
Решим данным способом задачу об ожерельях. Пусть необходимый вес — это количество бусинок, а — количество цветов. Причем каждая бусинка весит . То есть .
так как невозможно набрать вес менее, чем бусинами при весе бусин .
. Поскольку все бусины имеют одинаковый вес , то
В итоге,
.Метод производящих функций
Такие большие группы часто анализируют с помощью производящих функций. Один из популярных методов — метод символов [5]. Он использует внутреннюю структуру объектов для получения производящих функций. В случае непомеченных объектов, как и в анализе в нашей статье, считается, что нет объектов нулевого веса. Иногда для удобства их добавляют, чтобы показать наличие одного пустого множества. При непомеченных объектах рассмотренные классы имеют следующие производящие функции:
функция Эйлера. | , где —
---|
Однако порой некоторые комбинаторные классы удобнее обозначать как помеченные. Например, — помеченные графы. С помеченными объектами используется экспоненциальная производящая функция [6]. В данном случае для некоторых рассмотренных классов используются следующие производящие функции:
. |
---|
Ограниченные конструкции
Иногда в анализе необходимо ввести ограничение на количество компонентов. Такой случай обозначается нижним коэффициентом (например,
— компонентов).Непосредственной формулой для производящих функций является диагональ [7] , определяемая как . Тогда имеет место соотношение .
декартова произведенияДиагональная конструкция позволяет получить доступ к классу всех неупорядоченных пар из различных элементов из
, то есть к . Прямое выражение выполняется следующим способом: неупорядоченная пара связана с двумя упорядоченными парами и , кроме тех случаев, когда , то есть когда пара лежит на диагонали декартова произведения. Другими словами, .Это, в свою очередь, означает что
. Таким образом можно выразить . Аналогично для , и :Аналогичные рассуждения можно провести и для больших теорема Пойа.
, однако расчеты быстро становятся сложными. Классический способ исправления таких вопросов —Однако в методе символов предлагается более глобальный подход, основанный на многомерных производящих функциях и использующий ряд Бюрмана-Лагранжа [8]. В общем случае, используя метод символов, производящие функции ограниченных конструкций можно подсчитать следующим способом:
функция Эйлера. | , где —
---|