I discovered this old question in connection with someone else's similar (and current) question: https://mathoverflow.net/questions/162428/the-simultaneous-conjugacy-problem-in-the-symmetric-group-s-n#comment414650_162428

If anyone still cares, here is a slightly different answer for your question using the character table instead of centralizer sizes.  The characters might be more accessible in certain cases (and of interest in their own right).
$$N=\frac{1}{n!} \sum_{\alpha \in G} \left( \sum_{\text{irreps}\ \chi} \chi(\alpha)^2 \right)^2$$
The inner sum is just the centralizer term in Marty Isaacs answer, but expressed in a different way.  It might be of some use in this form.  For example, if you want to enrich the group action to allow coordinate swap or inversion, similar class functions can be used.

The OP and others may be interested in the above linked question, which discusses the related decision problem and the generalization to more coordinates.