Вероя́тностная комбинато́рика, раздел дискретной математики, в котором методы теории вероятностей применяются для изучения комбинаторных объектов. В вероятностной комбинаторике рассматриваются также перечислительные задачи комбинаторики и вопросы существования комбинаторных объектов с заданными характеристиками.

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

Первые шаги вероятностной комбинаторики связаны с развитием в середине 17 в. элементарной теории вероятностей, когда комбинаторные методы использовались для подсчёта различных вероятностей в азартных играх. Первые результаты исследований в вероятностной комбинаторике с использованием современных методов теории вероятностей появились в работах В. Л. Гончарова (1896–1955) (см. Гончаров. 1942; 1944), в которых получены основные результаты о предельном поведении случайных величин, связанных с цикловой структурой случайных подстановок при возрастании их степеней. Случайная подстановка степени $n$ – это подстановка, выбираемая с равными вероятностями из множества всех подстановок степени $n$. С использованием хорошо развитых в теории вероятностей методов доказательства предельных теорем (метода производящих функций, метода характеристических функций, а также метода моментов) Гончаровым было доказано, что число циклов длины $r$ в случайной подстановке степени $n$ имеет в пределе при $n→∞$ распределение Пуассона с параметром $1/r$, распределение общего числа циклов сближается с нормальным распределением с параметрами $(\ln n, \ln n)$, найдено предельное распределение максимальной длины цикла случайной подстановки. Впоследствии эти результаты во многом служили образцом для изучения различных классов случайных комбинаторных объектов, в том числе случайных размещений, случайных разбиений целых чисел на целочисленные слагаемые, различных классов случайных графов (случайных отображений, лесов, деревьев), случайных матриц, систем случайных уравнений, случайных автоматов, случайных алгоритмов.

При изучении случайных графов венгерскими математиками П. Эрдёшем и А. Реньи был обнаружен (1960) неожиданный эффект, который по аналогии с подобным эффектом в поведении систем частиц в статистической физике трактуется как фазовый переход. Пусть $\mathscr{G}_{n,T}$ – случайный граф с $n$ вершинами, который получается в результате размещения $T$ рёбер, каждое из которых независимо от размещения остальных рёбер занимает любое из $n(n-1)/2$ возможных мест с равными вероятностями. Пусть $2T/n→λ$ при $n, T→∞$. Если $λ < 1$, точнее, если $(1–2T/n)^3n→∞$, то граф $\mathscr{G}_{n,T}$ с вероятностью, стремящейся к единице, состоит из связных компонент, которые являются либо деревьями, либо компонентами, содержащими ровно один цикл. При переходе параметром $2T/n$ значения 1, точнее, в области, где при $n, T→∞$ параметр $(1–2T/n)^3$ стремится к какой-либо постоянной $c$, появляется т. н. гигантская компонента, число вершин в которой асимптотически нормально с математическим ожиданием $α (c)n$, при этом с убыванием параметра $c$ параметр $α(c)$ возрастает. При $(1–2T/n)^3n→–∞$ граф $\mathscr{G}_{n,T}$ с вероятностью, стремящейся к единице, состоит из гигантской компоненты, деревьев и компонент с одним циклом. Такое поведение случайного графа при переходе параметром $2T/n$ значения 1 можно интерпретировать как фазовый переход, или, другими словами, как наличие порогового эффекта в поведении случайного графа. Позднее пороговый эффект был обнаружен в поведении ещё более простых случайных комбинаторных объектов, таких как случайные леса из корневых и некорневых деревьев.

Вероятностный подход используется и для доказательства существования комбинаторных объектов без привлечения конструктивных построений. Простейший вариант этого подхода основан на том, что если математическое ожидание целочисленной неотрицательной случайной величины положительно, то эта случайная величина не равна тождественно нулю. Один из примеров применения вероятностного подхода состоит в следующем.

Пусть $\mathscr{G}_n(p)$ – случайный граф с $n$ вершинами, в котором каждая пара вершин независимо от остальных соединена ребром с вероятностью $p$ (с вероятностью $q$ такого ребра нет, $p+q=1$). В графе $\overline{\mathscr{G}_{n}}(p)$, дополнительном к графу ${\mathscr{G}_{n}(p)}$, пара вершин соединена ребром тогда и только тогда, когда такого ребра нет в ${\mathscr{G}_{n}(p)}$. Пусть $v_n(p, k)$ и $\overline{v}_{n}(p, k)$ – числа полных подграфов с $k$ вершинами в $\mathscr{G}_n(p)$ и $\overline{\mathscr{G}_{n}}(p)$ соответственно. Для математических ожиданий справедливы равенства$$\begin{gathered}\mathsf{M}v_n(p,k)=C_{n}^{k}p^{k(k-1)/2},\\ \mathsf{M}\overline{v}_n(p,k)=\mathsf{M}v_n(q,k)=C_{n}^{k}q^{k(k-1)/2}.\end{gathered}$$Если число $k > \max\{[2\ln n /\ln (1/p)], [ 2 \ln n / \ln(1/q)]\}$, где $C_{n}^{k}$ – биномиальные коэффициенты, $[a]$ – целая часть числа $a$, то $\mathsf{M}v_n(p,k)\to0$ и $\mathsf{M}\overline{v}_n(p,k)\to0$ при $n→∞$. Следствием этих соотношений является то, что для каждого фиксированного $p, 0 < p < 1$, и каждого достаточно большого $n$ существует граф $G_n(p)$ c $n$ вершинами, не содержащий полного подграфа с более чем $2\ln n/\ln(1/p)$ вершинами, дополнительный граф $\overline{G}_n(p)$ которого не содержит полного подграфа с более чем $\ln n/ \ln(1/q)$ вершинами.

Значительное внимание в вероятностной комбинаторике уделяется генерации последовательностей случайных чисел, генерации случайных комбинаторных объектов, таких как случайные подстановки, а также вероятностному анализу алгоритмов и построению вероятностных алгоритмов, включающих в себя датчики случайных чисел.