Редактирование: Конструирование комбинаторных объектов и их подсчёт

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 71: Строка 71:
 
Пусть <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)|динамического программирования]].
 +
 +
==Количество связных графов==
 +
{{Определение
 +
|definition=
 +
<tex dpi="130">CONN_{n}</tex> - количество связных графов порядка <tex dpi="130">n</tex>.
 +
}}
 +
 +
{{Лемма
 +
|statement=
 +
<tex dpi="130">G_{n}=2^{\binom{n}{2}}</tex>, {{---}} количество помеченных графов.
 +
}}
 +
 +
{{Утверждение
 +
|statement=
 +
<tex dpi="150">CONN_{n}=G_{n} - \frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}2^{\binom{n-k}{2}}CONN_{k}</tex>, {{---}} количество связных графов порядка n.
 +
|proof=
 +
Пусть <tex dpi="150">X</tex> {{---}} количество '''несвязных графов'''. Тогда количество '''связных графов''' равно <tex dpi="150">G_{n}-X</tex>.
 +
Пусть <tex dpi="150">Y</tex> {{---}} количество '''количество корневых несвязных графов'''. Тогда количество '''несвязных графов''' равно <tex dpi="150">\dfrac{Y}{n}</tex>.
 +
 +
Заметим, что, так как граф является '''несвязным''', то в нём найдётся компонента связности, внутри которой лежит корневая вершина <ref>[[wikipedia:Rooted_graph | Wikipedia {{---}} Корневой граф]]</ref>, а остальной граф будет представлять собой одну или более компонент связности.
 +
 +
Переберем количество вершин в компоненте связности, содержащей корневую вершину. <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">CONN_{k}</tex>.
 +
 +
В-третьих, оставшийся граф из <tex dpi="150">n-k</tex> вершин является произвольным графом, поэтому он даёт множитель <tex dpi="150">G_{n-k}</tex>.
 +
 +
В-четвертых, количество способов выделить корневую вершину в компоненте связности из <tex dpi="150">k</tex> вершин равно <tex dpi="150">k</tex>.
 +
 +
Итого, при фиксированном <tex dpi="150">k</tex> количество корневых несвязных графов равно:
 +
 +
<tex dpi="150">k\binom{n}{k}CONN_{k}G_{n-k}</tex>.
 +
 +
Значит, количество несвязных графов с <tex dpi="150">n</tex> вершинами равно:
 +
 +
<tex dpi="150">\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}</tex>
 +
 +
Наконец, искомое количество связных графов равно:
 +
 +
<tex dpi="150">CONN_{n}=G_{n}-\frac{1}{n}\sum\limits_{k=1}^{n-1}k\binom{n}{k}CONN_{k}G_{n-k}</tex>
 +
}}
 +
  
 
==Мультимножества (MSet)==
 
==Мультимножества (MSet)==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)