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 sets, with given sizes: . The (distinct) elements in each set are taken from elements (where ).
A combination is defined as an assignment of distinct elements (from possible ones) to each of the sets. For example, say that we have sets of sizes and that . Then one possible combination is , another one is and so on.

It is easy to note that there are possible combinations.

My question is - given the sizes , how many combinations have intersection of size (denote this function of by )?

My first thought was to find first how many combinations have an intersection of size at least , :
My guess was that
(and then )
however, the formula above for gives an over estimate. Obviously, in the first example above, it will take into account both and that are essentially the same.

Any help would be greatly appreciated.

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