Set of unordered integer partitions: Difference between revisions

Latest revision as of 23:05, 21 May 2012

Definition

Let $n$ be a nonnegative integer. An unordered integer partition of $n$ is an additive partition of $n$ into positive integers, without any specific ordering on the parts. The set of unordered integer partitions of $n$ , sometimes denoted $P(n)$ , is the set of all such unordered integer partitions.

The cardinality of this set, also termed the number of unordered integer partitions or partition number, is denoted $p(n)$ . We have:

$p(n)=O(e^{\pi {\sqrt {2n/3}}})$ .

The set of unordered integer partitions figures in the following ways:

It is in canonical bijection with the set of conjugacy classes in the symmetric group of degree $n$ . The bijection is via the cycle type map, and it is a bijection because cycle type determines conjugacy class.
It is in canonical bijection with the set of irreducible representations over the rationals (and also, over any algebraic extension of the rationals) of the symmetric group of degree $n$ . Further information: Linear representation theory of symmetric groups
For any fixed prime number $p$ , it is in canonical bijection with the set of isomorphism classes of abelian groups of order $p^{n}$ , via the structure theorem for finitely generated abelian groups.

Examples

We have the following small values:

$n$	$p(n)$	List of partitions	Application to conjugacy class structure of symmetric group	Application to irreducible representation structure of symmetric group	Application to abelian groups of prime power order
0	1	The empty partition	trivial group has unique conjugacy class	trivial group has unique conjugacy class	only the trivial group
1	1	The trivial partition $1$ .	trivial group has unique conjugacy class	trivial group has unique conjugacy class	the unique group of prime order, see equivalence of definitions of group of prime order
2	2	$2$ , $1+1$	link	link	classification of groups of prime-square order
3	3	$3$ , $2+1$ , $1+1+1$	link	link	link
4	5	$4$ , $3+1$ , $2+2$ , $2+1+1$ , $1+1+1+1$	link	link	link
5	7	$5$ , $4+1$ , $3+2$ , $3+1+1$ , $2+2+1$ , $2+1+1+1$ , $1+1+1+1+1$	link	link	link
6	11	Too long to list	link	link
7	15	Too long to list	link	link
8	22	Too long to list	link	link
9	30	Too long to list
10	42	Too long to list
11	56	Too long to list
12	77	Too long to list
13	101	Too long to list
14	135	Too long to list
15	176	Too long to list
16	231	Too long to list
17	297	Too long to list
18	385	Too long to list
19	490	Too long to list
20	627	Too long to list
21	792	Too long to list
22	1002	Too long to list
23	1255	Too long to list
24	1575	Too long to list

@@ Line 3: / Line 3: @@
 Let <math>n</math> be a nonnegative integer. An ''unordered integer partition'' of <math>n</math> is an additive partition of <math>n</math> into positive integers, without any specific ordering on the parts. The '''set of unordered integer partitions''' of <math>n</math>, sometimes denoted <math>P(n)</math>, is the set of all such unordered integer partitions.
-The cardinality of this set, also termed the ''number of unordered integer partitions'', is denoted <math>p(n)</math>. We have:
+The cardinality of this set, also termed the '''number of unordered integer partitions''' or '''partition number''', is denoted <math>p(n)</math>. We have:
 <math>p(n) = O(e^{\pi\sqrt{2n/3}})</math>.
@@ Line 11: / Line 11: @@
 * It is in canonical bijection with the set of conjugacy classes in the symmetric group of degree <math>n</math>. The bijection is via the [[cycle type]] map, and it is a bijection because [[cycle type determines conjugacy class]].
 * It is in canonical bijection with the set of irreducible representations over the rationals (and also, over any algebraic extension of the rationals) of the symmetric group of degree <math>n</math>. {{further|[[Linear representation theory of symmetric groups]]}}
+* For any fixed prime number <math>p</math>, it is in canonical bijection with the set of isomorphism classes of [[abelian group of prime power order|abelian groups of order]] <math>p^n</math>, via the [[structure theorem for finitely generated abelian groups]].
 ==Examples==
 We have the following small values:
-{| class="wikitable" border="1"
+{| class="sortable" border="1"
-! <math>n</math> !! <math>p(n)</math> !! List of partitions
+! <math>n</math> !! <math>p(n)</math> !! List of partitions !! Application to conjugacy class structure of symmetric group !! Application to irreducible representation structure of symmetric group !! Application to abelian groups of prime power order
+|-
+| 0 || 1 || The empty partition || [[trivial group]] has unique conjugacy class || [[trivial group]] has unique conjugacy class || only the [[trivial group]]
+|-
+| 1 || 1 || The trivial partition <math>1</math>. || [[trivial group]] has unique conjugacy class || [[trivial group]] has unique conjugacy class || the unique [[group of prime order]], see [[equivalence of definitions of group of prime order]]
+|-
+| 2 || 2 || <math>2</math>, <math>1 + 1</math> || [[Element structure of cyclic group:Z2#Interpretation as symmetric group of degree two|link]] || [[Linear representation theory of cyclic group:Z2#Interpretation as symmetric group|link]] || [[classification of groups of prime-square order]]
+|-
+| 3 || 3 || <math>3</math>, <math>2 + 1</math>, <math>1 + 1 + 1</math> || [[Element structure of symmetric group:S3#Interpretation as symmetric group|link]] || [[Linear representation theory of symmetric group:S3#Interpretation as symmetric group|link]] || [[Classification of groups of prime-cube order#The three abelian groups|link]]
+|-
+| 4 || 5 || <math>4</math>, <math>3 + 1</math>, <math>2 + 2</math>, <math>2 + 1 + 1</math>, <math>1 + 1 + 1 + 1</math> || [[Element structure of symmetric group:S4#Interpretation as symmetric group|link]] || [[Linear representation theory of symmetric group:S4#Interpretation as symmetric group|link]] || [[Classification of groups of prime-fourth order#The five abelian groups|link]]
+|-
+| 5 || 7 || <math>5</math>, <math>4 + 1</math>, <math>3 + 2</math>, <math>3 + 1 + 1</math>, <math>2 + 2 + 1</math>, <math>2 + 1 + 1 + 1</math>, <math>1 + 1 + 1 + 1 + 1</math> || [[Element structure of symmetric group:S5#Interpretation as symmetric group|link]] || [[Linear representation theory of symmetric group:S5#Interpretation as symmetric group|link]] || [[Classification of groups of prime-fifth order#The seven abelian groups|link]]
+|-
+| 6 || 11 || Too long to list || [[element structure of symmetric group:S6|link]] || [[linear representation theory of symmetric group:S6|link]] ||
+|-
+| 7 || 15 || Too long to list || [[element structure of symmetric group:S7|link]] || [[linear representation theory of symmetric group:S7|link]] ||
+|-
+| 8 || 22 || Too long to list || [[element structure of symmetric group:S8|link]] || [[linear representation theory of symmetric group:S8|link]]||
+|-
+| 9 || 30 || Too long to list || || ||
+|-
+| 10 || 42 || Too long to list || || ||
+|-
+| 11 || 56 || Too long to list || || ||
+|-
+| 12 || 77 || Too long to list || || ||
+|-
+| 13 || 101 || Too long to list || || ||
 |-
-| <math>0</math> || <math>1</math> || The empty partition
+| 14 || 135 || Too long to list || || ||
 |-
-| <math>1</math> || <math>1</math> || The trivial partition <math>1</math>.
+| 15 || 176 || Too long to list || || ||
 |-
-| <math>2</math> || <math>2</math> || <math>2</math>, <math>1 + 1</math>.
+| 16 || 231 || Too long to list || || ||
 |-
-| <math>3</math> || <math>3</math> || <math>3<math>, <math>2 + 1</math>, <math>1 + 1 + 1</math>.
+| 17 || 297 || Too long to list || || ||
 |-
-| <math>4<math> || <math>5</math> || <math>4<math>, <math>3 + 1</math>, <math>2 + 2</math>, <math>2 + 1 + 1</math>, <math>1 + 1 + 1 + 1</math>.
+| 18 || 385 || Too long to list || || ||
 |-
-| <math>5<math> || <math>7</math> || <math>5</math>, <math>4 + 1</math>, <math>3 + 2</math>, <math>3 + 1 + 1</math>, <math>2 + 2 + 1</math>, <math>2 + 1 + 1 + 1</math>, <math>1 + 1 + 1 + 1 + 1</math>.
+| 19 || 490 || Too long to list || || ||
 |-
-| <math>6</math> || <math>11</math> || Too long to list.
+| 20 || 627 || Too long to list || || ||
 |-
-| <math>7</math> || <math>15</math> || Too long to list.
+| 21 || 792 || Too long to list || || ||
 |-
-| <math>8</math> || <math>22</math> || Too long to list.
+| 22 || 1002 || Too long to list || || ||
 |-
-| <math>9</math> || <math>30</math> || Too long to list.
+| 23 || 1255 || Too long to list || || ||
 |-
-| <math>10</math> || <math>42</math> || Too long to list.
+| 24 || 1575 || Too long to list || || ||
 |}