There are $2^L$ binary strings of length $L$. The number of ordered $N$-tuples of distinct strings is $(2^L)!/(2^L-N)!$, so the probability that all are unique is $\dfrac{(2^L)!}{(2^L-N)! 2^{NL}}$. As $M = 2^L \to \infty$ with $N$ fixed, that is asymptotically
$$1 - \dfrac{N(N-1)}{2M} + \dfrac{N(N-1)(N-2)(3N-1)}{24M^2} + \ldots$$
The Hamming distance between a pair of random binary strings of length $L$ is a binomial random variable with parameters $L$ and $1/2$. For $k << L$ the probability that this distance is $k$ is ${L \choose k} 2^{-L}$. In $N$ random strings the expected number of
unordered pairs with distance $< k$ is $\mu = \dfrac{N(N-1)}{2} \sum_{j=0}^{k-1} {L \choose j} 2^{-L}$. When $\mu$ is small, we should be able to approximate the distribution of the number of such pairs with
a Poisson distribution of parameter $\mu$, so the probability that there are no such pairs is
approximately $e^{-\mu}$.
Your formulation in terms of Hamming distance seems to be a good one for making progress.
The quantity you want then seems to be denoted $A_2(n,n/2)$. The Plotkin bound gives: if $n/2$ is even then $A_2(n,n/2) \le 2n$, otherwise $A_2(n,n/2) \le 2\lfloor n/2+1 \rfloor = n+1$.
A lower bound can be found by constructing an explicit set. For the special case $n=2^t$ for positive integer $t$, consider the strings $0^n, 0^{n/2}1^{n/2}, 0^{n/4}1^{n/4}0^{n/4}1^{n/4},\dots, 0^21^20^2\dots 0^21^2, 0101\dots 01$. This satisfies the conditions and has $t+1 = 1 + \log_2 n$ strings.
I suspect that better bounds are known, and would be interested in a more precise analysis. Perhaps someone like Peter Cameron might be able to provide pointers.
It is worth remarking that there is an interesting reformulation of your problem in terms of set systems.
Given a set of strings which are all distance $n/2$ from each other, first transform the coordinate system. Pick one string in the set and flip its 1 bits to make it the all-zero string. Applying the same permutation to each of the other strings retains the Hamming distances.
This leads to every string other than $0^n$ having exactly $n/2$ bits set to 1.
Consider the set system of which these strings are the characteristic vectors of sets in the system, excluding the all-zero vector. Each set contains precisely $n/2$ elements. Observe that the pairwise intersections contain precisely $n/4$ elements.
Then your question can be rephrased as follows (equivalent up to the difference of 1 from excluding the $0^n$ string).
What is the largest possible set system of subsets of an $n$-element set, such that each contains precisely $n/2$ elements, and such that their pairwise intersections have precisely $n/4$ elements?
Again this sounds natural and I would expect this is known, but I did not find anything about this problem in the Lovász Combinatorial Problems and Exercises book or in the Deza/Frankl survey from 1983; it seems a bit tricky to find the right online search terms. The usual setup for Erdős–Ko–Rado style results is more relaxed, allowing intersections of at least some threshold; here all pairwise intersections are precisely $n/4$.
- M. Deza and P. Frankl, Erdös–Ko–Rado Theorem—22 Years Later, SIAM J. Alg. Disc. Meth. 4 419–431, 1983. doi:10.1137/0604042
There is another potentially relevant paper but I have not been able to extract much from it (or at least from the scanned image of the paper).
Best Answer
Actually this seems quite easy
Let $A^d_{i,j}$ be the event that two strings $s_i$ $s_j$ have distance $d$. Then, if both $s_i,s_j$ are random, we have $$P(A^d_{i,j})= \binom{n}{d} 2^{-n}$$
Then, if we sample $k$ random strings, the expected number of pairs with such distance is
$$ \frac{k(k-1)}{2} \binom{n}{d} 2^{-n}$$