# Random covering of a set

Let $$A$$ be a set of $$n$$ elements. Let $$S_1,\dots,S_n$$ be independent $$k$$-element random subsets of $$A$$. What is the probability that $$S_1,\dots, S_n$$ evenly cover $$A$$, i.e. each element of $$A$$ belongs to exactly $$k$$ random subsets?

• what do u want? exact answer? asymptotics? if asymptotics, is, e.g., $k$ fixed and $n \to \infty$? Sep 17, 2022 at 11:04
• It equals $T/{n\choose k}^n$, where $T=T(n, k)$ is the number of $k$-regular labelled bipartite graphs with $n$ vertices in each part. Equivalently, $T$ is the number of $(0,1)$-matrices of size $n\times n$ and row and column sums $k$. Or, if you prefer, $T$ is a coefficient of $\prod x_i^ky_i^k$ in $\prod_{i, j=1}^n (1+x_iy_j)$. Also, $T$ is a coefficient of $\prod x_i^ky_i^{n-k}$ in $\prod_{i, j=1}^n (x_i+y_j)$. Sep 18, 2022 at 5:04

It follows immediately from the special case (with $$m=n$$ and $$s=t=k$$) of Theorem 1 of Canfield and Mckay that the probability -- say $$p_{n,k}$$ -- in question is $$\sim\frac1{\sqrt e}\dfrac{\displaystyle{\binom{n}{k}^n}}{\displaystyle{\binom{n^2}{k n}}} \tag{1}\label{1}$$ if $$n\to\infty$$ and either $$k=o(n^{1/2})$$ or $$k\asymp n-k\asymp n$$. (Indeed, writing $$M_{ij}:=1(j\in S_i)$$ for all $$i$$ and $$j$$ in $$[n]:=\{1,\dots,n\}$$, we have a bijection between the set of all "even" $$k$$-coverings $$(S_1,\dots,S_n)$$ of the set $$[n]$$ and the set of all $$0$$-$$1$$ "incidence" matrices $$M=(M_{ij}\colon(i,j)\in[n]^2)$$ with all row sums and all column sums equal $$k$$.)
According to Conjecture 1 of Canfield and Mckay, \eqref{1} holds uniformly over all $$k\in\{1,\dots,n-1\}$$ as $$n\to\infty$$.
For $$k=2,3,4$$, $$p_{n,k}=C_{n,k}\Big/\binom nk^n,$$ where $$(C_{n,2})$$, $$(C_{n,3})$$, and $$(C_{n,3})$$ are A001499, A001501, and A058528, respectively.
• Thank you very much for your answer. Before asking the question I found out that $C_{n,2} = \frac{n!}{2^n} \mathbb E[(X^2-1)^n]$, where $X \sim \mathcal N(0,1)$. I can't find this formula anywhere in the OEIS page, so perhaps it's unknown. Sep 18, 2022 at 6:28