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.

See also

http://oeis.org/A000110 or


  • 1
    $\begingroup$ 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)$ $\endgroup$ – coool Oct 6 '14 at 13:27
  • $\begingroup$ 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. $\endgroup$ – Slepecky Mamut Oct 6 '14 at 14:01

Your Answer

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

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