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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Apr 10, 2013 at 14:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .