Partición (teoría de números)

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Decomposición de un entero como una suma de enteros positivos

Diagramas jóvenes asociados a las particiones de los enteros positivos 1 a 8. Se arreglan para que las imágenes bajo la reflexión sobre la diagonal principal de la plaza sean particiones conjugadas.

Particiones de

n

con mayor parte

k

En teoría de números y combinatoria, una partición de un número entero positivo $n$ , también llamada partición de enteros, es una forma de escribir $n$ como una suma de enteros positivos. Dos sumas que difieren solo en el orden de sus sumandos se consideran la misma partición. (Si el orden es importante, la suma se convierte en una composición). Por ejemplo, $4$ se puede dividir en cinco formas distintas:

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

La composición dependiente del orden $1 + 3$ es la misma partición que $3 + 1$ , y las dos composiciones distintas $1 + 2 + 1$ y $1 + 1 + 2$ representan la misma partición que $2 + 1 + 1$ .

Un sumando individual en una partición se denomina parte. El número de particiones de $n$ viene dado por la función de partición $p (n)$ . Entonces $p (4) = 5$ . La notación $λ ⊢ n$ significa que $λ$ es una partición de $n$ .

Las particiones se pueden visualizar gráficamente con diagramas de Young o diagramas de Ferrers. Ocurren en varias ramas de las matemáticas y la física, incluido el estudio de polinomios simétricos y del grupo simétrico y en la teoría de representación de grupos en general.

Ejemplos

Las siete particiones de 5 son

5
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Algunos autores tratan una partición como una secuencia decreciente de sumandos, en lugar de una expresión con signos más. Por ejemplo, la partición 2 + 2 + 1 podría escribirse como la tupla $(2, 2, 1)$ o en la forma aún más compacta $(2 2, 1)$ donde el superíndice indica el número de repeticiones de una parte.

Esta notación multiplicidad para una partición se puede escribir alternativamente como ${displaystyle 1^{m_{1}}2^{m_{2}}3^{m_{3}}cdots }$ , donde $m 1$ es el número de 1's, $m 2$ es el número de 2's, etc. (Componentes con $m i = 0$ puede ser omitido.) Por ejemplo, en esta notación, las particiones de 5 están escritas ${displaystyle 5^{1},1^{1}4^{1},2^{1}3^{1},1^{2}3^{1},1^{1}2^{2},1^{3}2^{1}}$ , y ${displaystyle 1^{5}}$ .

Representaciones esquemáticas de particiones

Hay dos métodos diagramáticos comunes para representar particiones: como diagramas de Ferrers, llamados así por Norman Macleod Ferrers, y como diagramas de Young, llamados así por Alfred Young. Ambos tienen varias convenciones posibles; aquí usamos la notación inglesa, con los diagramas alineados en la esquina superior izquierda.

Diagrama de Ferrer

La partición 6 + 4 + 3 + 1 del número 14 se puede representar mediante el siguiente diagrama:

Los 14 círculos están alineados en 4 filas, cada una con el tamaño de una parte de la partición. Los diagramas para las 5 particiones del número 4 se muestran a continuación:


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

Diagrama joven

Una representación visual alternativa de una partición de enteros es su diagrama de Young (a menudo también llamado diagrama de Ferrers). En lugar de representar una partición con puntos, como en el diagrama de Ferrers, el diagrama de Young usa cajas o cuadrados. Así, el diagrama de Young para la partición 5 + 4 + 1 es

mientras que el diagrama de Ferrers para la misma partición es

Si bien esta variación aparentemente trivial no parece digna de una mención aparte, los diagramas de Young resultan extremadamente útiles en el estudio de las funciones simétricas y la teoría de la representación de grupos: llenar las casillas de los diagramas de Young con números (o, a veces, con objetos más complicados) obedecer varias reglas conduce a una familia de objetos llamados cuadros de Young, y estos cuadros tienen un significado combinatorio y teórico de la representación. Como un tipo de forma formada por cuadrados adyacentes unidos, los diagramas de Young son un tipo especial de poliominó.

Función de partición

Usando el método de Euler para encontrar p(40): Un gobernante con más y menos signos (caja gris) es deslizado hacia abajo, las partes pertinentes añadidos o restados. Las posiciones de los signos se dan por diferencias de números naturales (azul) y extraños (orange). En el archivo SVG, salta sobre la imagen para mover la regla.

La función de partición $p(n)$ iguala el número de posibles particiones de un entero no negativo $n$ . Por ejemplo, ${displaystyle p(4)=5}$ porque el entero $4$ tiene las cinco particiones ${displaystyle 1+1+1+1}$ , ${displaystyle 1+1+2}$ , $1+3$ , $2+2$ , y $4$ . Los valores de esta función $n=0,1,2,dots$ 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,... A000041 en el OEIS).

La función generadora de $p$ es

{displaystyle sum _{n=0}^{infty }p(n)q^{n}=prod _{j=1}^{infty }sum _{i=0}^{infty }q^{ji}=prod _{j=1}^{infty }(1-q^{j})^{-1}.}

No se conoce ninguna expresión de forma cerrada para la función de partición, pero tiene expansiones asintóticas que la aproximan con precisión y relaciones de recurrencia mediante las cuales se puede calcular exactamente. Crece como una función exponencial de la raíz cuadrada de su argumento., como sigue:

{displaystyle p(n)sim {frac {1}{4n{sqrt {3}}}}exp left({pi {sqrt {frac {2n}{3}}}}right)}

como

nto infty

El inverso multiplicativo de su función generadora es la función de Euler; por el teorema del número pentagonal de Euler, esta función es una suma alterna de potencias de números pentagonales de su argumento.

p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+cdots

Srinivasa Ramanujan descubrió que la función de partición tiene patrones notriviales en aritmética modular, ahora conocida como congruencias de Ramanujan. Por ejemplo, cuando la representación decimal $n$ termina en el dígito 4 o 9, el número de particiones de $n$ será divisible por 5.

Particiones restringidas

Tanto en combinatoria como en teoría de números, a menudo se estudian familias de particiones sujetas a varias restricciones. En esta sección se examinan algunas de esas restricciones.

Particiones conjugadas y autoconjugadas

Si volteamos el diagrama de la partición 6 + 4 + 3 + 1 a lo largo de su diagonal principal, obtenemos otra partición de 14:

	Administración
6 + 4 + 3 + 1	=	4 + 3 + 3 + 2 + 1 + 1

Al convertir las filas en columnas, obtenemos la partición 4 + 3 + 3 + 2 + 1 + 1 del número 14. Se dice que tales particiones son conjugadas entre sí. En el caso del número 4, las particiones 4 y 1 + 1 + 1 + 1 son pares conjugados, y las particiones 3 + 1 y 2 + 1 + 1 son conjugados entre sí. De particular interés es la partición 2 + 2, que se tiene a sí mismo como conjugado. Se dice que tal partición es autoconjugada.

Afirmación: el número de particiones autoconjugadas es el mismo que el número de particiones con distintas partes impares.

Prueba (esquema): la observación crucial es que todas las partes impares se pueden "doblar" en el medio para formar un diagrama autoconjugado:

Administración

Entonces se puede obtener una biyección entre el conjunto de particiones con distintas partes impares y el conjunto de particiones autoconjugadas, como se ilustra en el siguiente ejemplo:

	Administración
9 + 7 + 3	=	5 + 5 + 4 + 3 + 2
Extraño.		autoconyugado

Partes impares y partes distintas

Entre las 22 particiones del número 8, hay 6 que contienen sólo 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 + 1

Alternativamente, podríamos contar las particiones en las que ningún número aparece más de una vez. Tal partición se llama una partición con distintas partes. Si contamos las particiones de 8 con partes distintas, también obtenemos 6:

8
7 + 1
6 + 2
5 + 3
5 + 2 + 1
4 + 3 + 1

Esta es una propiedad general. Para cada número positivo, el número de particiones con partes impares es igual al número de particiones con partes distintas, indicado por q(n). Este resultado fue demostrado por Leonhard Euler en 1748 y luego se generalizó como el teorema de Glaisher.

Para cada tipo de partición restringida existe una función correspondiente para el número de particiones que satisfacen la restricción dada. Un ejemplo importante es q(n) (particiones en partes distintas). Los primeros valores de q(n) son (empezando por q(0)=1):

1, 1, 1, 2, 3, 4, 5, 6, 8, 10... A000009 en el OEIS).

La función generadora de q(n) viene dada por

sum _{n=0}^{infty }q(n)x^{n}=prod _{k=1}^{infty }(1+x^{k})=prod _{k=1}^{infty }{frac {1}{1-x^{2k-1}}}.

El teorema del número pentagonal da una recurrencia para q:

q()k) a_k + q()k −1) + q()k 2) - q()k 5) - q()k − 7) + q()k − 12) + q()k 15 - 15 q()k 22 – –

donde a_k es (−1)^m si k = 3m² − m para algún número entero m y es 0 en caso contrario.

Tamaño de pieza restringido o número de piezas

Al tomar conjugados, el número $p k (n)$ de particiones de $n$ en exactamente k partes es igual al número de particiones de $n$ en el que la parte más grande tiene tamaño $k$ . La función $p k (n)$ satisface la recurrencia

p k () n) p k () n - k) + p k -1 () n -1)

con valores iniciales $p 0 (0) = 1$ y $p k (n) = 0$ si $n \leq 0 o k \leq 0$ y $n$ y $k$ no son ambos cero.

Se recupera la función p(n) por

{displaystyle p(n)=sum _{k=0}^{n}p_{k}(n).}

Una posible función generadora para tales particiones, tomando k fijo y n variable, es

{displaystyle sum _{ngeq 0}p_{k}(n)x^{n}=x^{k}prod _{i=1}^{k}{frac {1}{1-x^{i}}}.}

Más generalmente, si T es un conjunto de números enteros positivos, entonces el número de particiones de n, todas cuyas partes pertenecen a T, tiene función generadora

prod _{tin T}(1-x^{t})^{-1}.

Esto se puede usar para resolver problemas de cambios (donde el conjunto T especifica las monedas disponibles). Como dos casos particulares, uno tiene que el número de particiones de n en las que todas las partes son 1 o 2 (o, de manera equivalente, el número de particiones de n en 1 o 2 partes) es

{displaystyle leftlfloor {frac {n}{2}}+1rightrfloor}

y el número de particiones de n en las que todas las partes son 1, 2 o 3 (o, de manera equivalente, el número de particiones de n en un máximo de tres partes) es el entero más cercano a (n + 3)² / 12.

Particiones en un rectángulo y coeficientes binomiales gaussianos

También se puede limitar simultáneamente el número y el tamaño de las partes. Denote $p (N, M; n)$ el número de particiones de $n$ con como máximo $M$ partes, cada una de tamaño máximo $N$ . De manera equivalente, estas son las particiones cuyo diagrama de Young encaja dentro de un rectángulo $M \times N$ . Hay una relación de recurrencia

{displaystyle p(N,M;n)=p(N,M-1;n)+p(N-1,M;n-M)}

p(N,M;n)-p(N,M-1;n)

n

M

N

n - M

M

El coeficiente binomial de Gauss se define como:

{displaystyle {k+ell choose ell }_{q}={k+ell choose k}_{q}={frac {prod _{j=1}^{k+ell }(1-q^{j})}{prod _{j=1}^{k}(1-q^{j})prod _{j=1}^{ell }(1-q^{j})}}.}

p () N, M; n)

{displaystyle sum _{n=0}^{MN}p(N,M;n)q^{n}={M+N choose M}_{q}.}

Rango y plaza Durfee

El rango de una partición es el mayor número k tal que la partición contiene al menos k partes de tamaño al menos k. Por ejemplo, la partición 4 + 3 + 3 + 2 + 1 + 1 tiene rango 3 porque contiene 3 partes que son ≥ 3, pero no contiene 4 partes que son ≥ 4. En el diagrama de Ferrers o el diagrama de Young de una partición de rango r, el cuadrado de entradas r × r en la parte superior izquierda se conoce como el cuadrado de Durfee:

El cuadrado de Durfee tiene aplicaciones dentro de la combinatoria en las pruebas de varias identidades de partición. También tiene algún significado práctico en forma de índice h.

Una estadística diferente también se llama a veces el rango de una partición (o rango Dyson), es decir, la diferencia ${displaystyle lambda _{k}-k}$ para una partición de k partes con mayor parte $lambda _{k}$ . Esta estadística (que no está relacionada con la descrita anteriormente) aparece en el estudio de las congruencias de Ramanujan.

Enrejado de Young

Hay un orden parcial natural en las particiones dado por la inclusión de diagramas de Young. Este conjunto parcialmente ordenado se conoce como Red de Young. La red se definió originalmente en el contexto de la teoría de la representación, donde se usa para describir las representaciones irreducibles de grupos simétricos S_n para todo n, junto con sus propiedades de ramificación, en la característica cero. También ha recibido un estudio significativo por sus propiedades puramente combinatorias; en particular, es el ejemplo motivador de una pose diferencial.

Contenido relacionado

Más resultados...