A partition of a set
$S=\left{1,\ldots,n\right}$ is a family of
sets $T_1,\ldots,T_k$ satisfying
- $i\neq j\longrightarrow T_i\cap
T_j=\emptyset$
- $\cup_{i=1}^kT_k=S$
- $T_i\neq\emptyset$for$i=1,\ldots,
k$
The induced equivalence relation has $i\sim j$ if
and only if $i$ and $j$ belong to the same partition.
There are exactly fifteen ways to partition a set of four
elements:
l{
$(1234)$
$(123)(4), (124)(3), (134)(2), (234)(1)$
$(12)(34), (13)(24), (14)(23)$
$(12)(3)(4), (13)(2)(4), (23)(1)(4), (24)(1)(3),
(34)(1)(2)$
$(1)(2)(3)(4)$
}
Note that $(12)(3)(4)$ is the same partition as, for example,
$(3)(4)(21)$ as the equivalence relation is the same.
Consider partitions of a set $S$ of five elements (named
$1,2,3,4,5$) with sizes 2,2,1. These may be enumerated as
follows:
> u <- c(2,2,1)
> setparts(u)
[1,] 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3
[2,] 2 2 3 1 1 1 2 2 3 2 2 3 1 1 1
[3,] 3 2 2 3 2 2 1 1 1 3 2 2 2 1 2
[4,] 2 3 2 2 3 2 3 2 2 1 1 1 2 2 1
[5,] 1 1 1 2 2 3 2 3 2 2 3 2 1 2 2 See how each column has two 1s, two 2s and one 3. This is because the
first and second classes have size two, and the third has size one.
The first partition, x=c(1,2,3,2,1), is read class 1
contains elements 1 and 5 (because the first and fifth element of
x is 1); class 2 contains elements 2 and 4 (because the second
and fourth element of x is 2); and class 3 contains element 3
(because the third element of x is 3). Formally, class
i has elements which(x==u[i]).