3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ what do u want? exact answer? asymptotics? if asymptotics, is, e.g., $k$ fixed and $n \to \infty$? $\endgroup$ Sep 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$ Sep 18, 2022 at 5:04

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
2
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.