My Math Forum (http://mymathforum.com/math-forums.php)
-   -   Number of intersections between given sets (http://mymathforum.com/advanced-statistics/37188-number-intersections-between-given-sets.html)

 mid July 22nd, 2013 07:07 AM

Number of intersections between given sets

Assume that we have $P$ sets, with given sizes: $m_1, m_2, ..., m_p$. The (distinct) elements in each set are taken from $N$ elements (where $m_1,m_2,...,m_p \le N\$).
A combination is defined as an assignment of distinct elements (from $N\$ possible ones) to each of the sets. For example, say that we have $p=2$ sets of sizes $m_1=2, m_2=3$and that $N=4$. Then one possible combination is $\left\{ {1,2} \right\},\left\{ {1,2,3} \right\}$, another one is $\left\{ {2,3} \right\},\left\{ {2,3,4} \right\}$ and so on.

It is easy to note that there are $\prod\limits_{i= 1}^p \left( N \\ {{m_i}} \right)$ possible combinations.

My question is - given the sizes $m_1, m_2, ..., m_p$, how many combinations have intersection of size $k=1,2...,{\text max}(m_i)$ (denote this function of $k\$ by $I(k)$)?

My first thought was to find first how many combinations have an intersection of size at least $k$, $s(k)$:
My guess was that $S(k)= \left( N \\ {{k}} \right)\prod\limits_{i = 1}^p \left( N-k \\ {{m_i-k}} \right)$
(and then $I(k)= s(k) - s(k+1)$)
however, the formula above for $s(k)$ gives an over estimate. Obviously, in the first example above, it will take into account both $\left\{ {1,2} \right\},\left\{ {1,2,3} \right\}$ and $\left\{ {2,1} \right\},\left\{ {2,1,3} \right\}$ that are essentially the same.

Any help would be greatly appreciated.

 All times are GMT -8. The time now is 12:33 AM.