# Asymptotics of the Number of Non-Isomorphic Equivalence Relations and the Number of Non-Isomorphic Relations

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.

• 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 Apr 10, 2013 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}$. Apr 10, 2013 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. Apr 10, 2013 at 16:47
• @Tom: Consider the empty relation. Apr 11, 2013 at 9:13
• OK, I'm considering it. Apr 11, 2013 at 23:42

## 1 Answer

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.$$

• Algebra, pah! Where is a lovely combinatorial proof? Gerhard "Some Logicians Don't Appreciate Distinction" Paseman, 2013.04.10 Apr 10, 2013 at 16:13
• I’d prefer “Some Logicians Don’t Bother With Sophistication If There Is An Easy Way To Get Things Done”. Apr 10, 2013 at 16:30
• This seems like a strange use of the term "kernel" to me. Apr 10, 2013 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? Apr 10, 2013 at 16:51