  Can you decide if there is a coincidence in the numbers counting two
different combinatorial objects? For example, can you decide if two regions in
$\mathbb{R}^3$ have the same number of domino tilings? There are two versions
of the problem, with $2\times 1 \times 1$ and $2\times 2 \times 1$ boxes. We
prove that in both cases the coincidence problem is not in the polynomial
hierarchy unless the polynomial hierarchy collapses to a finite level. While
the conclusions are the same, the proofs are notably different and generalize
in different directions.
  We proceed to explore the coincidence problem for counting independent sets
and matchings in graphs, matroid bases, order ideals and linear extensions in
posets, permutation patterns, and the Kronecker coefficients. We also make a
number of conjectures for counting other combinatorial objects such as plane
triangulations, contingency tables, standard Young tableaux, reduced
factorizations and the Littlewood--Richardson coefficients.
