Partition (combinatorics)

Definition

A partition of [ilmath]n[/ilmath] having [ilmath]m[/ilmath] parts 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:

• [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.

• 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]

Equality of partitions

Two partitions, [ilmath]\pi[/ilmath] and [ilmath]\pi'[/ilmath] are considered the same or equal if they:

1. Have the same number of parts and sum to the same number (are both [ilmath]m[/ilmath]-part partitions of [ilmath]n[/ilmath]) and
2. [ilmath]\forall i\in\{1,2,\cdots,m\}[\pi_i=\pi'_i][/ilmath]

and we write [ilmath]\pi=\pi'[/ilmath]

See also

• Composition (combinatorics)
• Monomial symmetric function - the motivation for these partitions