Theorem. Choose $Q$ random natural numbers in the set $\{1,2, ..., M\}.$ The probability of getting at least one collision is
$$P_C(Q) = 1 - \frac{M - (Q - 1)}{M} P_{\neg C}(Q-1).$$
Notation. By $P_C$, I mean the probability of getting a colision. By $P_{\neg C}$ I mean the probability of not getting a collision.
Remark. This is the birthday problem.
Remark. So $P_C(Q)$ is just being computed by using its complement. The reason I express the theorem this way is because its induction proof relates directly to it being enunciated this way.
Theorem. $$P_C(Q) \approx 1 - e^{-\tfrac{(Q-1)Q}{2M}}.$$
Proof. We know $$e^{-x} = 1 - x + x^2/2! - x^3/3! + x^4/4! - ...$$
If we take the two terms of this expansion, we get $e^{-x} \approx 1 - x$. Then
\begin{align} P(Q)&= \prod_{i=1}^{Q-1} \left(1 - \dfrac{i}{M}\right)\\ &\approx \prod_{i=1}^{Q-1} e^{-i/M} \\ &= e^{-1/M} e^{-2/M} \dotsc\ e^{-(Q - 1)/M} \\ &= e^{-\sum_{i=1}^{Q-1} i/M} \\ &= e^{-\dfrac{1}{M} (Q-1)Q/2}\\ &= e^{-\dfrac{(Q-1)Q}{2M}}, \end{align}
So $P_C(Q) \approx 1 - P_{\neg C}(Q),$ as desired.
Question. How can I (at least) have some notion of how off the right number I am if I use this estimation to compute the probability of getting a collision in a concrete case?
Some empirical results:
Your approximation for the probability of a collision of $1-e^{-{(Q-1)Q}/({2M})}$ is never too high and is only exact when $Q=1$ or $0$
Clearly there is an error when $Q\gt M$, as the probability of a collision is $1$ while your approximation gives a value slightly less than $1$. In particular then $Q=M+1$ the error is $e^{-({M+1})/{2}}$, which is very small for large $M$ and the error gets even smaller when $Q$ is larger still
This is not the largest error when $M\gt 2$. Instead the largest error then seems to occur when $Q \approx \sqrt{3M}$ and seems to be between $\dfrac{0.19}{\sqrt{M}}$ and $\dfrac{0.26}{\sqrt{M}}$, declining slowly as $M$ increases
As an illustration, with $M=10$ the largest error seems to be when $Q=6$, which is near $\sqrt{30}$, with the exact probability of a collision being $0.8488$ but your approximation giving about $0.77687$; the difference of about $0.07193$ is around $\frac{0.2274}{\sqrt{10}}$. The following is a table of the probabilities of collisions for different $Q$s when $M=10$