MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The number of non-isomorphic equivalence relations on a set of $n$ elements is the partition function $$p(n) =\frac{1}{\pi\sqrt{2}} \sum_{k=1}^{\infty} \sum_{h=1}^{k} \delta_{\gcd(h,k),1} \text{exp}\left(\pi i \sum_{j=1}^{k-1} \frac{j}{k}\left(\frac{hj}{k} - \left\lfloor \frac{hj}{k} \right\rfloor - \frac{1}{2}\right) - \frac{2\pi i h n}{k} \right) \sqrt{k} \frac{d}{dn}\left[ \frac{\sinh\left(\frac{\pi}{k} \sqrt{\frac{2}{3}(n - \frac{1}{24})}\right)}{\sqrt{n - \frac{1}{24}}} \right]$$ The Hardy-Ramanujan asymptotic formula states that $$p(n) \sim \frac{1}{4\sqrt{3}n}e^{\pi \sqrt{2n/3}}$$

By this answer (I would appreciate any reference to an actual derivation of this formula) the number of non-isomorphic relations on a set of $n$ elements is

$$a(n) = \sum_{1s_{1} + 2s_{2} + \cdot\cdot\cdot =n} \left(2^{\sum_{i,j \geq 1} \gcd(i,j)s_{i}s_{j}} \bigg/ \prod_{k=1} k^{s_{k}}s_{k}!\right)$$

I have no idea about the asymptotics of $a(n)$, but if you know of a reference that would be amazing. My question is whether anyone has researched, or if you have any idea about, whether or not $$\frac{p(n)}{a(n)} \sim 0$$ I conjecture that it is asymptotic to zero, but I have no idea how to prove it.

share|cite|improve this question
Consider a normal form for (the isomorphism classes of) the equivalence relations. (I like to think of them as diagonal block matrices.) There should be a region of "area" o(n) of unrelated elements, and in my picture a column of n/2 empty cells are guaranteed. Toggling elements in this area should give you that your ratio is smaller than 2/n, and likely even smaller with more astute toggling. Gerhard "Ask Me About Fibbonacci Matrices" Paseman, 2013.04.10 – Gerhard Paseman Apr 10 '13 at 15:52
It appears to me that for every equivalence relation $E$ there are at least $n$ nonisomorphic ways of making a relation $R$ such that $E$ is generated by $R$. If so, then $\frac{p(n)}{a(n)}\le \frac{1}{n}$. – Tom Goodwillie Apr 10 '13 at 16:02
The formula should be in Graphical Enumeration by Harary and Palmer, but I'm not sure. You can find a (sketch of a) derivation in Section 2.2 of Combinatorial Species and Tree like structures by Bergeron, Labelle and Leroux. – Martin Rubey Apr 10 '13 at 16:47
@Tom: Consider the empty relation. – Brendan McKay Apr 11 '13 at 9:13
OK, I'm considering it. – Tom Goodwillie Apr 11 '13 at 23:42
up vote 3 down vote accepted

You don’t need either of the two fancy formulas. Since every equivalence relation is the kernel of a function from the $n$-element set into itself, their number is at most $n^n$ (and taking them up to isomorphism can only make it smaller). On the other hand, there are $2^{n^2}$ binary relations in total, and each isomorphism class has at most $n!$ elements, hence there are at least $2^{n^2}/n!$ nonisomorphic relations. Thus, $$\frac{p(n)}{a(n)}\le\frac{n^nn!}{2^{n^2}}=2^{O(n\log n)-n^2}\to0.$$

share|cite|improve this answer
Algebra, pah! Where is a lovely combinatorial proof? Gerhard "Some Logicians Don't Appreciate Distinction" Paseman, 2013.04.10 – Gerhard Paseman Apr 10 '13 at 16:13
I’d prefer “Some Logicians Don’t Bother With Sophistication If There Is An Easy Way To Get Things Done”. – Emil Jeřábek Apr 10 '13 at 16:30
This seems like a strange use of the term "kernel" to me. – Greg Martin Apr 10 '13 at 16:37
Well, that’s how it is called in universal algebra (though here the algebra would be just a set with empty signature). Any better name? – Emil Jeřábek Apr 10 '13 at 16:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.