Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Partition (number theory)
Summary
In number theory and combinatorics, a partition of a non-negative integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.) For example, 4 can be partitioned in five distinct ways:
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
The only partition of zero is the empty sum, having no parts.
The order-dependent composition 1 + 3 is the same partition as 3 + 1, and the two distinct compositions 1 + 2 + 1 and 1 + 1 + 2 represent the same partition as 2 + 1 + 1.
An individual summand in a partition is called a part. The number of partitions of n is given by the partition function p(n). So p(4) = 5. The notation λ ⊢ n means that λ is a partition of n.
Partitions can be graphically visualized with Young diagrams or Ferrers diagrams. 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.
The seven partitions of 5 are
5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
Some authors treat a partition as a decreasing sequence of summands, rather than an expression with plus signs. For example, the partition 2 + 2 + 1 might instead be written as the tuple (2, 2, 1) or in the even more compact form (22, 1) where the superscript indicates the number of repetitions of a part.
This multiplicity notation for a partition can be written alternatively as , where m1 is the number of 1's, m2 is the number of 2's, etc. (Components with mi = 0 may be omitted.) For example, in this notation, the partitions of 5 are written , and .
There are two common diagrammatic methods to represent partitions: as Ferrers diagrams, named after Norman Macleod Ferrers, and as Young diagrams, named after Alfred Young. Both have several possible conventions; here, we use English notation, with diagrams aligned in the upper-left corner.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (1)
Fluctuation estimates for the multi-cell formula in stochastic homogenization of partitions
In this paper we derive quantitative estimates in the context of stochastic homogenization for integral functionals defined on finite partitions, where the random surface integrand is assumed to be st
2022Related concepts (34)
Generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers (an) by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem.
Partition (number theory)
In number theory and combinatorics, a partition of a non-negative integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.) For example, 4 can be partitioned in five distinct ways: 4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 The only partition of zero is the empty sum, having no parts.
Srinivasa Ramanujan
Srinivasa Ramanujan (ˈsriːnᵻvɑːsə_rɑːˈmɑːnʊdʒən ; born Srinivasa Ramanujan Aiyangar, sriːniʋaːsa ɾaːmaːnud͡ʑan ajːaŋgar; 22 December 1887 26 April 1920) was an Indian mathematician. Though he had almost no formal training in pure mathematics, he made substantial contributions to mathematical analysis, number theory, infinite series, and continued fractions, including solutions to mathematical problems then considered unsolvable. Ramanujan initially developed his own mathematical research in isolation.
Related courses (7)
COM-490: Large-scale data science for real-world data
This hands-on course teaches the tools & methods used by data scientists, from researching solutions to scaling up
prototypes to Spark clusters. It exposes the students to the entire data science pipe
MSE-421: Statistical mechanics
This course presents an introduction to statistical mechanics geared towards materials scientists. The concepts of macroscopic thermodynamics will be related to a microscopic picture and a statistical
PHYS-512: Statistical physics of computation
This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and
Related lectures (94)
Set Partitions
Explores set partitions from empty to full sets, illustrating subsets relationships.
Quantum Effective Action
Explores the quantum effective action, its role in perturbation theory, and the organization of correlators in momentum space.
Classical Scattering: Two-Body Dynamics
Covers the classical scattering of two-body systems and their energy levels.