Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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 –  boumol Apr 10 '13 at 14:18

Your Answer

 
discard

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.