The probability for two random variables to be independent I'm learning probability, and many theorems start by assuming that you have a set of mutually independent random variables. However, The condition that two random variables are independent seems to me quite restrictive. Is it? For example:

Suppose $(\Omega,p)$ is a finite uniform probability space. How many
  pairs of random variables with range in $\{0,1\}$ are
  independent?. Does their proportion to the total number of pairs grow as the size of $\Omega$ grows?

Thanks
 A: A set of random variables $X_1,\ldots,X_n$ taking values in $\{0,1\}$ is independent iff for any subsets $E_1,\ldots,E_n$ of $\{0,1\}$,
$$
\mathbb P(X_1\in E_1,\ldots X_n\in E_n) = \prod_{i=1}^n \mathbb P(X_i\in E_i).
$$
For $n=2$, there are four possible random variables, as $\Omega=\{\omega_1,\omega_2\}$ and $X(\omega_i)$ can be zero or one. In particular the random variables $X(\omega)=0$ and $Y(\omega)=1$ are independent. The random variables $Z(\omega_1)=0, Z(\omega_2)=1$ and $W(\omega_1)=1, W(\omega_2)=0$ are not:$$\mathbb P(\{W=1\}\cap\{Z=1\})=\mathbb P(\{\omega_1\}\cap \{\omega_2\})=\mathbb P(\varnothing) = 0,$$ while
$$
\mathbb P(X=0)\mathbb P(W=1)=\frac12\cdot\frac12=\frac14.
$$ $X$ and $Y$ are also independent with $W$ and $Z$, so of the $\binom 42=6$ pairs of random variables, $5$ of them are independent.
In general there are $2^n$ possible random variables, and $\binom{2^n}2$ pairs. Computing this manually for $n\geqslant 3$ is tedious, and likely there is a better method of solving this problem. 
I suspect the number of pairs that are not independent is the number of ways in which one can partition $\{\omega_1,\ldots,\omega_n\}$, or the Bell numbers $B_{n+1}= \sum_{k=0}^n \binom nk B_k$, $B_1=1$. A closed form for $B_n$ is given by $B_n = \frac1e\sum_{k=0}^\infty \frac{k^n}{k!}$. So the number of pairs of random variables that are independent is $2^n - \frac1e\sum_{k=0}^\infty \frac{k^n}{k!}$.
