Number of combinations such that each pair of combinations has at most x elements in common?

Question

I am doing research on the sense of smell and have a combinatorics problem: I have 128 different odors (n) and I mix them in mixtures of 10 (r). There are 2.26846154e+14 different mixtures. What I want to know is: What is the size of the group of mixtures such that no mixture in the group shares more than 5 (k) odors with any other mixture in the group. I hope this makes sense. I very much appreciate your help!

Answer 1

First of all, such kind of questions are very hard to answer exactly, in particular, if the set of possibilities is so huge as in your case. However, there is a standard method to derive an upper bound on the maximum size. I will compute this upper bound in this answer.

Your question can be reformulated: What is the maximum size of a set $X$ of mixtures, such that each set of $6$ odors is contained in at most one mixture in $X$?

We double count the set $Y$ of pairs $(T,B)$ where $T$ is a set of $6$ odors, and $B\in X$.

There are $\binom{128}{6}$ possibilities for $T$, and each $T$ is contained in at most one $B$. So $\#Y \leq \binom{128}{6}$. On the other hand, there are $\#X$ possibilities for $B$, and each $B$ containes $\binom{10}{6}$ elements $T$. So $\#Y = \#X\cdot\binom{10}{6}$.

This yields $$ \#X \leq \frac{\binom{128}{6}}{\binom{10}{6}} \approx 1080219781813,33$$ so your group of mixtures cannot contain more than $1080219781813$ mixtures.