So we have a canonical surjection $X \twoheadrightarrow \pi$ : $x\in X \mapsto$ the member of $\pi$ which contains $x$. It is a surjection because each member of $\pi$ is non-empty.
Partitions come in several varieties:
- Of a number or of a set? E.g., $3=2+1$ or $\{1,2,3\}=\{1,2\}+\{3\}$?
- Ordered or unordered? E.g., $2+1$ or $1+2$; $\{1,2,3\}=\{1,2\}+\{3\}$ or $\{1,2,3\}=\{3\}+\{1,2\}$?
- Weak or strong? I.e.: For number partitions, do we allow $0$? For set partitions, do we allow the empty set $\emptyset=\{\}$?
A note on terminology: Normal mathematical usage is that the word “partition”, without any modifier, is what the taxonomy above would call an “unordered strong partition” (number or set, as determined by the context). If an ordered partition is under discussion, it is called just that. Rather than the “weak/strong” distinction made above, weak partitions are sometimes (e.g., by Martin Aigner in Combinatorial Theory) called “generalized partitions”. Also, an ordered strong number partition is normally called a “composition”. So the above terminology is neither traditional nor necessary, but it does have the advantages, perhaps, of explicitness and orthogonality.
We may summarize the types of partitions in the following two tables,
the first one for $\target r$‑partitions of an $n$-set,
the second one for $\target r$‑partitions of a number $n$.
The number in each cell of the table is
the number of partitions of that type with $\target r$ blocks (called $\target r$‑partitions)
for a set $X$ or number $n$.
The entries for the two strong unordered cases are the definitions of those symbols.
| $r$‑partitions of an $\source n$-set $\source X$ | ordered | unordered $- \target {{} / S_Y}$ |
|---|---|---|
| weak | $\homst X\Set Y$ $\target r^{\source n}$ | $\homst X\Set Y \target{{} / S_Y}$ $\displaystyle{\target{\sum\limits_{k=1}^r} {\source X \brace \target k}}$ |
| strong | $\homst X\Surj Y$ $\displaystyle {\source X \brace \target r} \times \target{r!}$ | $$\homst X\Surj Y \target{{}/ S_Y}$$ $\displaystyle {\source X \brace \target r}$ |
| $\target r$‑partitions of a number $\source n$ $\source{S_X \backslash {}} -$ | ordered | unordered $- \target {{} / S_Y}$ |
|---|---|---|
| weak | $\source{S_X \backslash {}} \homst X\Set Y$ $\displaystyle {\source n+\target{r-1} \choose {\source n,\target{r-1}}}$ | $\source{S_X \backslash {}} \homst X\Set Y \target{{} / S_Y}$ $\displaystyle {\target{\sum\limits_{k=1}^r} P_{\source n, \target k}}$ |
| strong | $\source{S_X \backslash{}} \homst X\Surj Y$ $\displaystyle {\source{n-1} \choose \target{r-1}}$ | $\source{S_X \backslash {}} \homst X\Surj Y \target{{} / S_Y}$ $\displaystyle {P_{\source n,\target r}}$ |
Here is a small but nontrivial example, taking
$X=[4]=\{0,1,2,3\}$, so $n=4$, and
$Y=\{a,b\}$, so $r=2$,
thus considering $2$-partitions of a $4$-set.
| $2$‑partitions of the $4$-set $[4] = \{0,1,2,3\}$ | ordered | unordered |
|---|---|---|
| weak | $|\hom {[4]}\Set {\{a,b\}}|$ $2^4 = 16$ The kernel-partitions of the 16 functions from [4] to {a,b} (click here to see a figure showing those). | $|\hom {[4]}\Set {\{a,b\}} / S_{\{a,b\}}|$ $\displaystyle{{[4] \brace 1} + {[4] \brace 2}} = 1+7 = 8$ The weak 2-partition $$0,1,2,3 \mid {}$$ together with the seven unordered strong 2-partitions of $[4]$ shown below. |
| strong | $|\hom {[4]}\Surj {\{a,b\}}|$ $\displaystyle {{[4] \brace 2} \times 2! = 7 \times 2 = 14}$ Take each of the two possible orderings of the seven unordered strong 2-partitions of $[4]$, e.g.,$$\begin{array}{c} 0,1,2 \mid 3 \\ 3 \mid 0,1,2 \end{array}$$ | $|\hom {[4]}\Surj {\{a,b\}} / S_{\{a,b\}}|$ $\displaystyle {[4] \brace 2} = 7$ $$\left. \begin{array}{c} 0,1,2 \mid 3 \\ 0,1,3 \mid 2 \\ 0,2,3 \mid 1 \\ 1,2,3 \mid 0\end{array} \right\} (4)$$ $$\left. \begin{array}{c} 0,1 \mid 2,3 \\ 0,2 \mid 1,3 \\ 0,3 \mid 1,2 \end{array} \right\} (3)$$ |
| $2$‑partitions of the number $4$ | ordered | unordered |
|---|---|---|
| weak | $|S_4 \backslash \hom {[4]}\Set {\{a,b\}}|$ $\displaystyle {{4+2-1 \choose {4,2-1}}} = {{5 \choose {4,1}}} = 5$ $$\begin{array}{c}4+0 \\ 3+1 \\ 2+2 \\ 1+3 \\ 0+4\end{array}$$ | $|S_{[4]} \backslash \hom {[4]}\Set {\{a,b\}}/ S_{\{a,b\}}|$ $\displaystyle {P_{4,1} + P_{4,2}} = 1+2 = 3$ $$\begin{array}{c} 4+0 \\ 3+1 \\ 2+2\end{array}$$ |
| strong | $|S_{[4]} \backslash \hom {[4]}\Surj {\{a,b\}}|$ $\displaystyle {4-1 \choose 2-1} = {3 \choose 1} = 3$ $$\begin{array}{c} 3+1 \\ 2+2 \\ 1+3 \end{array}$$ | $|S_{[4]} \backslash \hom {[4]}\Surj {\{a,b\}}/ S_{\{a,b\}}|$ $\displaystyle {P_{4,2}} = 2$ $$\begin{array}{c} 3+1 \\ 2+2 \end{array}$$ |
Returning to the general case,
here is are some justifications for the entries in that table.
The entry for strong ordered set $k$‑partitions simply is
the number of strong unordered set $k$‑partitions times
the number of ways of ordering such a partition.
The entry for strong ordered number $k$‑partitions results from a simple representation.
Given a number $n$, write $n$ $1$'s in a row.
There are $n-1$ spaces between the $1$s.
Choose $k-1$ of those to insert a $+$ sign.
Add up the $1$s between $+$ signs.
Each ordered $k$‑partition of $n$ arises in one and only one such way.
E.g., there are $\binom{5}{2} = 10$ ordered $3$‑partitions of $6$:
The above display may contain more information than is really necessary. The column labeled $\{s,t\}$ contains all $\binom{5}{2} = 10$ ways of choosing two numbers from the set $\{1,2,3,4,5\}$ (which we view as numbering the spaces between the six $1$s). For now, skip the second and third columns. The final two column implement the process described before the display.
On the other hand, there are only $3$ unordered $3$‑partitions of $6$: \[ \begin{aligned} 4+1+1 \\ 3+2+1\\ 2+2+2\\ \end{aligned} \] so $P_{6,3}=3$.
\[ \begin{array}{ccc} \{(s,t)|1\le s\lt t\le 5\} & \substack {\longrightarrow \\ \longleftarrow} & \{(i,j,k)| 1\le i, 1\le j, 1\le k, i+j+k=6 \} \\ (s,t) & \mapsto & (s, t-s, 6-t) \\ (i,i+j) & \leftarrow & (i,j,k) \\ \end{array} \]
Often we are interested in the ordered strong number partitions of a number $n$, not just of a given size $k$, but of all possible sizes, from $1$ to $n$. There are $2^{n-1}$ such, and they can easily be parametrized by the $2^{n-1}$ binary numbers of length $n-1$. The trick, as above, is that each $n-1$-digit binary number encodes where to place $+$ signs in the $n-1$ spaces between the $1$s in a string of $n$ $1$s. Here are tables showing the bijections, for $n$ from $1$ to $5$.
\[\begin{array}{cccc}
&n=1&\\
\text{binary} & \text{string} && \text{partition} \\
\emptyset & 1 &= &1 \\
\end{array}\]
\[\begin{array}{cccc}
&n=2&\\\text{binary} & \text{string} && \text{partition} \\
0 & 11 &= &2\\
1 & 1+1 &= &1+1\\
\end{array}\]
\[\begin{array}{cccc}
&n=3&\\
\text{binary} & \text{string} && \text{partition} \\
00 & 111 &= &3\\
01 & 11+1 &= &2+1\\
10 & 1+11 &= &1+2\\
11 & 1+1+1 &= &1+1+1\\
\end{array}\]
\[\begin{array}{cccc}
&n=4&\\
\text{binary} & \text{string} && \text{partition} \\
000 & 1111 &= &4\\
001 & 111+1 &= &3+1\\
010 & 11+11 &= &2+2\\
011 & 11+1+1 &= &2+1+1\\
100 & 1+111 &= &1+3\\
101 & 1+11+1 &= &1+2+1\\
110 & 1+1+11 &= &1+1+2\\
111 & 1+1+1+1 &= &1+1+1+1\\
\end{array}\]
\[\begin{array}{cccc}
&n=5&\\
\text{binary} & \text{string} && \text{partition} \\
0000 & 11111 &= &5\\
0001 & 1111+1 &= &4+1\\
0010 & 111+11 &= &3+2\\
0011 & 111+1+1 &= &3+1+1\\
0100 & 11+111 &= &2+3\\
0101 & 11+11+1 &= &2+2+1\\
0110 & 11+1+11 &= &2+1+2\\
0111 & 11+1+1+1 &= &2+1+1+1\\
1000 & 1+1111 &= &1+4\\
1001 & 1+111+1 &= &1+3+1\\
1010 & 1+11+11 &= &1+2+2\\
1011 & 1+11+1+1 &= &1+2+1+1\\
1100 & 1+1+111 &= &1+1+3\\
1101 & 1+1+11+1 &= &1+1+2+1\\
1110 & 1+1+1+11 &= &1+1+1+2\\
1111 & 1+1+1+1+1 &= &1+1+1+1+1\\
\end{array}\]
Weak ordered number partitions
Weak ordered number partitions play an important role in mathematics.Here is a look at some alternate representations for them,
one of which allows them to be counted easily.
We consider the case of weak ordered $k$-partitions of a number $n$.
There are in general ${n+k-1 \choose n} = {n+k-1 \choose k-1} = {n+k-1 \choose n,\,k-1}$ such partitions.
For example, here is a table showing three different ways of representing the ${4+3-1 \choose 4,\,3-1} = {6 \choose 4,\,2} = 15$ weak ordered $3$-partitions of $n=4$.
\[\begin{array}{ccl}
\text{string} & \text{partition} & \text{monomial}\\[2ex]
++1111 & 0+0+4 & c^4 \\
+1+111 & 0+1+3 & bc^3 \\
+11+11 & 0+2+2 & b^2c^2 \\
+111+1 & 0+3+1 & b^3c \\
+1111+ & 0+4+0 & b^4 \\[1ex]
1++111 & 1+0+3 & ac^3 \\
1+1+11 & 1+1+2 & abc^2 \\
1+11+1 & 1+2+1 & ab^2c \\
1+111+ & 1+3+0 & ab^3 \\[1ex]
11++11 & 2+0+2 & a^2c^2 \\
11+1+1 & 2+1+1 & a^2bc \\
11+11+ & 2+2+0 & a^2b^2 \\[1ex]
111++1 & 3+0+1 & a^3c \\
111+1+ & 3+1+0 & a^3b \\[1ex]
1111++ & 4+0+0 & a^4 \\
\end{array}\]
Strong unordered set partitions (i.e., just "partitions")
Rather than giving a closed form for these, such as we have for $n \choose k$, we give a recursive formula for them: $${n+1 \brace k} = {n \brace k-1} + k{n \brace k}$$ This is easily seen to be correct:If a set with $n+1$ elements has a $k$-partition,
either the $n+1$st element stands alone, in which case the other $k-1$ blocks of the partition form a $k-1$-partition of the other $n$ elements,
or it is added to (an arbitrary) one of the $k$ blocks of a $k$-partition of the other $n$ elements.
Using that recursive formula,
we may form a triangular table for these partition numbers,
analogous to Pascal’s triangle for the binomial coefficients.
Perhaps a good name for this triangle is Stirling’s partition table
(vice Stirling’s cycle table). \[\bbox[navajowhite,10px,border:4px groove red]{\begin{array}{ccccccc} \displaystyle{n \brace k} & \displaystyle{\brace 0} & \displaystyle{\brace 1} & \displaystyle{\brace 2} & \displaystyle{\brace 3} & \displaystyle{\brace 4} & \displaystyle{\brace 5}\\ \displaystyle{0 \brace } & 1\\ \displaystyle{1 \brace } & 0 & 1\\ \displaystyle{2 \brace } & 0 & 1={2 \choose 2} & 1\\ \displaystyle{3 \brace } & 0 & 1 & 3={3 \choose 2}=2^2-1 & 1\\ \displaystyle{4 \brace } & 0 & 1 & 7=2^3-1 & 6 ={4 \choose 2} & 1\\ \displaystyle{5 \brace } & 0 & 1 & 15=2^4-1 & 25 & 10={5 \choose 2} & 1\\ \end{array}}\] The formulas ${n \brace 2} = {(2^n -2)\over 2} = 2^{n-1}-1$ and ${n \brace n-1} = {n \choose 2}$ are easily seen.
What is the relation between ordered and unordered partitions of numbers and sets?
There is an extensive theory on that, of course, but a small example may provide a useful introduction.
The following table gives the (strong) partitions, ordered and unordered, of the number $4$ and, for the set $[4] \equiv \{1,2,3,4\}$, the number of elements of its stabilizer group and its orbit space for both unordered set partitions and unordered cycles.
The table’s bottom line gives the general form for the ``type'' of a partition, and the sizes of its corresponding stabilizers and orbits. \[\bbox[navajowhite,10px,border:6px groove red]{\begin{array}{ccccccccc} \text{type (ordered)} & \text{ordered} \# \text{partition} & \text{unordered} \# \text{partition} & \text{type (unordered)} & \text{template} & \text{partition stabilizer} & \text{partition orbit (partitions)} & \text{cycle stabilizer} & \text{cycle orbit (cycles)} \\[2ex] 000 & 4 & 4 & 4^1 & (\cdotp\cdotp\cdotp\cdotp) & (4!)^1 & 1 & 4^1 & 6 \\ 001 & 3+1 & 3+1 & 1^13^1 & (\cdotp)(\cdotp\cdotp\cdotp) & (3!)^1 & 4 & 3^1 & 8 \\ 010 & 2+2 & 2+2 & 2^2 & (\cdotp\cdotp)(\cdotp\cdotp) & 2!(2!)^2 & 3 & 2!2^2 & 3 \\ 011 & 2+1+1 & 2+1+1 & 1^22^1 & (\cdotp)(\cdotp)(\cdotp\cdotp) & 2!(2!)^1 & 6 & 2!2^1 & 6 \\ 100 & 1+3 \\ 101 & 1+2+1 \\ 110 & 1+1+2 \\ 111 & 1+1+1+1 & 1+1+1+1 & 1^4 & (\cdotp)(\cdotp)(\cdotp)(\cdotp) & 4! & 1 & 4! & 1 \\[3ex] &&& 1^{b_1}2^{b_2}\cdots i^{b_i}\cdots n^{b_n} && b_1!(1!)^{b_1} b_2!(2!)^{b_2} b_3!(3!)^{b_3} \cdots b_i!(i!)^{b_i} \cdots b_n!(n!)^{b_n} &n!/\text{(partition_stabilizer)} & b_1!1^{b_1} b_2!2^{b_2} b_3!3^{b_3} \cdots b_i!i^{b_i} \cdots b_n!n^{b_n} & n!/\text{(cycle_stabilizer)} \\ \end{array}}\] The appearances of $(1!)^{b_1}$ and $1^{b_1}$ are of course entirely unnecessary,
as each is equal to $1$;
they are there just to show the uniformity of the product of which they are a part.
No comments:
Post a Comment