Partition function

This article describes the partition function in math. For the partition function in statistical physics see partition function .

The partition functions indicate the number of possibilities to break down positive, whole numbers into positive, whole summands . Usually one looks at the decompositions without considering the order. Each such decomposition is called a (disordered) number partition in combinatorics, or sometimes a partition for short . The determination of all number partitions for a certain (large) natural number is an important problem in both theoretical and practical computer science . See the article Partitioning Problem .

The partition function without constraints (number of unordered number partitions of ) is noted as , sometimes also as , and is sequence A000041 in OEIS . There are a number of functions in which additional conditions are placed on the summands, for example that each summand may only appear once ( strict number partitions ), this variant is also called a partition function, sometimes also called a strict partition function, noted as or and is sequence A000009 in OEIS . ${\displaystyle n}$ ${\displaystyle P(n)}$ ${\displaystyle p(n)}$ ${\displaystyle Q(n)}$ ${\displaystyle q(n)}$

Partition function P (n) in a semi-logarithmic representation

With a number theoretic function derived from the partition function, the number of isomorphism types for the finite Abelian groups can be given. ${\displaystyle P(n)}$

Properties of P (n)

Sample values

Example values ​​of P (n) and associated number partitions

n	P (n)	Payment partitions
0	1	() empty partition / empty sum
1	1	(1)
2	2	(1 + 1), (2)
3	3	(1 + 1 + 1), (1 + 2), (3)
4th	5	(1 + 1 + 1 + 1), (1 + 1 + 2), (2 + 2), (1 + 3), (4)
5	7th	(1 + 1 + 1 + 1 + 1), (1 + 1 + 1 + 2), (1 + 2 + 2), (1 + 1 + 3), (2 + 3), (1 + 4), (5)
6th	11	(1 + 1 + 1 + 1 + 1 + 1), (1 + 1 + 1 + 1 + 2), (1 + 1 + 2 + 2), (2 + 2 + 2), (1 + 1 + 1 +3), (1 + 2 + 3), (3 + 3), (1 + 1 + 4), (2 + 4), (1 + 5), (6)

The values ​​then increase quickly (see sequence A000041 in OEIS ):

${\displaystyle {\begin{array}{lcr|lcr|lcr}P(7)&=&15&P(45)&=&89\,134\\P(8)&=&22&P(100)&=&190\,569\,292&\\P(9)&=&30&P(200)&\approx &3{,}973\cdot 10^{12}\\P(10)&=&42&P(1000)&\approx &2{,}406\cdot 10^{31}\end{array}}}$

Recursive representation

Example values ​​of P (n, k)

P nk)		k
		1	2	3	4th	5	6th	7th	8th	9	10
n	1	1
	2	1	1
	3	1	1	1
	4th	1	2	1	1
	5	1	2	2	1	1
	6th	1	3	3	2	1	1
	7th	1	3	4th	3	2	1	1
	8th	1	4th	5	5	3	2	1	1
	9	1	4th	7th	6th	5	3	2	1	1
	10	1	5	8th	9	7th	5	3	2	1	1

Describes the number of possibilities to break down the positive whole number into exactly positive whole summands, then applies ${\displaystyle P(n,k)}$ ${\displaystyle n}$ ${\displaystyle k}$

${\displaystyle P(n)=\sum _{i=1}^{n}P(n,i)}$,

where the numbers recursively over and as well as ${\displaystyle P(n,k)}$ ${\displaystyle P(n,1)=1}$ ${\displaystyle P(n,n)=1}$

${\displaystyle P(n+k,k)=\sum _{j=1}^{k}P(n,j)}$

or directly through

${\displaystyle P(n,k)=P(n-k,k)+P(n-1,k-1)}$

let determine.

Asymptotic behavior

Relative error of the approximation function

${\displaystyle n}$	5	10	100	250	500
${\displaystyle {\frac {E(n)-P(n)}{P(n)}}}$ in %	27.7	14.5	4.57	2.86	2.01

For large values ​​of Godfrey Harold Hardy and S. Ramanujan’s formula gives ${\displaystyle n}$

${\displaystyle P(n)\sim E(n)={\frac {\exp \left(\pi {\sqrt {2n/3}}\right)}{4n{\sqrt {3}}}}}$

a good approximation for . In particular, this means that the number of decimal places is roughly proportional to the square root : P (100) has 9 places ( ), P (1000) has 32 places ( ). ${\displaystyle P(n)}$ ${\displaystyle P(n)}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {100}}=10}$ ${\displaystyle {\sqrt {1000}}\approx 31{,}6}$

${\displaystyle P(4n)}$has about twice as many digits as . ${\displaystyle P(n)}$

Generating function

A simple generating function for the partition function is obtained from the multiplicative inverse of Euler's function

${\displaystyle \sum _{n=0}^{\infty }P(n)x^{n}=\prod _{k=1}^{\infty }{\frac {1}{1-x^{k}}}}$

You get

${\displaystyle f(x)={\frac {1}{\prod _{k=1}^{\infty }(1-x^{k})}}=1+1x+2x^{2}+3x^{3}+5x^{4}+...}$

d. that is, the coefficients of the series representation correspond to the values ​​of . ${\displaystyle f(x)}$ ${\displaystyle P(n)}$

Connection with the pentagonal numbers

The coefficients of Euler's function ( Euler's product ) ${\displaystyle c(n)}$

${\displaystyle \prod _{k=1}^{\infty }(1-x^{k})\;=\sum _{m=-\infty }^{\infty }(-1)^{m}\cdot x^{\frac {m(3m-1)}{2}}=\sum _{n=0}^{\infty }c(n)\cdot x^{n}}$

can be with the pentagonal number theorem of Leonhard Euler easily calculated explicitly. The result is sequence A010815 in OEIS and it always applies ${\displaystyle c(n)}$ ${\displaystyle c(n)\in \{-1,0,1\}.}$

From the fact that Euler's function is multiplicatively inverse to the generating function of the partition function, it follows that for the discrete convolution and holds ${\displaystyle c\ast P}$ ${\displaystyle n\in \mathbb {N} _{0}}$

${\displaystyle (c\ast P)(n)=\sum _{r\in \mathbb {Z} }c(r)\cdot P(n-r)=\sum _{r=0}^{n}P(r)\cdot c(n-r)={\begin{cases}1\;(n=0)\\0\;(n\neq 0).\end{cases}}}$

The summation only has to be extended over, since both sequences as coefficient sequences of their respective function are equal to zero in negative places. ${\displaystyle r\in \{0,1,\ldots n\}}$

Recursion formula from the pentagonal number set

From the convolutional relation to the coefficients given in the previous subsection it follows for the recursion formula ${\displaystyle c(n)}$ ${\displaystyle n\in \mathbb {N} \setminus \{0\}}$

${\displaystyle P(n)=-\sum _{r=1}^{n}c(r)\cdot P(n-r)=P(n-1)+P(n-2)-P(n-5)-P(n-7)+\cdots }$

for the partition function.

Calculation with analytical number theory

The formula derived from the generating function provides a possibility for direct calculation

${\displaystyle P(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n)\;{\sqrt {k}}\;{\frac {\mathrm {d} }{\mathrm {d} n}}\left({\frac {\sinh \left({\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}\right)}{\sqrt {n-{\frac {1}{24}}}}}\right)}$

With

${\displaystyle A_{k}(n)=\!\!\!\!\sum _{0\leq m<k \atop \operatorname {ggT} (m,k)=1}\!\!\!\!\exp \left\{{\frac {\pi i}{k}}\left[s(m,k)-2nm\right]\right\}.}$

and

${\displaystyle s(m,k)=\sum _{j=1}^{k-1}j\left({\frac {mj}{k}}-\left\lfloor {\frac {mj}{k}}\right\rfloor -{\frac {1}{2}}\right)}$

which Hans Rademacher , building on the findings of S. Ramanujan and Godfrey Harold Hardy , found.

Calculation with algebraic number theory

An algebraic, closed form of that does without infinite series expansion was published in 2011 by Jan Hendrik Bruinier and Ken Ono . More precisely, Bruinier and Ono give a function so that for every natural number there is a finite number of algebraic numbers with ${\displaystyle P(n)}$ ${\displaystyle Q}$ ${\displaystyle n}$ ${\displaystyle \alpha _{1},\alpha _{2},\ldots ,\alpha _{m}}$

${\displaystyle P(n)={\frac {1}{24n-1}}\left(Q(\alpha _{1})+Q(\alpha _{2})+\ldots +Q(\alpha _{m})\right)}$

let find. In addition, all values ​​are also algebraic. ${\displaystyle Q(\alpha _{i})}$

This theoretical result only leads to a faster calculation of the partition function in special cases (e.g. via congruences that can be derived from it).

Congruences

${\displaystyle n}$	${\displaystyle P(n)}$	Congruences
1	1
2	2
3	3
4th	5	mod 5
5	7th	mod 7
6th	11	mod 11
7th	15th
8th	22nd
9	30th	mod 5
10	42
11	56
12	77	mod 7
13	101
14th	135	mod 5
15th	176
16	231
17th	297	mod 11
18th	385
19th	490	mod 5 and 7
20th	627

Ramanujan discovered a law in his studies. If you start with 4 and jump by 5, you always get multiples of the jump number 5 as the decomposition numbers. If you start at 6 and jump by 11, you get multiples of 11. Ramanujan discovered other similar relationships, also called congruences, when he examined the powers of the prime numbers 5, 7 and 11 and their products as jump numbers. The American number theorist Ken Ono was able to show that there are congruences for all prime numbers greater than 3. Ono could not prove whether this also applies to the two smallest prime numbers, 2 and 3, and their multiples. The following congruences go back to Ramanujan:

${\displaystyle {\begin{aligned}P(5k+4)&\equiv 0\mod 5\\P(7k+5)&\equiv 0\mod 7\\P(11k+6)&\equiv 0\mod {11}\end{aligned}}}$

AOL Atkin found the following congruence:

${\displaystyle P(17303k+237)\equiv 0\mod {13}}$

Ferrers diagrams

→ In the article Young-Tableau a similar type of diagram is described in detail, which, like the Ferrers diagrams described here, uniquely defines a partition and is mainly used in representation theory.

The number partition can be represented by the following diagram, called the Ferrers diagram . These diagrams were named in honor of Norman Macleod Ferrers. ${\displaystyle 6+4+3+1=14}$

6 + 4 + 3 + 1

The 14 counties are lined up in four columns for the four summands of the partition, the columns from left to right never higher will. The reverse convention is also often used, where the columns of circles are on the baseline and never lower from left to right . The 5 partitions of 4 are shown below as Ferrers diagrams:

4th	=	3 + 1	=	2 + 2	=	2 + 1 + 1	=	1 + 1 + 1 + 1

Conjugated partition

If we mirror the diagram of the partition on its main diagonal, we get another partition of 14: ${\displaystyle 6+4+3+1=14}$

	↔
6 + 4 + 3 + 1	=	4 + 3 + 3 + 2 + 1 + 1

So by turning rows into columns, we get the partition . It is called the partition to be conjugated . Among the partitions of 4 are and ; and conjugate to each other. Partitions such as those that are conjugated to themselves, whose Ferrers diagram is axisymmetric to its main diagonal, are particularly interesting . ${\displaystyle 4+3+3+2+1+1=14}$ ${\displaystyle 6+4+3+1=14}$ ${\displaystyle 1+1+1+1=4}$ ${\displaystyle 4=4}$ ${\displaystyle 3+1}$ ${\displaystyle 2+1+1}$ ${\displaystyle 3+2+1=6}$

• The number of partitions of conjugated to itself is equal to the number of partitions of in different, odd summands. ${\displaystyle n}$ ${\displaystyle n}$

Idea of ​​proof: The crucial observation is that any column in the Ferrers diagram that contains an odd number of circles can be "folded" in the middle to produce part of a symmetrical diagram:

↔

From this, as shown in the following example, one obtains a bijective mapping of the partitions with different, odd summands to the partitions that are conjugated to themselves:

	↔
9 + 7 + 3	=	5 + 5 + 4 + 3 + 2

The following statements, for example, can be proven with similar methods: The number of partitions of with at most summands is the same ${\displaystyle n}$ ${\displaystyle k}$

1. the number of partitions of where no summand is greater than . ${\displaystyle n}$ ${\displaystyle k}$
2. the number of partitions of with exactly summands. ${\displaystyle n+k}$ ${\displaystyle k}$

Formalization

The Ferrers diagrams are an intuitive aid with which connections between disordered partitions can be clearly recognized and understood. They are unsuitable for computer generation and compact storage, so "formalized" representations also play an important role for these diagrams:

1. A number partition of (“diagram of the order ”) is a tuple (“number of columns = columns”) with the property , is called its number of columns . (In order to include the "empty" partition here, you have to set for , it is then the empty sum and always results in 0.) ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n}$ ${\displaystyle C}$ ${\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}\in \left(\mathbb {N} \setminus \{0\}\right)^{C}}$ ${\displaystyle \sum \nolimits _{k=1}^{C}i_{k}=n}$ ${\displaystyle C}$ ${\displaystyle ()=\operatorname {()} _{k=1}^{0}}$ ${\displaystyle C=0}$ ${\displaystyle \left(\mathbb {N} \setminus \{0\}\right)^{0}:=\{()\}}$
2. The number is called the number of rows (= "rows") of ${\displaystyle R=R(\pi )=\max(0,\max\{i_{k}:1\leq k\leq C\})}$ ${\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}.}$
3. A number partition is "valid" if for always applies, for valid partitions is . ${\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}}$ ${\displaystyle 1\leq k<C}$ ${\displaystyle i_{k}\geq i_{k+1}}$ ${\displaystyle C>0}$ ${\displaystyle R(\pi )=i_{1}}$
4. A pay partition is called “strict” if it is always . Strict partitions are always valid. ${\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}}$ ${\displaystyle 1\leq k<C}$ ${\displaystyle i_{k}>i_{k+1}}$
5. The conjugate partition of a valid partition is defined by . It is valid. ${\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}}$ ${\displaystyle {\overline {\pi }}=\operatorname {\left(\max\{k:\,{i_{k}}+1-r>0\land 1\leq k\leq C\}\right)} _{r=1}^{R(\pi )}}$

Alternatively, and closer to the graphical representation of the Ferrers diagrams each partition can be described as - matrix with entries from represent wherein means that in Ferrers diagram in series in column a circuit is, that there is not a circle. The conjugate of a partition then has the transposed matrix of the original partition as its matrix . ${\displaystyle R\times C}$ ${\displaystyle (a_{jk})}$ ${\displaystyle \{0,1\}}$ ${\displaystyle a_{jk}=1}$ ${\displaystyle j}$ ${\displaystyle k}$ ${\displaystyle a_{jk}=0}$

variants

Partitions with given smallest summands, p (k, n)

If the partition function is modified, it is required that the smallest summand in the number partition is greater than or equal to . The number of such partitions is noted as. The "normal" partition function is thus This modification is consequence A026807 in OEIS . ${\displaystyle k}$ ${\displaystyle p(k,n)}$ ${\displaystyle P(n)=p(1,n).}$ ${\displaystyle p(k,n)}$

Example values ​​for p (k, n)

Example values ​​of p (k, n)

p (k, n)		k
		1	2	3	4th	5	6th	7th	8th	9	10
n	1	1
	2	2	1
	3	3	1	1
	4th	5	2	1	1
	5	7th	2	1	1	1
	6th	11	4th	2	1	1	1
	7th	15th	4th	2	1	1	1	1
	8th	22nd	7th	3	2	1	1	1	1
	9	30th	8th	4th	2	1	1	1	1	1
	10	42	12	5	3	2	1	1	1	1	1

For the values ​​of for small numbers, see the second table on the right. Individual values ​​are: ${\displaystyle p(k,n)}$

${\displaystyle {\begin{alignedat}{4}p(1,4)&=5,&p(2,8)&=7,&p(3,12)&=9,\\p(4,16)&=11,\quad &p(5,20)&=13,\quad &p(6,24)&=16.\end{alignedat}}}$

Recursion formula for p (k, n) and P (n)

It applies

${\displaystyle p(k,n)=1+\sum _{j=k}^{\lfloor {\frac {n}{2}}\rfloor }p(j,n-j);\;p(n,n)=1}$

where is the Gaussian bracket . With this recursion formula , all values ​​of and thus also for can be calculated. Note, however, that with the recursion formula for the calculation of all values ​​of for must be known or must be calculated with. ${\displaystyle \lfloor n\rfloor }$ ${\displaystyle p(k,n)}$ ${\displaystyle P(n)=p(1,n)}$ ${\displaystyle p(1,N)}$ ${\displaystyle p(k,n)}$ ${\displaystyle 1\leq k<\lfloor {\frac {N}{2}}\rfloor ;\;1<n<N}$

Ordered payment partitions

If the summands in a number partition are viewed as an ordered set, i.e. if the order in the sum is taken into account, then one speaks of an ordered number partition . The following number functions are considered here, for which no formula symbol is generally used.

• ${\displaystyle g(k,n)}$is the number of representations of the sum of exactly positive whole numbers taking into account the order of the summands, i.e. the number of solutions to the equation ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle (i_{1},i_{2},\ldots ,i_{k})\in \left(\mathbb {N} \setminus \{0\}\right)^{k}}$ ${\displaystyle i_{1}+i_{2}+\cdots +i_{k}=n.}$

• It applies . ${\displaystyle g(k,n)={\binom {n-1}{k-1}}}$
• The number can be interpreted geometrically as the number of points with positive, integer coordinates on the hyperplane with the equation im - dimensional real affine point space . ${\displaystyle x_{1}+x_{2}+\cdots +x_{k}=n}$ ${\displaystyle k}$
• The sequence is the sequence of the numbers in Pascal's triangle , read in sequence, sequence A007318 in OEIS . ${\displaystyle g(1,1),g(1,2),g(2,2),g(1,3),g(2,3),g(3,3),g(1,4),\ldots }$

• ${\displaystyle G(n)}$is the number of representations of the sum of at most positive whole numbers, taking into account the order of the summands. It is sequence A000079 in OEIS and it applies ${\displaystyle n}$ ${\displaystyle n}$

• ${\displaystyle G(n)=\sum _{j=1}^{n}g(j,n)}$,
• the recursion formula and ${\displaystyle G(n)=1+\sum _{i_{1}=1}^{n-1}G(n-i_{1}),\,n\geq 1}$
• ${\displaystyle G(n)=2^{n-1},n\geq 1}$which can easily be proven with complete induction from the recursion formula.

Obviously the function, which is easy to calculate, provides a (very rough) upper bound for the partition function: ${\displaystyle G(n)}$

${\displaystyle P(n)<G(n)=2^{n-1},\ n\geq 3.}$

Strict partitions and related constraints

The number partitions of , which consist of nothing but uneven summands, can be mapped bijectively onto the strict number partitions, that is, the number partitions with nothing but different summands . This fact was proven by Euler as early as 1748 . It is a special case of Glaisher's theorem named after James Whitbread Lee Glaisher : ${\displaystyle n}$

The number of partitions of , for which no summand is divisible by , equals the number of partitions of , in which no matching summands occur. ${\displaystyle n}$ ${\displaystyle d\in \mathbb {N} \setminus \{0,1\}}$ ${\displaystyle n}$ ${\displaystyle d}$

Related to this is the following statement, named after Leonard James Rogers as the theorem of Rogers :

The number of partitions of whose summands differ by 2 or more is equal to the number of partitions of where all summands leave the remainder 1 or 4 when divided by 5. ${\displaystyle n}$ ${\displaystyle n}$

The statement is part of the Rogers-Ramanujan identities .

Math applications

→ Main article : Partitioning problem

on applications in technology and computer science.

Conjugation classes of the symmetrical group

→ Main article : Young tableau

The number of conjugation classes in the symmetrical group is equal to the value of the partition function, because each conjugation class corresponds exactly to a cycle type of permutations with a certain structure of the representation in disjoint cycle notation . ${\displaystyle S_{n}}$ ${\displaystyle P(n)}$

Examples

• The permutation belongs as an element to the number partition of the number 9, as an element to the number partition of 12. Note that fixed elements of the permutation, which are almost always omitted in the cycle notation (as "one-cycles"), are added in the number partition as the summand 1 Pop up. Every element of the , which in the disjoint cycle notation consists of a three and a four cycle, is conjugated to the above element, in this case there are such permutations. ${\displaystyle (1,2,3)(5,7,8,9)}$ ${\displaystyle S_{9}}$ ${\displaystyle 1+1+3+4}$ ${\displaystyle S_{12}}$ ${\displaystyle 1+1+1+1+1+3+4}$ ${\displaystyle S_{12}}$ ${\displaystyle S_{12}}$ ${\displaystyle {\binom {12}{4}}\cdot {\binom {8}{3}}\cdot 3!\cdot 2!=332\,640}$
• The permutation belongs as an element to the number partition of 12. It belongs to a conjugation class that contains permutations. ${\displaystyle (1,2,3)(5,7,6)(10,11)}$ ${\displaystyle S_{12}}$ ${\displaystyle 1+1+1+1+2+3+3}$ ${\displaystyle S_{12}}$ ${\displaystyle {\binom {12}{3}}\cdot {\binom {9}{3}}\cdot {\binom {6}{2}}\cdot {\frac {2!\cdot 2!}{2!}}=554\,400}$

Payment partition and finite quantity partition

Every equivalence relation on a finite set with elements determines a set partition of . In combinatorics, the generality is assumed without restriction . A non-empty set of isomorphic equivalence classes of the set belongs to every number partition of . The number of number partitions from is therefore less than or equal to the number of quantity partitions from , for really less: ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle M=\{1,2,\ldots n\}}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle M}$ ${\displaystyle n\geq 3}$

Examples

${\displaystyle n}$	0	1	2	3	4th	5	6th	7th	8th	9	10	11
Number of payment partitions ${\displaystyle P(n)}$	1	1	2	3	5	7th	11	15th	22nd	30th	42	56
Number of volume partitions ${\displaystyle B_{n}}$	1	1	2	5	15th	52	203	877	4140	21147	115975	678570

• The 3 volume partitions belong to the number partition of 3 . ${\displaystyle 3=2+1}$ ${\displaystyle \{\{1,2\},\{3\}\};\{\{1,3\},\{2\}\};\{\{2,3\},\{1\}\}}$
• The number partitions and of 5 each belong to volume partitions, to the number partitions and each exactly one volume partition. ${\displaystyle 5=3+2}$ ${\displaystyle 5=3+1+1}$ ${\displaystyle {\binom {5}{3}}=10}$ ${\displaystyle 5=5}$ ${\displaystyle 5=1+1+1+1+1}$

Finite abelian p-groups and abelian groups

If a positive prime number , then for each group with the group order there is a p-group . The number of (isomorphism classes of) Abelian groups with group elements is - regardless of the prime number - equal to the value of the partition function, because according to the main theorem about finitely generated Abelian groups , every such group is isomorphic to a direct product with and . Since the isomorphism class does not depend on the order of the factors in the direct product, every isomorphism class of Abelian groups with elements that can be reversed uniquely corresponds to a number partition of . ${\displaystyle p}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle p^{n}}$ ${\displaystyle p^{n}}$ ${\displaystyle p}$ ${\displaystyle P(n)}$ ${\displaystyle G}$ ${\displaystyle G\cong \mathbb {Z} /p^{k_{1}}\mathbb {Z} \times \mathbb {Z} /p^{k_{2}}\mathbb {Z} \times \cdots \times \mathbb {Z} /p^{k_{r}}\mathbb {Z} }$ ${\displaystyle p^{n}=p^{k_{1}}\cdot p^{k_{2}}\cdot \cdots \cdot p^{k_{r}}}$ ${\displaystyle n=k_{1}+k_{2}+\cdots +k_{r}}$ ${\displaystyle p^{n}}$ ${\displaystyle n}$

For example, apart from isomorphism, there are exactly Abelian groups with elements. ${\displaystyle P(5)=7}$ ${\displaystyle 32=2^{5},243=3^{5},3125=5^{5}}$

Application examples:

1. How many isomorphism types of Abelian groups with exactly 70,000 elements are there? Every such group is, again according to the main theorem, a direct product of its abelian p- Sylow groups to the prime numbers 2, 5 and 7. It is , so there are “essentially different” Abelian groups with 70,000 elements. ${\displaystyle 70000=2^{4}\cdot 5^{4}\cdot 7^{1}}$ ${\displaystyle P(4)\cdot P(4)\cdot P(1)=5\cdot 5\cdot 1=25\,}$
2. How many types of isomorphisms of Abelian groups with 7200 elements are there that contain an element of order 180? It is . Of the Abelian 2 and 3 groups, only those belonging to a partition of 5 or 2, which contain a summand greater than or equal to 2, are considered, so that a number partition (sum of ones) is omitted. So there are such groups. ${\displaystyle 180=2^{2}\cdot 3^{2}\cdot 5^{1};7200=2^{5}\cdot 3^{2}\cdot 5^{2}}$ ${\displaystyle (P(5)-1)\cdot (P(2)-1)\cdot P(2)=6\cdot 1\cdot 2=12}$
3. If, in addition to the information in the previous example, it is known that no element has an order greater than 180, only 2 types of 2-Sylow groups and one type of 5-Sylow group are possible and there are exactly 2 isomorphism types of groups with these properties . ${\displaystyle (5=2+2+1;5=2+1+1+1)}$ ${\displaystyle (2=1+1)}$

Number function of isomorphism types of finite Abelian groups

The main theorem about finitely generated Abelian groups allows the number of isomorphism types of finite Abelian groups with elements to be expressed using the partition function: ${\displaystyle a(n)}$ ${\displaystyle n}$ ${\displaystyle P}$

• For every natural number with the prime factorization there are exactly isomorphy types of Abelian groups with elements. ${\displaystyle n\in \mathbb {N} \setminus \{0\}}$ ${\displaystyle n={p_{1}}^{r_{1}}\cdot {p_{2}}^{r_{2}}\cdots {p_{k}}^{r_{k}}}$ ${\displaystyle a(n)=P(r_{1})\cdot P(r_{2})\cdots P(r_{k})}$ ${\displaystyle n}$
• The sequence is sequence A000688 in OEIS , it is a multiplicative number theoretic function of and as such completely determined by its values ​​for prime powers . ${\displaystyle a(n)}$ ${\displaystyle n}$
• The (formal) Dirichlet series assigned to the number function is ${\displaystyle a(n)}$ ${\displaystyle A(s)}$

${\displaystyle A(s)=\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}},\,}$ with its Euler product ${\displaystyle s=\sigma +it\in \mathbb {C} ,\,}$ ${\displaystyle A(s)=\prod _{p\ {\mathrm {prim} }}\sum _{r=0}^{\infty }{\frac {P(r)}{p^{rs}}}.}$

• The number function are for the same time the number of through the divisibility parent chain to which the product equal is ${\displaystyle a(n)}$ ${\displaystyle n\geq 2}$ ${\displaystyle (t_{1},t_{2},\ldots ,t_{r})\in \left\lbrace \left(\mathbb {N} \setminus \{0,1\}\right)^{r}:\;t_{1}|t_{2}|\cdots |t_{r}\right\rbrace }$ ${\displaystyle n}$ ${\displaystyle (t_{1}\cdot t_{2}\cdot \cdots t_{r}=n).}$

literature

• Jacobus Hendricus van Lint , RM Wilson: A Course in Combinatorics . 2nd Edition. Cambridge University Press, Cambridge 2001, ISBN 0-521-80340-3 .
• Derrick Henry Lehmer : Two nonexistence theorems on partitions . In: Bulletin of the American Mathematical Society . Volume 52, No. 6 , 1946, pp. 538-544 , doi : 10.1090 / S0002-9904-1946-08605-X ( projecteuclid.org [accessed February 18, 2012]).
• John Edensor Littlewood : A Mathematician's Miscellany . A journey of discovery. Methuen, London 1953, ISBN 3-540-42386-9 , pp. 84–90 (English, full text in various file formats [accessed on February 15, 2012] Littlewood tells in this book, among other things, about Hardy's collaboration with Ramanujan and how they solved the problem of approximation of the partition function in 1918).
• Jiří Matoušek, Jaroslav Nešetřil: Discrete Mathematics . A journey of discovery. Springer, Berlin / Heidelberg / New York etc. 2002, ISBN 3-540-42386-9 , 10.7 number partitions ( table of contents [accessed on February 8, 2012] English: Invitation to Discrete Mathematics . Translated by Hans Mielke, textbook that has little previous knowledge - advanced school mathematics up to the 2nd semester of mathematics studies - required).

About the applications in group theory:

• Thomas W. Hungerford: Algebra . In: Graduate texts in mathematics . 8th corrected edition. No. 73. Springer, New York / Berlin / Singapore / Tokyo / Heidelberg / Barcelona / Budapest / Hong Kong / London / Milan / Paris / Santa Clara 1996, ISBN 3-540-90518-9 , I. Groups, II. The Structure of Groups, p. 35–82 ( table of contents filediva.com (PDF; 8 MB) [accessed on February 15, 2012]).

Web links

• Eric W. Weis Stone : Partition Function P . In: MathWorld (English). Partition function . ${\displaystyle P(n)}$
• Eric W. Weis Stone : partition function Q . In: MathWorld (English). Partition function . ${\displaystyle Q(n)}$
• The computer algebra program Maple contains in the package combinat the function partition (n) , which creates all number partitions of the finite sets , and the function numbpart (n) , which calculates the value of the partition function. ${\displaystyle \{1,2,\ldots n\}}$ ${\displaystyle P(n)}$

Individual evidence

1. ↑ Florian Scheck: Theoretical Physics 5: Statistical theory of heat . Springer, 2008, ISBN 978-3-540-79823-1 , pp. 98 ( books.google.de ).
2. ↑ ^{a b c d e f} Matoušek, Nešetřil (2002)
3. ↑ Eric W. Weis Stone : partition function Q . In: MathWorld (English).
4. ↑ Angelika Steger: Discrete Structures 1: Combinatorics, Graph Theory, Algebra . Springer, 2001, ISBN 978-3-540-67597-6 , pp. 36 .
5. ^ Karl-Heinz Zimmermann: Discrete Mathematics . Books on Demand , 2006, ISBN 978-3-8334-5529-2 , pp. 115 .
6. ↑ Littlewood, 1953
7. ↑ JH Bruinier, K. Ono: An algebraic formula for the partition function ( Memento of the original from January 24, 2011 in the Internet Archive ) Info: The archive link was automatically inserted and not yet checked. Please check the original and archive link according to the instructions and then remove this notice. , 2011. 
8. ^ Euler's legacy - mathematicians celebrate discovery in number theory . sueddeutsche.de, accessed January 29, 2011.
9. ↑ Ferrers was a British mathematician (August 11, 1829 to January 31, 1903), see Matoušek, Nešetřil (2002)
10. ↑ Ulrik Brandes: Methods of Network Analysis - Lecture Notes, 1.15 (PDF; 316 kB) University of Konstanz; Retrieved February 17, 2012.
11. ^ Leonhard Euler : Introductio analysin infinitorum , Volume 1. Lausanne 1748, pp. 253-275
12. ↑ ^{a b} Lehmer, 1946