Partition (combinatorics)
Contents
Definition
A partition of [ilmath]n[/ilmath] having [ilmath]m[/ilmath] parts[1] is an unordered collection of [ilmath]m[/ilmath] integers that sum to [ilmath]n[/ilmath].
- Examples: [ilmath]6[/ilmath] may be partitioned into [ilmath]3[/ilmath] parts, [ilmath]3[/ilmath], [ilmath]2[/ilmath] and [ilmath]1[/ilmath]
Notation
Of partitions
An [ilmath]m[/ilmath]-part partition of [ilmath]n[/ilmath] is represented by a sequence:[1]
- [ilmath]\pi=[\pi_1,\pi_2,\cdots,\pi_n][/ilmath] which is chosen such that [ilmath]\pi_1\ge\pi_2\ge\cdots\ge\pi_m > 0[/ilmath]
As the order is insignificant this ordering makes partitions easy to compare by making identical partitions easy to see.
When the same number occurs multiple times the notation of raising to the power of the number of consecutive terms is used to save writing.[1]
- For example: in the [ilmath]3[/ilmath] part partition of [ilmath]6[/ilmath]: [ilmath][4,1,1][/ilmath] it is standard to write [ilmath][4,1^2][/ilmath] instead
Signifying [ilmath]\pi[/ilmath] is a partition of [ilmath]n[/ilmath]
To signify that [ilmath]\pi[/ilmath] is a partition of [ilmath]n[/ilmath] we may write:
- [ilmath]\pi\vdash n[/ilmath][1]
Equality of partitions
Two partitions, [ilmath]\pi[/ilmath] and [ilmath]\pi'[/ilmath] are considered the same or equal[1] if they:
- Have the same number of parts and sum to the same number (are both [ilmath]m[/ilmath]-part partitions of [ilmath]n[/ilmath]) and
- [ilmath]\forall i\in\{1,2,\cdots,m\}[\pi_i=\pi'_i][/ilmath]
and we write [ilmath]\pi=\pi'[/ilmath]
