13 514
правок
Изменения
→Комбинаторный анализ и теория графов
==== Основные комбинаторные числа ====
Число '''подмножеств''' множества = 2<sup>|M|</sup>.
[[rupedia:Размещение|Число '''размещений''']] элементов из n по k = (n)<sub>k</sub> (убывающий факториал).
Число '''перестановок''' n элементов = n!.
e = <m>lim(1+\frac{1}{n})^n</m>
[[rupedia:Сочетание|Число '''сочетаний''']] из n по k, или же биномиальный коэффициент <m>{n \choose k} = C_n^k = \frac{n!}{k!\left(n-k\right)!}</m>.
Число '''сочетаний с повторениями''' из n по k <m>H_n^k = {n+k-1 \choose k}</m>
[[rupedia:Мультиномиальный коэффициент|Число разбиений]] n-элементного множества на множества мощностей <m>n_1, \dots, n_m</m> равняется <m>{n\choose n_1,\ n_2,\ \dots,\ n_m} = \frac{n!}{n_1!n_2!\dots n_m!}</m>.
Число разбиений n-элементного множества на k множеств (число Стирлинга) <m>\Phi(n, k) = \frac{1}{k!}\sum_{n_1+\dots+n_k=n, n_i>0} \frac{n!}{n_1!n_2!\dots n_k!}</m> и число всех разбиений (число Белла) <m>\Phi(n) = \sum_{k=0}^{n} \Phi(n, k) = \sum_0^{n-1}{n-1 \choose i}\Phi(i)</m>
==== Оценки и асимптотики для комбинаторных чисел ====
* '''Т.''' (логарифм факториала) <m>ln n! ~ (n+0.5)ln n</m>
* '''Т.''' (формула Стирлинга) <m>n! ~ a\sqrt{n}n^n e^{-n}</m>
* '''Т.''' (корень квадратный из пи)
* '''Т.''' (число сочетаний)
* '''Т.''' (сумма числа сочетаний)
* '''Т.''' (числа Белла)
==== Графы и сети. Оценки числа графов и сетей различных типов ====
* '''Опр.''' граф, цикл, петля, связный граф, сеть, степень сети, степенная структура сети
* '''Т.''' число графов c h рёбрами без изол.вершин меньше a(bh)<sup>h</sup>, a, b = Const.
* '''Т.''' число укладок деревьев с h рёбрами меньше 4<sup>h</sup>.
* '''Т.''' (Лупанова) число сетей с заданной степ.структурой ≤ c<sup>h</sup>h<sup>(μ-1)h</sup>, c зависит только от числа полюсов, средней степени и числа наборов.
==== Плоские и планарные графы. Формула Эйлера для плоских графов. Необходимые условия планарности в теореме Понтрягина—Куратовского (без доказательства достаточности) ====
==== Экстремальная теория графов. Теорема Турана ====
* Можно также почитать [[rupedia:Теорема Турана]].
* '''Т.''' (Турана) (макс. количество ребёр в графе, не содержащем полного n-вершинного подграфа)
==== Теорема Рамсея ====
* Можно также почитать [[rupedia:Теорема Рамсея]].
* '''Т.''' (Рамсея) («полная неупорядоченность невозможна») для любого набора классов сочетаний r элементов в любом достаточно большом множестве всегда найдётся подмножество, все сочетания r элементов которого будут принадлежать одному классу.
* Условно говоря, если на вечеринке 6 человек, то либо какие-то 3 из них все друг с другом знакомы, либо какие-то 3 из них друг с другом незнакомы.
* Правда «достаточно большое множество» — '''очень большое'''.
== Теория кодирования ==
