# discrete 7-4 等價關係

## partition
A is a set
$A_i \in A$
$A_i\cap A_j = \varnothing$
$A_i\cup A_j\cup A_k..=A$

## equivalence
$x \in A, x\in A_i,[x]=A_i$

Verify reflexive, symmetric, and transitive

### ex
if A={1,2,3,4,5} R={(1,1),(2,2),(2,3),(3,2),(3,3),(4,4),(4,5),(5,4),(5,5)}

[1]={1}
[2]=[3]={2,3}
[4]=[5]={4,5}
A=$[1]\cup [2]\cup [4]$

## R $\iff$ Partition
等價關係，會觀察到如果是等價關係的話，在集合中的每個元素都是相等的
R -> Partition
R <- Partition
one to one

### ex
A={1,2,3,4,5,6},How many equivalence relation
b. How many of the equivalence relations in part (a) satisfy 1, 2∈[4]?

a.$\sum\limits_{i=1}^6{s(6,i)}=203$
b.$\sum\limits_{i=1}^4{s(4,i)}=15$

discrete 5-3
# stirling numbers of the second kind
解決一個大集合分成多個非空子集合的方法，或是一對一對應的方法數
s(m,n) =這個大集合有m個元素，要分n組

$s(m,n) = \frac{1}{n!}\sum\limits_{i = 0}^n{(-1)^iC_{i}^{n}(n-i)^m}$