We develop the collision probability for a canonical collision problem using a counting procedure based on signed graphs. The result involves Stirling numbers of the second kind and is straightforward to evaluate. Characteristics are discussed in the context of a generalized birthday problem and error of the standard binomial approximation is quantified. The basic solution for two sets is also extended to an arbitrary number of sets.
- Signed graphs
- Stirling numbers