2
$\begingroup$

Bell numbers are the numbers counting the total partitions on a set with $n$ distinct elements.

Explanation:

Consider a set like $A:=\left\{x_{1},x_{2},...,x_{n}\right\}$

A partial equivalence relation is either reflexive or it is not, so the number of partial equivalence relation on a set with cardinality $n$ is $B_n$ plus the relations which are partial equivalence relation but not reflexive, to make these relations we can consider that a set with $n$ element cannot be reflexive if at least one of the ordered pairs $(x_i,x_i)$ is not in that relation,so at first we can remove one of the ordered pairs $(x_i,x_i)$ $(0\le i\le n)$ and continue till we have $n-1$ ordered pair in the form $(x_i,x_i)$ removed (It cannot be $n$ because if we have $n$ ordered pairs then we are counting a relation which has been already counted by $B_n$)

Also given these kind of the partial equivalence relation, they can be combined with each other to make another equivalence relation that is not reflexive.

For example for $A=\left\{1,2,3\right\}$ the total conditions that a partial equivalence relation is not reflexive is: $$\left\{\right\}\,\,\,\,\,\,\,\,\,\,\,\,\,{{3}\choose{0}}$$ $$\left\{\left(1,1\right)\right\}\left\{\left(2,2\right)\right\}\left\{\left(3,3\right)\right\}\,\,\,\,\,\,\,\,\,\,\,\,\,{{3}\choose{1}}$$ $$\left\{\left(11\right),\left(22\right)\right\}\left\{\left(1,1\right),\left(3,3\right)\right\}\left\{\left(2,2\right),\left(3,3\right)\right\}\,\,\,\,\,\,\,\,\,\,\,\,\,{{3}\choose{2}}$$

$$\left\{\left(11\right),\left(22\right),\left(12\right),\left(21\right)\right\}\left\{\left(1,1\right),\left(3,3\right),\left(13\right),\left(31\right)\right\}\left\{\left(2,2\right),\left(3,3\right),\left(23\right),\left(32\right)\right\}\,\,\,\,\,\,\,\,\,\,\,\,\,{{3}\choose{2}}{{2}\choose{2}}$$

The relations in the last row are made form combining the second and third row, the number of choosing $2$ element form the set $A$ is ${{3}\choose{2}}$ ( indeed the number of way to choose $2$ of these elements to make an ordered pair in the form $(x_i,x_i)$) and there is ${{2}\choose{2}}$ ways to make a new partial equivalence relation with the $2$ elements.

If we sum the number of these kind of partial equivalence relations that are not reflexive with those partial equivalence relations which are reflexive we get :

$$\color{blue}{9+B_3}=10+5=15=\color{blue}{B_4}$$

Which is indeed the number of partial equivalence relations on $A$.

I used this strategy and tried for $n=4$, finally could derive the recurrence formula for Bell numbers:

$$2^{n}-1+\sum_{k=2}^{n-1}\sum_{m=2}^{k}{{n}\choose{k}}{{k}\choose{m}}+B_n=B_{n+1}$$

Mapping $k-2\mapsto k$ and $m-2\mapsto m$ equivalently the formula can be rewritten as:

$$2^{n}-1+\sum_{k=0}^{n-3}\sum_{m=0}^{k+2}{{n}\choose{k+2}}{{k+2}\choose{m+2}}+B_n=B_{n+1}$$

With the initial value $B_0=1$ the formula gives: $$0+B_{0}=0+1=\color{blue}{1}=\color{blue}{B_{1}}$$ $$1+B_{1}=1+1=\color{blue}{2}=\color{blue}{B_{2}}$$ $$3+B_{2}=3+2=\color{blue}{5}=\color{blue}{B_{3}}$$ $$10+B_{3}=10+5=\color{blue}{15}=\color{blue}{B_{4}}$$ $$37+B_{4}=37+15=\color{blue}{52}=\color{blue}{B_{5}}$$ $$136+B_{5}=136+52=\color{red}{188}\ne \color{red}{B_{6}}$$

The formula does not give the right number for $B_{6}$, but I'm sure the validity of the other Bell numbers is not accidental, so why the formula gives such a wrong number? where I was wrong?

Finally I should say that I came up with this calculation, because I cannot understand why the total number of partial equivalence relations on a set with cardinality $n$ is $B_{n+1}$, so It would be really appreciated if someone explain that with more details.

$\endgroup$
4
  • $\begingroup$ Doesn't your new sum over $k$ range from $k=0$ to $n+1$? $\endgroup$ – fundamentalform Jan 29 '20 at 10:56
  • $\begingroup$ @higgs, you mean the formula in the yellow box?well why? $\endgroup$ – user715522 Jan 29 '20 at 10:57
  • $\begingroup$ It seems to me that you've squeezed out two terms from that outer sum over $k$ $\endgroup$ – fundamentalform Jan 29 '20 at 11:04
  • $\begingroup$ @well I checked that at Desmos.com and the two formula are the same, besides changing the index does not give us the right number for $B_6$, I think there should be a counting problem here that I'm not aware of $\endgroup$ – user715522 Jan 29 '20 at 11:07
1
$\begingroup$

First, the number of PER's on $\{1,\ldots,n\}$ is indeed $B_{n+1}$. To show this, we construct a bijection between PER's on $\{1,\ldots,n\}$ and equivalence relations on $\{0,1,\ldots,n\}$: given a PER, keep the existing equivalence classes and put the non-reflexive elements in a new equivalence class with $0$ (if there are none, put $0$ in an equivalence class on its own).

So if your formula breaks down, it must be getting the number of non-reflexive PER's wrong, but only for $n$ at least $5$. In fact, it appears you are only counting the number of non-reflexive PER's which have at most one non-singleton class (in your formula, $k+2$ is the number of reflexive elements, and $m+2$ is the number of these in the large equivalence class). If $n\leq 4$ this covers all the non-reflexive PER's, but if $n=5$ you will miss out PER's with two classes of size $2$ and one irreflexive element, that is $$\{(2,2),(2,3),(3,2),(3,3),(4,4),(4,5),(5,4),(5,5)\}$$ and isomorphic PER's. There are $15$ PER's of this form ($5$ ways to choose the irreflexive element and then $3$ ways to pair off the remaining four), which is exactly the discrepancy. For larger numbers, the number of missing PER's will grow very quickly.

$\endgroup$
4
  • $\begingroup$ in there any way to edit my formula? $\endgroup$ – user715522 Jan 29 '20 at 11:24
  • $\begingroup$ @user715522 the problem is that although it's quite easy to add in this particular case (two larger classes), as $n$ gets larger the number of extra cases you need to deal with also grows. Of course, you could deal with them all at once by writing the number of PER's with $k$ reflexive elements in terms of $B_k$ but then you just get the standard recurrence for the Bell numbers. $\endgroup$ – Especially Lime Jan 29 '20 at 12:57
  • $\begingroup$ thank you, can you please explain why the number of partial equivalance relations over a set with $n$ elements is $B_{n+1}$? although I hard tried to get that but I don't $\endgroup$ – user715522 Jan 29 '20 at 13:01
  • $\begingroup$ @user715522 that's what the first paragraph of my answer shows. $\endgroup$ – Especially Lime Jan 30 '20 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy