1
$\begingroup$

From "Models and Games" by Jouko Vaananen (Cambridge studies in advanced mathematics), I quote

The Hardy-Ramanujan asymptotic formula says that the number of equivalence relations on a fixed set of $n$ elements is asymptotically $$\frac{1}{4\sqrt{3}n}e^{\pi\sqrt{2n/3}}$$ So this is also an asymptotic upper bound for the number of non-isomorphic equivalence relations on a universe of $n$ elements.

I am very confused by this as I thought that the Hardy-Ramanujan asymptotic formula was asymptotic to the partition function $p(n)$ which says how many times you can write $n$ as a sum of positive integers, not the number of partitions of a set of $n$ elements. Is this book incorrect or am I missing something about the connection between equivalence relations and the partition function?

$\endgroup$

1 Answer 1

3
$\begingroup$

If $R$ and $S$ are two equivalence relations on a set $X$ of card. $n$, we say that they are equivalent if there exists a bijection $\varphi:X\rightarrow X$ such that:

$\varphi(x)R\varphi(y)\quad\iff\quad xSy$

Then the partition function $n$ is counting the number of equivalence relations on $X$ modulo this identification.

$\endgroup$
1
  • $\begingroup$ In other words, the Hardy-Ramanujan asymptotic formula (which is counting partitions in the arithmetic sense) tells us about the assymptotic behaviour of counting up to ismorphism equivalence relations over the set $\{ 1, ..., n \}$. But it is not strictly talking about Bell numbers en.wikipedia.org/wiki/Bell_number $\endgroup$
    – boumol
    Apr 10, 2013 at 14:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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