Partición (teoría de números)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d8/Ferrer_partitioning_diagrams.svg/280px-Ferrer_partitioning_diagrams.svg.png)
En matemáticas discretas, una partición de un entero positivo n es una forma de descomponer n como suma de enteros positivos. Dos sumas se considerarán iguales si solo difieren en el orden de los sumandos.
De modo más riguroso, una partición de un número entero positivo n es una secuencia de enteros positivos tal que
- .
Las posibles particiones de un entero n pueden visualizarse con los diagramas conocidos como diagramas de Ferrers o diagramas de Young.
Ejemplos
Las cinco particiones del número 4 serían:
- 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1
Y las once particiones del número 6 serían:
- 6 = 5 + 1 = 4 +2 = 4 + 1 + 1 = 3 + 3 = 3 + 2 + 1 =
- = 3 + 1 + 1 + 1 = 2 + 2 + 2 = 2 + 2 + 1 + 1 = 2 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 +1
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/33/Particionn.png/280px-Particionn.png)
Representación de las particiones
Hay dos métodos comunes para representar particiones: por un lado, los esquemas Ferrers, más tarde nombrados Norman Macleod Ferrers, y por otro los esquemas Young, renombrados después por el matemático británico Alfred Young. Ambos tienen varias convenciones posibles; aquí, se suele utilizar la notación la inglesa, con esquemas alineados en la esquina superior izquierda.
Esquemas Ferrers
La partición 6+4+3+1 del número positivo 14 se puede representar mediante este diagrama:
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
Las 14 bolas están alineadas en 4 filas, cada una con el tamaño de la partición correspondiente.
A continuación, se muestra otro ejemplo con 5 posibles particiones del número 4:
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
![*](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/GrayDot.svg/16px-GrayDot.svg.png)
Esquemas Young
Una representación alternativa de la partición de enteros es el esquema Young. En lugar de una representación con puntos,como el caso anterior, este usa cajas o cuadrados. Así, la partición 5+4+1 viene dada por:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f2/Young_diagram_for_541_partition.svg/100px-Young_diagram_for_541_partition.svg.png)
mientras que en el esquema Ferrer sería:
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
Aparentemente esta variación es trivial; sin embargo el uso de los esquemas Young es útil en el estudio de funciones simétricas y en teoría de representación de grupos. Como consecuencia de la adyacencia de diferentes cuadrados, estos esquemas pueden considerarse como un caso especial de poliominós.
Función de partición
En la teoría de números, la función de partición p(n) representa el número de posibles particiones de un número natural n, o lo que es lo mismo, el número de formas de representar n como suma de números naturales. Por convenio, p(0)=1, y p(n)=0 para los números negativos.
Los primeros valores de la función de partición, comenzando desde p(0)=1 son: 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, … (secuencia A000041 en la OEIS).
Los valores de p(n) crecen muy rápidamente con el valor de n. De hecho:
- p(100) = 190,569,292
- p(200) = 3,972,999,029,388
- p(1000) = 24,061,467,864,032,622,473,692,149,727,991 ≈ 2.4 × 1031
Fórmulas para la función de partición
Una expresión asintótica de p(n) fue obtenida por G. H. Hardy y Ramanujan en 1918 y de forma independiente por J. V. Uspensky en el año 1920:
- Hardy y Ramanujan también obtuvieron una expansión asintótica cuyo primer término es la aproximación anterior:
- donde
- (la notación indica que la suma es sobre parejas de enteros primos relativos; y la función es una suma de Dedekind.
- En 1937, Hans Rademacher logró mejorar los resultados de Hardy y Ramanujan y encontró una serie convergente para calcular p(n), a saber[1]:
- Se puede demostrar que el término k de la serie de Rademacher es del orden de , así que el primer término reproduce la aproximación asintótica de Hardy y Ramanujan.
Particiones restringidas
Tanto en combinatoria como en la teoría de números, las familias de particiones son objetos de estudio. A continuación se mostrarán algunas de las restricciones.
Particiones conjugadas y autoconjugadas
Si damos la vuelta al diagrama de la partición de 6 + 4 + 3 + 1, a lo largo de su diagonal obtenemos la partición de 14.
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() | ↔ | ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
6 + 4 + 3 + 1 | = | 4 + 3 + 3 + 2 + 1 + 1 |
Transformando las filas en columnas obtenemos la partición 4 + 3 + 3 + 2 + 1 + 1 del número 14. Se dice por tanto que estas particiones son conjugadas. En el caso del número 4, la partición 4 y 1 + 1 + 1 + 1 son pares conjugados, y las particiones 3 + 1, y 2 + 1 + 1 son conjugadas mutuamente. Especial mención merece la partición 2 + 2, ya que su conjugada es ella misma. Por tanto, decimos que una partición es autoconjugada.
Proposición: El número de particiones autoconjugadas es el mismo que el número de particiones en partes distintas.
Demostración (boceto): La observación crucial es que cada parte impar puede ser "doblada" por la mitad, formando así un diagrama autoconjugado:
![]() ![]() ![]() ![]() ![]() | ↔ | ![]() ![]() ![]() ![]() ![]() |
Así se puede obtener una biyección entre el conjunto de particiones en partes impares distintas y el conjunto de particiones autoconjugadas, como se ilustra en el ejemplo siguiente:
| ↔ | ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
9 + 7 + 3 | = | 5 + 5 + 4 + 3 + 2 |
Distintas impares | autoconjugada |
Partes impares y partes distintas
Entre las 22 particiones del número 8, hay 6 que sólo contienen partes impares:
- 7 + 1
- 5 + 3
- 5 + 1 + 1 + 1
- 3 + 3 + 1 + 1
- 3 + 1 + 1 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
De manera alternativa, podríamos contar las particiones en las que ningún número aparece más de una vez. Una partición así se llama partición en partes distintas. Si contamos las particiones de 8 en partes distintas, también obtenemos 6:
- 8
- 7 + 1
- 6 + 2
- 5 + 3
- 5 + 2 + 1
- 4 + 3 + 1
Esto es una propiedad general. Para todo número positivo, el número de particiones en partes impares es igual al número de particiones en partes distintas, denotado por q(n). Este resultado fue demostrado por Leonhard Euler en 1748, y más tarde se generalizó mediante el teorema de Glaisher.
Véase también
Referencias
- ↑ Andrews, George E. (1976). The theory of partitions (1st pbk. ed edición). Cambridge University Press. p. 63. ISBN 9780521637664. OCLC 39742738.
Bibliografía
- Tom M. Apostol. Introducción a la teoría analítica de números. Reverté, 1984. ISBN 84-291-5006-4, 9788429150063. pg 382
- Hardy and Wright (2008)
- George E. Andrews.The Theory of Partitions ISBN 978-0521637664
Enlaces externos
- Weisstein, Eric W. «Partition». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. Consultado el 27 de mayo de 2010.
- Weisstein, Eric W. «Partition Function P». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. Consultado el 27 de mayo de 2010.
Datos: Q1082910
Multimedia: Integer partitions / Q1082910