Partición de enteros

En teoría de números y combinatoria , una partición de un entero no negativo n , también llamada partición entera , 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 importa, la suma se convierte en una composición ). Por ejemplo, 4 se puede particionar de cinco maneras distintas:

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

La única partición de cero es la suma vacía, que no tiene partes.

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 llama parte . El número de particiones de n viene dado por la función de partición p ( n ) . Así, p (4) = 5 . La notación λ ⊢ n significa que λ es una partición de n .

Las particiones pueden visualizarse gráficamente mediante diagramas de Young o diagramas de Ferrers . Aparecen en diversas ramas de las matemáticas y la física , incluyendo el estudio de los polinomios simétricos y del grupo simétrico , así como en la teoría de la representación de grupos en general.

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 no creciente de sumandos, en lugar de una expresión con signos de suma. 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 ² , 1) , donde el superíndice indica el número de repeticiones de una parte.

Esta notación de multiplicidad para una partición se puede escribir alternativamente como${\displaystyle 1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots }$donde m ₁ es el número de 1, m ₂ es el número de 2, etc. (Los componentes con m _i = 0 pueden omitirse). Por ejemplo, en esta notación, las particiones de 5 se escriben${\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}}$.

Existen dos métodos diagramáticos comunes para representar particiones: los diagramas de Ferrers, que reciben su nombre de Norman Macleod Ferrers , y los diagramas de Young, que reciben su nombre de Alfred Young . Ambos presentan diversas convenciones; aquí utilizamos la notación inglesa , con los diagramas alineados en la esquina superior izquierda.

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

La función generadora de${\displaystyle 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 analítica para la función de partición, pero posee expansiones asintóticas que la aproximan con precisión y relaciones de recurrencia mediante las cuales puede calcularse exactamente. Crece como una función exponencial de la raíz cuadrada de su argumento, ^{[ 3 ]} de la siguiente manera:

${\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right)}$como${\displaystyle n\to \infty }$

En 1937, Hans Rademacher encontró una manera de representar la función de partición.${\displaystyle p(n)}$por la serie convergente

$${\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n){\sqrt {k}}\cdot {\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\sinh \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\,\,\,\right]}\right)}$$ dónde

$${\displaystyle A_{k}(n)=\sum _{0\leq m<k,\;(m,k)=1}e^{\pi i\left(s(m,k)-2nm/k\right)}.}$$ y${\displaystyle s(m,k)}$es la suma de Dedekind .

La inversa multiplicativa de su función generadora es la función de Euler ; según el teorema de los números pentagonales de Euler, esta función es una suma alternada de potencias de números pentagonales de su argumento.

${\displaystyle 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 no triviales en la aritmética modular , ahora conocidos como las congruencias de Ramanujan . Por ejemplo, siempre que la representación decimal de${\displaystyle n}$termina en el dígito 4 o 9, el número de particiones de${\displaystyle n}$será divisible por 5. ^{[ 4 ]}

Tanto en combinatoria como en teoría de números, se estudian con frecuencia familias de particiones sujetas a diversas restricciones. ^{[ 5 ]} Esta sección examina algunas de dichas restricciones.

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 sean  ≥  4. En el diagrama de Ferrers o diagrama de Young de una partición de rango r , el cuadrado r × r de entradas en la esquina superior izquierda se conoce como el cuadrado de Durfee :

El cuadrado de Durfee tiene aplicaciones dentro de la combinatoria en las demostraciones de varias identidades de partición. ^{[ 16 ]} También tiene cierta importancia práctica en forma del índice h .

Otra estadística también se denomina a veces rango de partición (o rango de Dyson), es decir, la diferencia${\displaystyle \lambda _{k}-k}$para una partición de k partes con la parte más grande${\displaystyle \lambda _{k}}$Esta estadística (que no guarda relación con la descrita anteriormente) aparece en el estudio de las congruencias de Ramanujan .

Existe un orden parcial natural en las particiones dadas por la inclusión de diagramas de Young. Este conjunto parcialmente ordenado se conoce como retículo de Young . El retículo se definió originalmente en el contexto de la teoría de la representación , donde se utiliza para describir las representaciones irreducibles de grupos simétricos S _n para todo n , junto con sus propiedades de ramificación, en característica cero. También ha sido objeto de un estudio significativo por sus propiedades puramente combinatorias; en particular, es el ejemplo que motiva un poset diferencial .

Existe una teoría profunda de particiones aleatorias elegidas según la distribución de probabilidad uniforme en el grupo simétrico mediante la correspondencia de Robinson-Schensted . En 1977, Logan y Shepp, así como Vershik y Kerov, demostraron que el diagrama de Young de una partición grande típica se aproxima asintóticamente a la gráfica de una cierta función analítica que minimiza un cierto funcional. En 1988, Baik, Deift y Johansson extendieron estos resultados para determinar la distribución de la subsecuencia creciente más larga de una permutación aleatoria en términos de la distribución de Tracy-Widom . ^{[ 17 ]} Okounkov relacionó estos resultados con la combinatoria de superficies de Riemann y la teoría de la representación. ^{[ 18 ] [ 19 ]}

• Abramowitz, Milton ; Stegun, Irene (1964). Manual de funciones matemáticas con fórmulas, gráficas y tablas matemáticas . Departamento de Comercio de los Estados Unidos, Oficina Nacional de Estándares. ISBN 0-486-61272-4.{{cite book}}: Incompatibilidad de ISBN/Fecha ( ayuda )
• Andrews, George E. (1976). La teoría de las particiones . Cambridge University Press. ISBN 0-521-63766-X.
• Andrews, George E.; Eriksson, Kimmo (2004). Particiones enteras . Cambridge University Press. ISBN 0-521-60090-1.
• Apostol, Tom M. (1990) [1976]. Funciones modulares y series de Dirichlet en teoría de números . Textos de posgrado en matemáticas . Vol.  41 (2.ª  ed.). Nueva York, etc.: Springer-Verlag . ISBN 0-387-97127-0. Zbl 0697.10023 . (Véase el capítulo 5 para una introducción pedagógica moderna a la fórmula de Rademacher) .
• Bóna, Miklós (2002). Un recorrido por la combinatoria: una introducción a la enumeración y la teoría de grafos . World Scientific Publishing. ISBN 981-02-4900-4.(Una introducción elemental al tema de las particiones enteras, que incluye una discusión sobre los grafos de Ferrers)
• Hardy, GH ; Wright, EM (2008) [1938]. Introducción a la teoría de los números . Revisado por DR Heath-Brown y JH Silverman . Prólogo de Andrew Wiles . (6.ª  ed.). Oxford: Oxford University Press . ISBN 978-0-19-921986-5. SEÑOR 2445243 . Zbl 1159.11001 .  
• Lehmer, DH (1939). " Sobre el resto y la convergencia de la serie para la función de partición" . Trans. Amer. Math. Soc . 46 : 362–373 . doi : 10.1090/S0002-9947-1939-0000410-9 . MR 0000410. Zbl 0022.20401 .  Proporciona la fórmula principal (sin derivadas), el resto y la forma anterior para A _k ( n ).)
• Gupta, Hansraj; Gwyther, CE; Miller, JCP (1962). Royal Society of Math. Tables . Vol.  4, Tablas de particiones.(Tiene texto, bibliografía casi completa, pero ellos (y Abramowitz) omitieron la fórmula de Selberg para A _k ( n ), que está en Whiteman.)
• Macdonald, Ian G. (1979). Funciones simétricas y polinomios de Hall . Monografías matemáticas de Oxford. Oxford University Press . ISBN 0-19-853530-9. Zbl 0487.20007 . (Véase la sección I.1)
• Nathanson, MB (2000). Métodos elementales en teoría de números . Textos de posgrado en matemáticas. Vol.  195. Springer-Verlag . ISBN 0-387-98912-9. Zbl 0953.11002 . 
• Rademacher, Hans (1974). Documentos recopilados de Hans Rademacher . vol.  vII. Prensa del MIT. Págs. 100–07 , 108–22 , 460–75 . 
• Sautoy, Marcus Du. (2003). La música de los números primos . Nueva York: Perennial-HarperCollins. ISBN 9780066210704.
• Stanley, Richard P. (1999). Combinatoria enumerativa . Vol.  1 y 2. Cambridge University Press. ISBN 0-521-56069-1.
• Whiteman, AL (1956). "Una suma relacionada con la serie para la función de partición" . Pacific Journal of Mathematics . 6 (1): 159– 176. doi : 10.2140/pjm.1956.6.159 . Zbl 0071.04004 . (Proporciona la fórmula de Selberg. La forma anterior es la expansión de Fourier finita de Selberg).

• "Partición" , Enciclopedia de Matemáticas , EMS Press, 2001 [1994]
• Calculadora de partición y composición
• Weisstein, Eric W. "Partición" . MundoMatemático .
• Wilf, Herbert S. Lecciones sobre particiones enteras (PDF) , archivado del original (PDF) el 26 de febrero de 2021 , consultado el 28 de febrero de 2021.
• Conteo con particiones con tablas de referencia a la Enciclopedia en línea de secuencias de enteros.
• Particiones enteras Archivadas el 22/10/2014 en la entrada de Wayback Machine en la base de datos FindStat
• Módulo Perl Integer::Partition de CPAN
• Algoritmos rápidos para generar particiones enteras
• Generación de todas las particiones: una comparación de dos codificaciones
• Grime, James (28 de abril de 2016). "Partitions - Numberphile" (vídeo) . Brady Haran . Archivado del original el 11 de diciembre de 2021. Consultado el 5 de mayo de 2016 .