Probability that 2 of t strings of length n are equal Given t bit-strings of length n that are generated randomly.
What is the probability that at least 2 of these strings are equal.
I've seen someone who wrote that the probability is $ \le \frac{t^2}{2^n}$
The reasoning is that you have $t$ options to choose the first string.
The $t$ options to choose the second string, and given a string chosen at the first stage, the probability that the other chosen string is equal to the first one is $\frac{1}{2^n}$.
The you sum all these options of choosing 2 equal string ($t^2$) and you get $ \frac{t^2}{2^n}$
This just seems wrong because for each such choice of 2 strings there are many other options to the other strings, but I can't find a proof to show that it is wrong.
Does this reasoning make sense? 
 A: This reminds of the Birthday Problem! 
In a room with $n$ students, what is the probability that at least two students share the same birthday? The probability that two students share a birthday is $\frac{1}{365}$, but you have to compare all pairs of n students.
To make an analogy, the probability that two strings are equal is $\frac{1}{2^n}$, but you have to compare all pairs of t strings.
A: We can actually be more precise and say that the probability is at most $\frac{\binom t2}{2^n}$.
For $1 \le i < j \le n$, let $A_{ij}$ be the event that the $i^{\text{th}}$ string is equal to the $j^{\text{th}}$ string. Then $\Pr[A_{ij}] = \frac{1}{2^n}$, because the $j^{\text{th}}$ string is equally likely to be any of $2^n$ possibilities, one of which is equal to the $i^{\text{th}}$ string.
We have two equal strings if any of the $\binom t2$ events $$A_{12}, A_{13}, A_{14}, \dots, A_{t-1,t}$$ occur. If these events were all disjoint - no two could happen at the same time - the probability that any of them occur would be exactly $\binom t2 \cdot \frac1{2^n}$. They're not all disjoint; if the $1^{\text{st}}$ string is equal to the $2^{\text{nd}}$, and the $3^{\text{rd}}$ string is equal to the $4^{\text{th}}$, then $A_{12}$ and $A_{34}$ both occur. So this is not the actual probability we want.
However, it's still an upper bound. For any two events $A$ and $B$, we have \begin{align}
\Pr[A \text{ or } B] &= \Pr[A] + \Pr[B] - \Pr[A \text{ and }B] \\
&\le \Pr[A] + \Pr[B]
\end{align}
and by induction, we can show that for any $m$ events $A_1, A_2, \dots, A_m$, we have
$$\Pr[A_1 \text{ or } A_2  \text{ or }  \dots  \text{ or } A_m] \le \Pr[A_1] + \Pr[A_2] + \dots + \Pr[A_m].$$
This is known as the union bound. In our case, it says that
\begin{align}
\Pr[A_{12} \text{ or } A_{13}  \text{ or }  \dots  \text{ or } A_{t-1,t}]
  &\le \Pr[A_{12}] + \Pr[A_{13}] + \dots + \Pr[A_{t-1,t}] \\
  &= \binom t2 \frac1{2^n}.
\end{align}
We can find the exact probability by first finding the probability that all $t$ strings are different. This is $$\frac{(2^n-1)(2^n-2) \cdots (2^n-t+1)}{(2^n)^{t-1}}.$$ (If all strings must be different, there are $2^n-1$ possibilities for the second string, $2^n-2$ for the third, and so on.) So the exact answer is $1 - \frac{(2^n-1)(2^n-2) \cdots (2^n-t+1)}{(2^n)^{t-1}}$.
But the union bound is often useful when the exact answer cannot be found: for example, if the dependence between the events is very hard to describe. Even here, the bound $\binom t2 \frac1{2^n}$ may be more useful than an exact answer: it makes it much easier to see that if $t$ is much smaller than $2^{n/2}$, then $\binom t2$ is much smaller than $2^n$, and so the probability that any two strings are equal is very small.
A: I think this probability is $1-\frac{\binom{2^n}{t}}{\binom{2^n -1 +t}{2^n -1}}$. Essentially this means 1- probability to have all strings different. The numerator is all different strings. The denominator is all cases of selecting t out of $2^n$ with repetitions.
EDIT: 
OK @MishaLavrov's solution $\frac{\binom{2^n}{t} t!}{2^{nt}}$ is better. What my solution gives is $\frac{\text{number of ways to get $t$ unique strings length $n$ from a set of $2^n$ strings, order does not matter}}{\text{number of ways to get $t$ strings length $n$ from a set of $2^n$ strings, order does not matter}}$.
For example, if $t=3$, one possible denominator would be $aba, aab, baa$ counted as one. In the numerator we can have $abc,bac,...,cba$ all counted as one outcome. 
My confusion is that, even if strings are 'generated randomly', do we account for repeated sets or not? 
