✎ partition [CMQG Wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Partition of a set ======

===== Definition =====

Let $S$ be a finite set. A **partition** $\pi$ of $S$ is a decomposition of $S$ into disjoint non-empty subsets. That is
$$\pi=\{V_1,\dots,V_n\},$$
where $V_i\subset S$, $V_i\neq\emptyset$, and $V_i\cap V_j=\emptyset$ for any $i,j=1,\dots,n$, $i\neq j$. The subsets $V_i$ are called **blocks** of the partition $\pi$.

The set of all partitions of $S$ is denoted $\Pscr(S)$. In combinatorics, we usually take the canonical choice $S:=\{1,\dots,k\}$, for which we denote $\Pscr(k):=\Pscr(S)$.

Partition of a set should not be confused with a [[wp>Partition_(number_theory)|partition of a number]]. Any partition of a set induces a partition of a number if we remember only the sizes of the sets. Indeed, if $\pi=\{V_i\}_{i=1}^n$ is a partition of $S$, then $(|V_i|)_{i=1}^n$ is a partition of $|S|$.

Often we consider the set $S$ to be a totally ordered set. In this case, we can define the notion of a //non-crossing partition//. A partition $\pi=\{V_i\}_{i=1}^n$ of a totally ordered set $S$ is called **non-crossing** if for every four elements $a<b<c<d$ of $S$ having $a,c\in V_i$ and $b,d\in V_j$ implies $i=j$. The name //non-crossing// is motivated by the graphical representation of such partitions (see below).

===== Representing partitions =====

==== Graphical representation on one line ====

We can represent elements $p\in\Part(k)$, that is, partitions of a set $\{1,\dots,k\}$ as diagrams as follows. Put $k$ points on one line representing the elements of the set $\{1,\dots,k\}$. For each block $V\in p$ connect all the points representing elements of $V$ by a node.

For example, consider $k=8$ and a partition $p=\{\{1,2,5\},\{3,6\},\{4\},\{7,8\}\}$. This can be represented by the following diagram
$$p=\LPartition{0.3:4}{0.6:1,2,5;0.6:7,8;1.2:3,6}$$

If we draw all the nodes above the points (equivalently all the nodes bellow the points), we can characterize the non-crossing partitions using the graphical representation. A partition $p\in\Pscr(k)$ is non-crossing if and only if the lines corresponding to different blocks do not cross.

As an example, we see that the partition above is not non-crossing. Indeed, we have the sequence 2<3<5<6, where the points 2 and 5 belong to the first block and the points 3 and 6 belong to the second block. And indeed, in the graphical representation, the lines corresponding to the first and second block must cross each other.

==== Graphical representation on two lines ====

When using partitions to build diagramatical categories (such as the [[category_of_all_partitions|category of all partitions]]), we usually divide the points in our set $S$ into //upper points// (modeling domain of a morphism) and //lower points// (modeling codomain of a morphism). Thus, in this case, the canonical choice for $S$ is something like $S=\{1,\dots,k\}\sqcup\{1,\dots,l\}$, where the first $k$ elements are called **upper points** and the last $l$ elements are called **lower points**. The set of all partitions with $k$ upper and $l$ lower points is denoted $\Pscr(k,l)$

The idea of drawing the diagrams is very similar. Put all the upper points to one line and all the lower points to a second line below. Then connect by nodes those points that belong to the same block.

As an example, consider a partition $p\in\Pscr(4,3)$
$$p=\BigPartition{
\Pline(1,1)(2,0)
\Pline(2,1)(1,0)
\Psingletons 1to0.75:3,4
\Psingletons 0to0.25:3
\Pline(1.75,0.25)(3,0.25)
}$$
This is a partition, where four upper and three lower points are divided into four blocks. One block consists of the upper point 1 and lower points 2 and 3. Second block consists of upper point 2 and the first lower point. Finally the last two blocks contain only one point, namely the third and the fourth point of the upper row.

In this case, we again can define non-crossing partitions in the natural way -- a partition $p\in\Pscr(k,l)$ is non-crossing if and only if there is a graphical representation of $p$, where the nodes representing different blocks do not cross (following the rule that the nodes can be drawn only between the two lines). This corresponds to the original definition if we consider the so-called //cyclic order// of the points. That is, the point in the right top corner is the lowest, then follow all the points on the upper row from right to left, then comes the left bottom point and going on the bottom line from left to right we reach the greatest point in the bottom right corner.

==== Word representation ====

Consider again partitions on one line $p\in\Pscr(k)$. Another possibility to represent them is using words. Choose some alphabet with at least $k$ letters and assign a unique letter to each block of $p$. Then $p$ is represented by a word of the form $a_1\cdots a_k$, where each $a_i$ is a letter assigned to a block corresponding to the $i$-th point.

The above mentioned example
$$p=\LPartition{0.3:4}{0.6:1,2,5;0.6:7,8;1.2:3,6}$$
can be the represented by a word
$$p=\mathsf{aabcabdd}$$

The word representation is of course not unique. We could have assigned a different set of letters to the blocks and write for example
$$p=\mathsf{ccfbcfee}$$

===== Further reading =====

  * [[wp>Partition_of_a_set|Partition of a set]]
  * Richard P. Stanley. //Enumerative Combinatorics Vol. 1.// [[https://www.cambridge.org/us/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/enumerative-combinatorics-volume-1-2nd-edition?format=PB&isbn=9781107602625|Cambridge University Press, 2011]] [[http://www-math.mit.edu/~rstan/ec/ec1.pdf|Manuscript available on-line.]]
  * Alexandru Nica and Roland Speicher. //Lectures on the Combinatorics of Free Probability.// [[https://www.cambridge.org/core/books/lectures-on-the-combinatorics-of-free-probability/D8FC5F2DCCF6C34BB3164E0C0C29437F|Cambridge University Press, 2006.]] [[https://www.math.uni-sb.de/ag/speicher/publikationen/Nica-Speicher.pdf|Manuscript available on-line.]]
User Tools

Site Tools

Page Tools
