Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



The number of overlapping subsets of a set
Posted:
Jun 16, 1996 9:29 AM


Does anybody know how to compute the number of overlapping subsets in a set? i.e. given a set of N items, how many sets of K items, such that the overlap between each pair of sets is of L items or less.
for example, for N = 6 , K = 3, L = 1, there are four subsets, e.g. (2 4 5) (1 3 5) (6 3 4) (6 1 2)
Realy, I want an analytic approximation for N >> K >> L >> 1, though even a solution for L = 1 will be nice. The underlying question is what the amount of data a network can hold, assuming each item is a set of K nodes, and allowing overlap of L nodes.
Thanks
Yehouda Harpaz http://www.azc.com/client/yeh/



