# Total no. of partitions of $A$ using stirling no. of $2^{\text{nd}}$ kind

My notes describe Stirling numbers of $2^{\text{nd}}$ kind as :

Given non-negative integers $r,n$ the stirling numbers of $2^{\text{nd}}$ kind denoted by are defined as:

no. of ways of distributing $n$ distinct objects into $r$ identical empty boxes s.t. no box remains empty.

then there is a paragraph stating about equivalence relation:

Let $A=\{1,2\ldots n\}$ be a set and $S=\{S_1,S_2,\ldots S_r\}$ be a partition of $A$ with $r$ parts.

$(S_i\subseteq A,S_i\neq\phi,\cup S_i=A,S_i\cap S_j=\phi,$for $i\neq j).$ We define a binary relation $R$ on set $A$ as follows:

$aRb \Leftrightarrow a,b\in S_i$ for some $i~~,1\leq i\leq r$

Total no. of equivalence relations $=$ total no. of partitions of $A$ $=~~$ $S(n,1)+S(n,2)+\ldots S(n,n)$

I can't understand how can we write total no. of equivalence classes this way .Any help would be appreciated....

Bell numbers, 1,1, 2,5,15,52...

1. by recursion $B_{n+1}=\sum_{k=0}^{n}\left(\begin{array}{c} n\\ k \end{array}\right)B_{n-k}$
2. By generating function $B(x)=e^{e^{x}-1}$

No exist a closed formula.

• I can't understand this.I wanted reason for total no. of partitions of $A=S(n,1)+S(n,2)+\ldots S(n,n)$ – coool Oct 6 '14 at 13:27
• Stirling number of $2^nd$ type $S(n,k)$ ~ number of partitions $\{1,2...n\}$ with exactly $r$ parts ~ number of equivalence relations on $\{1,2...n\}$ with exactly $k$ equivalence-classes. A one-to-one map between equivalence-classes and sets is simple: Class $\rightarrow$ set of all equivalent elements. So, "equivalency relation $\rightarrow$ partition {1,2...n} to sets of equivalent elements" is a one-to-one map between partitions and equivalency relations. – Slepecky Mamut Oct 6 '14 at 14:01