My Math Forum Number of intersections between given sets

 July 22nd, 2013, 07:07 AM #1 Newbie   Joined: Jul 2013 Posts: 1 Thanks: 0 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.

 Tags intersections, number, sets

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post kikishillong Computer Science 2 September 30th, 2014 04:40 PM tbillion Applied Math 17 September 5th, 2012 06:13 AM hoyy1kolko Algebra 4 March 15th, 2011 06:44 AM hoyy1kolko Algebra 4 March 12th, 2011 11:00 PM mAraujo Real Analysis 2 July 26th, 2009 12:56 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top