In [1], Newman et al. introduced the Reduced Mutual Information (RMI), a measure of the similarity between two partitions of a set useful in clustering and community detection. The computation of RMI requires counting the amount of contingency tables with fixed row and column sums, a #P-complete problem, for which the authors suggest to use analytical approximations that work in general, but for other not so pathological cases these give highly inaccurate approximations. We propose a hybrid scheme based on combining existing Markov chain Monte Carlo methods with analytical approximations to make more accurate estimates of the number of contingency tables in all cases.