Partition (number theory)

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Partition (number theory)_sentence_0

Two sums that differ only in the order of their summands are considered the same partition. Partition (number theory)_sentence_1

(If order matters, the sum becomes a composition.) Partition (number theory)_sentence_2

For example, 4 can be partitioned in five distinct ways: Partition (number theory)_sentence_3

Partition (number theory)_description_list_0

  • 4Partition (number theory)_item_0_0
  • 3 + 1Partition (number theory)_item_0_1
  • 2 + 2Partition (number theory)_item_0_2
  • 2 + 1 + 1Partition (number theory)_item_0_3
  • 1 + 1 + 1 + 1Partition (number theory)_item_0_4

The order-dependent composition 1 + 3 is the same partition as 3 + 1, while the two distinct compositions 1 + 2 + 1 and 1 + 1 + 2 represent the same partition 2 + 1 + 1. Partition (number theory)_sentence_4

A summand in a partition is also called a part. Partition (number theory)_sentence_5

The number of partitions of n is given by the partition function p(n). Partition (number theory)_sentence_6

So p(4) = 5. Partition (number theory)_sentence_7

The notation λ ⊢ n means that λ is a partition of n. Partition (number theory)_sentence_8

Partitions can be graphically visualized with Young diagrams or Ferrers diagrams. Partition (number theory)_sentence_9

They occur in a number of branches of mathematics and physics, including the study of symmetric polynomials and of the symmetric group and in group representation theory in general. Partition (number theory)_sentence_10

Examples Partition (number theory)_section_0

The seven partitions of 5 are: Partition (number theory)_sentence_11

Partition (number theory)_unordered_list_1

  • 5Partition (number theory)_item_1_5
  • 4 + 1Partition (number theory)_item_1_6
  • 3 + 2Partition (number theory)_item_1_7
  • 3 + 1 + 1Partition (number theory)_item_1_8
  • 2 + 2 + 1Partition (number theory)_item_1_9
  • 2 + 1 + 1 + 1Partition (number theory)_item_1_10
  • 1 + 1 + 1 + 1 + 1Partition (number theory)_item_1_11

In some sources partitions are treated as the sequence of summands, rather than as an expression with plus signs. Partition (number theory)_sentence_12

For example, the partition 2 + 2 + 1 might instead be written as the tuple (2, 2, 1) or in the even more compact form (2, 1) where the superscript indicates the number of repetitions of a term. Partition (number theory)_sentence_13

Representations of partitions Partition (number theory)_section_1

There are two common diagrammatic methods to represent partitions: as Ferrers diagrams, named after Norman Macleod Ferrers, and as Young diagrams, named after the British mathematician Alfred Young. Partition (number theory)_sentence_14

Both have several possible conventions; here, we use English notation, with diagrams aligned in the upper-left corner. Partition (number theory)_sentence_15

Ferrers diagram Partition (number theory)_section_2

The partition 6 + 4 + 3 + 1 of the positive number 14 can be represented by the following diagram: Partition (number theory)_sentence_16

The 14 circles are lined up in 4 rows, each having the size of a part of the partition. Partition (number theory)_sentence_17

The diagrams for the 5 partitions of the number 4 are listed below: Partition (number theory)_sentence_18

Young diagram Partition (number theory)_section_3

Main article: Young diagram Partition (number theory)_sentence_19

An alternative visual representation of an integer partition is its Young diagram (often also called a Ferrers diagram). Partition (number theory)_sentence_20

Rather than representing a partition with dots, as in the Ferrers diagram, the Young diagram uses boxes or squares. Partition (number theory)_sentence_21

Thus, the Young diagram for the partition 5 + 4 + 1 is Partition (number theory)_sentence_22

Partition (number theory)_description_list_2

while the Ferrers diagram for the same partition is Partition (number theory)_sentence_23

Partition (number theory)_description_list_3

While this seemingly trivial variation doesn't appear worthy of separate mention, Young diagrams turn out to be extremely useful in the study of symmetric functions and group representation theory: filling the boxes of Young diagrams with numbers (or sometimes more complicated objects) obeying various rules leads to a family of objects called Young tableaux, and these tableaux have combinatorial and representation-theoretic significance. Partition (number theory)_sentence_24

As a type of shape made by adjacent squares joined together, Young diagrams are a special kind of polyomino. Partition (number theory)_sentence_25

Partition function Partition (number theory)_section_4

Main article: Partition function (number theory) Partition (number theory)_sentence_26

Partition (number theory)_description_list_4

  • 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (sequence in the OEIS).Partition (number theory)_item_4_12

No closed-form expression for the partition function is known, but it has both asymptotic expansions that accurately approximate it and recurrence relations by which it can be calculated exactly. Partition (number theory)_sentence_27

It grows as an exponential function of the square root of its argument. Partition (number theory)_sentence_28

The multiplicative inverse of its generating function is the Euler function; by Euler's pentagonal number theorem this function is an alternating sum of pentagonal number powers of its argument. Partition (number theory)_sentence_29

Restricted partitions Partition (number theory)_section_5

In both combinatorics and number theory, families of partitions subject to various restrictions are often studied. Partition (number theory)_sentence_30

This section surveys a few such restrictions. Partition (number theory)_sentence_31

Conjugate and self-conjugate partitions Partition (number theory)_section_6

If we flip the diagram of the partition 6 + 4 + 3 + 1 along its main diagonal, we obtain another partition of 14: Partition (number theory)_sentence_32

By turning the rows into columns, we obtain the partition 4 + 3 + 3 + 2 + 1 + 1 of the number 14. Partition (number theory)_sentence_33

Such partitions are said to be conjugate of one another. Partition (number theory)_sentence_34

In the case of the number 4, partitions 4 and 1 + 1 + 1 + 1 are conjugate pairs, and partitions 3 + 1 and 2 + 1 + 1 are conjugate of each other. Partition (number theory)_sentence_35

Of particular interest is the partition 2 + 2, which has itself as conjugate. Partition (number theory)_sentence_36

Such a partition is said to be self-conjugate. Partition (number theory)_sentence_37

Claim: The number of self-conjugate partitions is the same as the number of partitions with distinct odd parts. Partition (number theory)_sentence_38

Proof (outline): The crucial observation is that every odd part can be "folded" in the middle to form a self-conjugate diagram: Partition (number theory)_sentence_39

One can then obtain a bijection between the set of partitions with distinct odd parts and the set of self-conjugate partitions, as illustrated by the following example: Partition (number theory)_sentence_40

Odd parts and distinct parts Partition (number theory)_section_7

Among the 22 partitions of the number 8, there are 6 that contain only odd parts: Partition (number theory)_sentence_41

Partition (number theory)_unordered_list_5

  • 7 + 1Partition (number theory)_item_5_13
  • 5 + 3Partition (number theory)_item_5_14
  • 5 + 1 + 1 + 1Partition (number theory)_item_5_15
  • 3 + 3 + 1 + 1Partition (number theory)_item_5_16
  • 3 + 1 + 1 + 1 + 1 + 1Partition (number theory)_item_5_17
  • 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1Partition (number theory)_item_5_18

Alternatively, we could count partitions in which no number occurs more than once. Partition (number theory)_sentence_42

Such a partition is called a partition with distinct parts. Partition (number theory)_sentence_43

If we count the partitions of 8 with distinct parts, we also obtain 6: Partition (number theory)_sentence_44

Partition (number theory)_unordered_list_6

  • 8Partition (number theory)_item_6_19
  • 7 + 1Partition (number theory)_item_6_20
  • 6 + 2Partition (number theory)_item_6_21
  • 5 + 3Partition (number theory)_item_6_22
  • 5 + 2 + 1Partition (number theory)_item_6_23
  • 4 + 3 + 1Partition (number theory)_item_6_24

This is a general property. Partition (number theory)_sentence_45

For each positive number, the number of partitions with odd parts equals the number of partitions with distinct parts, denoted by q(n). Partition (number theory)_sentence_46

This result was proved by Leonhard Euler in 1748 and later was generalized as Glaisher's theorem. Partition (number theory)_sentence_47

For every type of restricted partition there is a corresponding function for the number of partitions satisfying the given restriction. Partition (number theory)_sentence_48

An important example is q(n). Partition (number theory)_sentence_49

The first few values of q(n) are (starting with q(0)=1): Partition (number theory)_sentence_50

Partition (number theory)_description_list_7

  • 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, ... (sequence in the OEIS).Partition (number theory)_item_7_25

The generating function for q(n) (partitions into distinct parts) is given by Partition (number theory)_sentence_51

The pentagonal number theorem gives a recurrence for q: Partition (number theory)_sentence_52

Partition (number theory)_description_list_8

  • q(k) = ak + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k − 15) − q(k − 22) − ...Partition (number theory)_item_8_26

where ak is (−1) if k = 3m − m for some integer m and is 0 otherwise. Partition (number theory)_sentence_53

Restricted part size or number of parts Partition (number theory)_section_8

By taking conjugates, the number pk(n) of partitions of n into exactly k parts is equal to the number of partitions of n in which the largest part has size k. The function pk(n) satisfies the recurrence Partition (number theory)_sentence_54

Partition (number theory)_description_list_9

  • pk(n) = pk(n − k) + pk−1(n − 1)Partition (number theory)_item_9_27

with initial values p0(0) = 1 and pk(n) = 0 if n ≤ 0 or k ≤ 0 and n and k are not both zero. Partition (number theory)_sentence_55

One recovers the function p(n) by Partition (number theory)_sentence_56

One possible generating function for such partitions, taking k fixed and n variable, is Partition (number theory)_sentence_57

More generally, if T is a set of positive integers then the number of partitions of n, all of whose parts belong to T, has generating function Partition (number theory)_sentence_58

This can be used to solve change-making problems (where the set T specifies the available coins). Partition (number theory)_sentence_59

As two particular cases, one has that the number of partitions of n in which all parts are 1 or 2 (or, equivalently, the number of partitions of n into 1 or 2 parts) is Partition (number theory)_sentence_60

and the number of partitions of n in which all parts are 1, 2 or 3 (or, equivalently, the number of partitions of n into at most three parts) is the nearest integer to (n + 3) / 12. Partition (number theory)_sentence_61

Asymptotics Partition (number theory)_section_9

Main article: Partition_function_(number_theory) § Approximation_formulas Partition (number theory)_sentence_62

The asymptotic growth rate for p(n) is given by Partition (number theory)_sentence_63

was first obtained by G. Partition (number theory)_sentence_64 H. Hardy and Ramanujan in 1918 and independently by J. Partition (number theory)_sentence_65 V. Uspensky in 1920. Partition (number theory)_sentence_66

A complete asymptotic expansion was given in 1937 by Hans Rademacher. Partition (number theory)_sentence_67

If A is a set of natural numbers, we let pA(n) denote the number of partitions of n into elements of A. Partition (number theory)_sentence_68

If A possesses positive natural density α then Partition (number theory)_sentence_69

and conversely if this asymptotic property holds for pA(n) then A has natural density α. Partition (number theory)_sentence_70

This result was stated, with a sketch of proof, by Erdős in 1942. Partition (number theory)_sentence_71

If A is a finite set, this analysis does not apply (the density of a finite set is zero). Partition (number theory)_sentence_72

If A has k elements whose greatest common divisor is 1, then Partition (number theory)_sentence_73

Partitions in a rectangle and Gaussian binomial coefficients Partition (number theory)_section_10

Main article: Gaussian binomial coefficient Partition (number theory)_sentence_74

One may also simultaneously limit the number and size of the parts. Partition (number theory)_sentence_75

Let p(N, M; n) denote the number of partitions of n with at most M parts, each of size at most N. Equivalently, these are the partitions whose Young diagram fits inside an M × N rectangle. Partition (number theory)_sentence_76

There is a recurrence relation Partition (number theory)_sentence_77

The Gaussian binomial coefficient is defined as: Partition (number theory)_sentence_78

The Gaussian binomial coefficient is related to the generating function of p(N, M; n) by the equality Partition (number theory)_sentence_79

Rank and Durfee square Partition (number theory)_section_11

Main article: Durfee square Partition (number theory)_sentence_80

The rank of a partition is the largest number k such that the partition contains at least k parts of size at least k. For example, the partition 4 + 3 + 3 + 2 + 1 + 1 has rank 3 because it contains 3 parts that are ≥ 3, but does not contain 4 parts that are ≥ 4. Partition (number theory)_sentence_81

In the Ferrers diagram or Young diagram of a partition of rank r, the r × r square of entries in the upper-left is known as the Durfee square: Partition (number theory)_sentence_82

Partition (number theory)_description_list_10

The Durfee square has applications within combinatorics in the proofs of various partition identities. Partition (number theory)_sentence_83

It also has some practical significance in the form of the h-index. Partition (number theory)_sentence_84

Young's lattice Partition (number theory)_section_12

Main article: Young's lattice Partition (number theory)_sentence_85

There is a natural partial order on partitions given by inclusion of Young diagrams. Partition (number theory)_sentence_86

This partially ordered set is known as Young's lattice. Partition (number theory)_sentence_87

The lattice was originally defined in the context of representation theory, where it is used to describe the irreducible representations of symmetric groups Sn for all n, together with their branching properties, in characteristic zero. Partition (number theory)_sentence_88

It also has received significant study for its purely combinatorial properties; notably, it is the motivating example of a differential poset. Partition (number theory)_sentence_89

See also Partition (number theory)_section_13

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: en.wikipedia.org/wiki/Partition (number theory).