-1
$\begingroup$

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( {\begin{array}{*{20}{c}} N\\ {{m_i}} \end{array}} \right)} $ possible combinations.

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

My thought was to find first how many combinations have an intersection of size at least $k=1,2,...,{\text {min}}(m_i)$ (denote this by $v(k)$), and then $I(k) = v(k) - v(k+1)$.

So far I know that for $k_{min}={\text {min}}(m_i)$:

$$v\left( {{k_{\min }}} \right) = \left( {\begin{array}{*{20}{c}} N \\ {{k_{\min }}} \end{array}} \right)\prod\limits_{i = 1}^p {\left( {\begin{array}{*{20}{c}} {N - {k_{\min }}} \\ {{m_i} - {k_{\min }}} \end{array}} \right)} $$ (and $I(k_{min})=v(k_{min})$).

However, the formula above for $k<k_{min}$ gives an over estimate.

Any help would be greatly appreciated.

$\endgroup$
  • $\begingroup$ copy on Mathematics. Please link in both directions when cross-posting. $\endgroup$ – Kaveh Jul 24 '13 at 20:15
  • $\begingroup$ Now deleted at math.SE. $\endgroup$ – András Salamon Sep 23 '13 at 14:19
1
$\begingroup$

I think you can finish off your computation using inclusion-exclusion.

If we fix a set $S$ of $k$ elements, let's count the number of ways to choose the $p$ sets so that they all contain $S$. Call this $n(k)$ [note that this number depends only on $k$ but not otherwise on $S$, justifying my notation]. You correctly showed how to compute $n(k)$, namely, $$n(k) = \prod_{i=1}^p {N-k \choose m_i-k}.$$

Now you should be able to use inclusion-exclusion to count the number of ways to choose the $p$ sets so that their intersection is of size exactly $k$.

For example, if $m=\min(m_1,\dots,m_p)$, then the number of ways to choose the $p$ sets so that their intersection is of size exactly $m$ is $$I(m) = {N \choose m} n(m)$$ [as you correctly noted in your question].

As another example, the number of ways to choose the $p$ sets so that their intersection is of size exactly $m-1$ is $$I(m-1) = {N \choose m-1} n(m-1) - m {N \choose m} n(m).$$ Here we've counted each set $S$ of size $m-1$ once; but then that overcounts things, because each set of size $m$ got counted $m$ times (once for each of its subsets of size $m-1$), so we account for the overcounting by subtracting off $m$ times the number of ways of getting an intersection of size $m$.

The number of ways to choose them so their intersection has size exactly $m-2$ is $$I(m-2) = {N \choose m-2} n(m-2) - (m-1) {N \choose m-1} n(m-1) + {m \choose 2} {N \choose m} n(m).$$ Here we've accounted for the overcounting by subtracting something related to sets of size $m-1$; but then that over-corrects and now undercounts some sets of size $m$, so we correct for that by adding an appropriate term. It's easier to re-discover the formula than to explain it, but hopefully you get the idea.

You should be able to take it from here.

$\endgroup$
  • $\begingroup$ Many thanks for your very helpful answer. Can you explain the third term in the expression for $I(m-2)$? I don't see why the first factor should be $\binom{m-1}{2}$. $\endgroup$ – user17047 Jul 24 '13 at 10:14
  • $\begingroup$ If I make it correct, this factor should be: $-\binom{m}{m-2}+(m-1)\binom{m}{m-1} = \binom{m}{m-2}$. $\endgroup$ – user17047 Jul 24 '13 at 10:47
  • $\begingroup$ @Rami, oops, you are right, that's an error. I've edited the answer to fix that equation. I think it is correct now. (How I got it: consider a set $S$ of size $m$. How many times has it been counted by the first two terms? It is counted positively $m(m-1)/2$ times by the first term, since it has $m(m-1)/2$ subsets of size $m-2$. Then, since there are $m$ subsets of size $m-1$ and each one gets counted negatively $m-1$ times by the second term, the second term has counted it negatively $m(m-1)$ times. Now $m(m-1)/2 - m(m-1) = -m(m-1)/2$, so we need to correct by adding it $m(m-1)/2$ times.) $\endgroup$ – D.W. Jul 24 '13 at 16:03
  • $\begingroup$ Can you give some more details on the way you choose the first terms for each $I(m-k)$ (this choice leads to the needed corrections)?. I tried to follow your logic for $m-3$ and afterwards, but I don't get the correct expressions. $\endgroup$ – user17047 Jul 24 '13 at 19:57
  • $\begingroup$ @Rami, this site is for research-level questions in theoretical computer science; I'm not seeing how this is research-level. This seems like something that should fall out from standard undergraduate techniques for counting. Am I missing something deep? Perhaps you might want to migrate it to Computer Science? $\endgroup$ – D.W. Jul 24 '13 at 20:02
0
$\begingroup$

Hint: Another way of seeing the problem is in terms of integer binary boolean operations:

The intersection of a set B indexed by b (the binary representation of the set) and a set B' indexed by b' is given by:

bb'

where the operation is bit-by-bit multiplication.

The number of elements in the intersection is then:

\sum \sum bb' = k

For b and b' running from 1 to N. Your equation is then:

\sum \sum bb' <= k The solution is an iterated map...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy