# Count $k$-subsets with at least $d>1$ different elements (pairwise)

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.

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