# Set partition

<https://en.wikipedia.org/wiki/Partition\\_of\\_a\\_set>

*A partition of a set* is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.

* Every equivalence relation on a set defines a partition of that set.
* Every partition of a set defines an equivalence relation on that set.
* A **setoid** is a set equipped with an equivalence relation or a partition.

## Definition and Notation

(…)

## Examples

* The empty set, `∅`, has exactly one partition, `P = ∅`; this is *the* partition, `P = ∅`, not a member of the partition, `P ≠ {∅}`
* Each singleton set, `{a}`, has exactly one partition, `{{a}}`
* Each non-empty set `X` has a *trivial partition*, `P = {X}`
* for any non-empty proper subset `A` of a set `U`, `A ⊂ U`,\
  the set `A` together with its complement `A'`\
  i.e. `U = A ⋃ A'`, so `A' = U ∖ A`\
  form a partition of `U`, viz. `{A, U ∖ A}`\
  (∀A. A : Set ⋀ A ≠ ∅). `A ⊂ U` => `𝙋(U) = {A, U \ A }`
* The set `{1,2,3}` has these 5 partitions:
  * `{ {1}, {2}, {3} }` or `1 | 2 | 3`
  * `{ {1, 2}, {3} }` or `1 2 | 3`
  * `{ {1, 3}, {2} }` or `1 3 | 2`
  * `{ {1}, {2, 3} }` or `1 | 2 3`
  * `{ {1, 2, 3} }` or `123` (when there's no confusion with the number)

## Refinement of partitions

(…)

## Noncrossing partitions

(…)

## Counting partitions

Bell number, `B(n+1)` = `Sum [k=0..n] n-choose-k B(k)`

Bell numbers satisfy the recursion:

$$
\displaystyle \Huge B\_{n+1}=\sum *{k=0}^{n}{n \choose k}B*{k}
$$

and have the exponential generating function:

$$
\displaystyle \Huge \sum *{n=0} ^{\infty} {\frac {B*{n}} {n!}} z ^{n} = e^ { e^ z - 1 }
$$

The first several Bell numbers are

```
B(0) = 1
B(1) = 1
B(2) = 2
B(3) = 5
B(4) = 15
B(5) = 52
B(6) = 203
```

**Bell triangle**

```
 1
 1  2
 2  3  5
 5  7 10  15
15 20 27  37  52
52 67 87 114 151 203
```

The number of partitions of an `n`-element set into exactly `k` non-empty parts is the Stirling number of the second kind `S(n, k)`.

The number of noncrossing partitions of an `n`-element set is the Catalan number `Cɴ`, given by

$$
\displaystyle \Huge C\_{n}={1 \over n+1}{2n \choose n}
$$

## Ref

<https://en.wikipedia.org/wiki/Equivalence\\_relation> <https://en.wikipedia.org/wiki/Equivalence\\_class>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mandober.gitbook.io/math-debrief/200-set-theory/topics/set-partition.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.