The size of unions of some families of sets Consider the class $\mathcal{F}_n^m$ of families of sets consisting of $n$ sets $s_i \subset \{1,2,\dots,n\cdot m\}$ of size $m$. For a family of sets $F \in \mathcal{F}_n^m$, $F = \{s_1,\dots,s_n\}$ with $|s_i| = m$, the size $\Sigma(F)$ of its union $\bigcup_{i=1,\dots,n} s_i$ is some number of which the  upper bound $\Sigma_{\textsf{max}}^{(nm)} = n\cdot m$ and the lower bound $\Sigma_{\textsf{min}}^{(nm)} = \min\{s\ |\  {s\choose m}\geq n\}$ are known.
I experimentally found out, that for $\mathcal{F}_4^4$, i.e. for 4-element sets of 4-element sets, the expected number $\Sigma_{\textsf{exp}}^{(44)}$ is approx. 10.936 and the sharp lower bound $\Sigma_{\textsf{min}}^{(44)}$ is 5. Furthermore I got this distribution of union sizes for some 10 million random samples taken from the universal set $\{1,2,\dots,16\}$.

My questions are:

*

*By which combinatorial considerations can the expected number $\Sigma_{\textsf{exp}}^{(nm)}$ of the union size for families of sets in $\mathcal{F}_n^m$ be calculated, giving 10.936 for the case $n=m=4$?


*What kind of distribution is the one I observed? It's obviously not a binomial distribution (because it's asymmetric), but it might be a Poisson distribution? How would I prove or check this?
 A: For the first question. The probability that you pick a configuration is given by
$$\frac{4!}{\binom{16}{4}^4},$$
Then to compute the expected value you need
$$P(|\Sigma|=k)=\frac{4!\binom{16}{k}}{\binom{16}{4}^4}\sum _{i=0}^k\frac{(-1)^i}{4!}\binom{k}{i}\binom{k-i}{4}^4=\frac{\binom{16}{k}}{\binom{16}{4}^4}\sum _{i=0}^k(-1)^i\binom{k}{i}\binom{k-i}{4}^4,$$
this because you pick the elements in the union in $\binom{16}{k}$ ways and then you need to use them all, so inclusion-exclusion gives you the other expression. If you do $$\mathbb{E}[|\Sigma|]=\sum _{i=0}^{16}k\cdot P(|\Sigma|=k)=10.9375,$$
you get the number you said.
A: For an element $x\in[nm]$, the probability that $x$ is not picked in a random set $S\subseteq [nm]$ of size $m$ is $\frac{nm-m}{nm}=1-1/n$. Therefore by independence, for a random collection of $n$ such sets, the probability that $x$ is not in their union is $(1-1/n)^n$. By linearity of expectation,
$$\Sigma_{\text{exp}}^{n,m}=\left(1-\left(1-\frac{1}{n}\right)^n\right)nm.$$
I do not think the distribution is a standard one, but you can probably obtain additional information about it.
