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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ what do u want? exact answer? asymptotics? if asymptotics, is, e.g., $k$ fixed and $n \to \infty$? $\endgroup$– mathworker21Sep 17, 2022 at 11:04
-
1$\begingroup$ 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)$. $\endgroup$– Fedor PetrovSep 18, 2022 at 5:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
A prehistory of this problem is discussed in Canfield and Mckay as well.
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.
answered Sep 18, 2022 at 1:55
-
$\begingroup$ 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. $\endgroup$ Sep 18, 2022 at 6:28
-
2$\begingroup$ @Pluviophile : A nice connection. You may want to contribute this observation to the OEIS -- oeis.org/Submit.html $\endgroup$ Sep 18, 2022 at 13:17