Take the 2-minute tour ×

The problem of counting the number of $k$-subsets in a set of size $n$ is well known. The answer is ${n \choose k}$.

But here, I want $k$-subsets with the property that any two of them have at least $d$ different elements.

If we take the set $S = \{1, 2, 3, 4, 5, 6\}$ ($n=6$), we have 15 4-subsets. (no need to enumerate them.) If you want those subsets to have at least 2 different elements pairwise, then the maximum number I could find is 3. ($\{1, 2, 3, 4\}, \{1, 2, 5, 6\}, \{3, 4, 5, 6\}$).

I am working with neuronal networks (kind of), and I want to represent symbols with $k$ neurons. But to ensure some difference between representation, I would like these subsets to be different enough (typically $d = k/2$). We also have $n >>k$.

Any (lower or upper) bound would be helpful. For example an approximation could use ${n/d \choose k/d}$ with proper rounding, but that is a bit rough.

Any simpler solution is also welcome, eg:

  • $k$ even, $d=k/2$, $n=0 \mod k$
  • $d=2$
  • etc.

Thanks for your consideration.

share|improve this question
Your question might be related to "constant weight codes" (a concept studied by coding theory); this page might provide some information too. –  Peter Košinár Jul 20 '13 at 0:43
@PeterKošinár : The link is broken to me. I will have a look to weight codes. –  Layus Jul 20 '13 at 7:15
That's it, definitely. I am looking for $A(n,d,k)$, which cannot be computed but only approximated... Too bad. Do we have an idea of the increase of this function, something in big $O$ notation maybe ? –  Layus Jul 20 '13 at 7:35
Just for reference: corrected link –  Peter Košinár Jul 20 '13 at 9:00

Your Answer



Browse other questions tagged or ask your own question.