Случайные минимальные покрытия множеств

В статье получен ряд новых асимптотических результатов для чисел покрытий $n$-множеств при $n\to\infty$. В частности, показано, что число блоков в случайном покрытии $n$-множества асимптотически нормально с параметрами $(2^{n-1}-1/2,2^{n/2-1})$. Получены асимптотические формулы для числа минимальных покрытий $n$-множества, имеющие различный вид в зависимости от того, является « четным или нечетным. Показано, что число блоков при $n\to\infty$ в случайном минимальном покрытии имеет нестандартное дискретное распределение со средним значением $n/2$ и конечной дисперсией. Вид дискретного распределения зависит от того, по какой из последовательностей чисел, четных или нечетных, $n$ стремится к бесконечности. Такое же предельное распределение имеет и число однократно покрытых элементов. Дается алгоритм для установления соответствия между определенными классами разбиений $n$-множества и минимальными покрытиями.