5
$\begingroup$

I've got a (what I think is) combinatorial problem: assume we have $n$ different elements, and we want to use these elements to construct some sets, each of which contains $m<n$ different elements. Moreover, for any two such sets, they should differ in at least some $k<m$ elements. (For example, if we have set $A=\{1,2,3,4,5\}$ and $B=\{1,6,7,8,5\}$, then they differ in three elements.) So, the question is, given $m$, $n$ and $k$, how many such sets (sets of size $m$) exist?

Thanks in advance!

$\endgroup$
4
  • 1
    $\begingroup$ Could you please clarify the question? If the $n$ elements are all different, don't the sets automatically contain $m$ different elements? Are we constructing one set a time, or several? $\endgroup$
    – Zavosh
    Commented Aug 20, 2013 at 6:51
  • $\begingroup$ @Prometheus, err, the things is, we want to construct many sets of size $m$, by using the given $n$ elements; and any pair of these constructed sets should be different in at least $k$ elements. And the question is how many such sets (of size $m$) can we construct. I hope this helps clarify the question. $\endgroup$
    – vistb
    Commented Aug 20, 2013 at 7:03
  • 1
    $\begingroup$ Looks like a definition of combinatorial designs. Usually we want $\mathcal{F} \subseteq {n \choose m}$ so that for every $A,B \in \mathcal{F}$ it holds that $|A \cap B| \leq k$. $\endgroup$
    – Igor Shinkar
    Commented Aug 20, 2013 at 7:07
  • $\begingroup$ @IgorShinkar Yeah, I think you get the idea, but it seems it should be $|A\cap B|\leq m-k$. $\endgroup$
    – vistb
    Commented Aug 20, 2013 at 7:13

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .