Dividir un número

Una partición de un número natural es una representación de un número como una suma de números enteros positivos que, a diferencia de la composición , no tiene en cuenta el orden de los términos. Los términos en la partición se llaman partes . En la representación canónica de la partición, los términos se enumeran en orden no creciente. $norte$ $norte$ ${\ estilo de visualización \ lambda _ {1} + \ lambda _ {2} + \ puntos + \ lambda _ {m}}$ $\lambda_k$

Si , entonces la partición correspondiente a este conjunto de números generalmente se denota como { } = . En este caso, el número se denomina potencia de partición y se denota como , y el número se denomina longitud de partición y se denota como . ${\ estilo de visualización \ lambda _ {1} \ geq \ lambda _ {2} \ puntos \ geq \ lambda _ {m}}$ ${\ estilo de visualización \ lambda _ {1}, \ lambda _ {2}, \ puntos \ lambda _ {m}}$ $\lambda$ $norte$ $|\lambda|$ $metro$ ${\ estilo de visualización l (\ lambda)}$

El número de particiones de un número natural es uno de los objetos de estudio fundamentales en combinatoria . $p(n)$ $norte$

Ejemplos

Por ejemplo, {3, 1, 1 } o {3, 2 } son particiones de 5, ya que 5 = 3 + 1 + 1 = 3 + 2 . Hay 5 particiones en total: {1, 1, 1, 1, 1 }, {2, 1, 1, 1 }, {2, 2, 1 }, {3, 1, 1 }, {3, 2 } , {4, 1 }, {5}. ${\ estilo de visualización p (5) = 7}$

Algunos valores para el número de particiones se dan en la siguiente tabla [1] : $p(n)$

norte	pag ( n )	Particiones
una	una	{una}
2	2	{2}, {1, 1 }
3	3	{3}, {2, 1 }, {1, 1, 1 }
cuatro	5	{4}, {3, 1 }, {2, 2 }, {2, 1, 1 }, {1, 1, 1, 1 }
5	7	{5}, {4, 1 }, {3, 2 }, {3, 1, 1 }, {2, 2, 1 }, {2, 1, 1, 1 }, {1, 1, 1, 1 , 1 },
6	once
7	quince
ocho	22
9	treinta
diez	42
veinte	627
cincuenta	204 226
100	190 569 292
1000	24061467864032622473692149727991
10000	36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144

Número de particiones

Función generadora

La secuencia del número de particiones tiene la siguiente función generadora : $p(n)$

\sum _{{n=0}}^{\infty }p(n)x^{n}=\prod _{{k=1}}^{\infty }{\frac {1}{1-x ^{k}}}.

Esta fórmula fue descubierta por Euler en 1740.

Teorema del pentágono de Euler

Al estudiar la función generadora de la sucesión , Euler se centró en su denominador, es decir, en el producto . Cuando se abren los paréntesis, este producto infinito toma la siguiente forma: $p(n)$ ${\ estilo de visualización (1-x)(1-x^{2})(1-x^{3})...}$

(1-x)(1-x^{2})(1-x^{3})\ldots =1-xx^{2}+x^{5}+x^{7}-x ^{12}-x^{15}+x^{22}+x^{26}-x^{35}-x^{40}+\ldots

En el lado derecho, los términos tienen la forma donde recorre todos los valores enteros posibles , y en este caso los números mismos se llaman pentagonales generalizados . Cuando son naturales , se les llama simplemente pentagonales. [2] $(-1)^{q}x^{(3q^{2}-q)/2},$ $q$ ${\ estilo de visualización (3q^{2}-q)/2}$ $q$

A partir de esta observación, Euler conjeturó el Teorema del Pentagonal :

\prod_{k=1}^{\infty}\left(1-x^{k}\right)=\sum_{q=-\infty}^{\infty}(-1)^ {q}x^{(3q^{2}-q)/2},

y luego lo probó. Este teorema permite calcular el número de particiones mediante la división de series de potencias formales .

Fórmulas asintóticas

Hardy y Ramanujan obtuvieron una expresión asintótica para el número de particiones en 1918, e independientemente en 1920 por el matemático ruso Uspensky : [3]

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

n\rightarrow\infty

Por ejemplo, . $p(1000)\aproximadamente 2{,}44\cdot 10^{31}$

Posteriormente, Hardy y Ramanujan encontraron una expresión más precisa en forma de suma, y Rademacher derivó una serie convergente exacta , a partir de la cual se pueden encontrar representaciones asintóticas arbitrariamente cercanas:

p(n)={\frac {1}{\pi {\sqrt {2))))\sum _{k=1}^{\infty }A_{k}(n)\;{\ sqrt {k}}\;{\frac {d}{dn}}\left({\frac {\sinh \left({\frac {\pi }{k}}{\sqrt {{\frac {2} {3}}\left(n-{\frac {1}{24}}\right)}}\right)}{\sqrt {n-{\frac {1}{24}}}}}\right) ,

dónde

A_{k}(n)=\sum_{\begin{pequeña matriz}0\leqslant m<k\\(m,k)=1\end{pequeña matriz}}\exp \left(\pi i\ cdot s(m,k)-2\pi in\cdot m/k\right).

Aquí la suma ha terminado , es coprima y es la suma de Dedekind . La serie converge muy rápidamente. $metro$ $k$ $s(m,k)$

Fórmulas recurrentes

El número de particiones de un número en términos que no excedan satisface la fórmula recursiva : $norte$ $k$

P(n,\;k)={\begin{casos}P(n,\;k-1)+P(nk,\;k),&k\leqslant n,\\P(n,\ ;n),&k>n,\end{casos}}

con valores iniciales:

{\ estilo de visualización P (0, \; 0) = 1,}

P(i,\;0)=0

para todos

yo>0

En este caso, el número de particiones posibles del número es igual a . $norte$ ${\ estilo de visualización PAG (n, \; n)}$

Diagramas jóvenes

Las particiones se representan convenientemente como objetos geométricos visuales, llamados diagramas de Young , en honor al matemático inglés Alfred Young . El diagrama de Young de partición es un subconjunto del primer cuadrante del plano, dividido en celdas, cada una de las cuales es una unidad cuadrada. Las celdas están dispuestas en filas, la primera fila es de length , encima hay una fila de length , y así sucesivamente hasta la -ésima fila de length . Las filas se alinean a la izquierda. $(k_{1},\;k_{2},\;\ldots,\;k_{m})$ $k_{1}$ $k_{2}$ $metro$ $k_m$

Más formalmente, el diagrama de Young es el cierre del conjunto de puntos tal que $(x,\;y)$

{\ estilo de visualización x, \ y> 0}

y<\sum_{{j=[x]}}^{{m}}k_{j},

donde denota la parte entera . $[X]$ $X$

En la literatura inglesa, los diagramas de Young a menudo se representan reflejados en torno al eje x .

Un objeto similar, llamado carta de Ferrers , difiere en que

se muestran puntos en lugar de celdas;
el gráfico se transpone: las filas y las columnas se invierten.

La partición conjugada (o transpuesta) de k es una partición cuyo diagrama de Young es el diagrama de Young de la partición reflejada con respecto a la recta . Por ejemplo, el conjugado de la partición (6,4,4,1) es la partición (4,3,3,3,1,1). La partición conjugada se denota por . $\lambda$ $\lambda$ ${\ estilo de visualización y = x}$ ${\ estilo de visualización \ lambda '}$

Suma y producto de particiones

Sean dos particiones y . Entonces se definen las siguientes operaciones para ellos: $\lambda$ $\mu$

${\ estilo de visualización \ lambda + \ mu}$ : ; ${\ estilo de visualización (\ lambda + \ mu) _ {i} = \ lambda _ {i} + \ mu _ {i}}$
${\ estilo de visualización \ lambda \ taza \ mu}$ : una partición que contiene partes y en orden descendente no estricto; $\lambda$ $\mu$
${\ estilo de visualización \ lambda \ mu}$ : ; ${\ estilo de visualización (\ lambda \ mu) _ {i} = \ lambda _ {i} \ mu _ {i}}$
${\ estilo de visualización \ lambda \ veces \ mu}$ : una partición que contiene partes para todos y todos en un orden descendente no estricto. $min(\lambda_{i},\mu_{j})$ ${\ Displaystyle i \ leq l (\ lambda)}$ ${\ estilo de visualización j \ leq l (\ mu)}$

Las operaciones de suma, como las operaciones de multiplicación, son duales con respecto a la conjugación:

(\lambda\cup\mu)'=\lambda'+\mu'

;

(\lambda \times \mu )'=\lambda '\mu '

Ordenar

Que haya dos particiones y números . $\lambda$ $\mu$ $norte$

Orden lexicográfico. Se dice que es más antiguo en orden lexicográfico si existe un número natural tal que para cada uno , y también . $\lambda$ $\mu$ $k$ ${\ estilo de visualización \ lambda _ {i} = \ mu _ {i}}$ ${\ estilo de visualización i<k}$ ${\ estilo de visualización \ lambda _ {k}> \ mu _ {k}}$

En la tabla anterior, las particiones están dispuestas en orden lexicográfico.

Orden natural (parcial). Se dice que es mayor en orden natural (indicado por ) si la desigualdad se cumple para cada . $\lambda$ $\mu$ ${\ estilo de visualización \ lambda \ geq \ mu}$ ${\ estilo de visualización i \ geq 1}$ $\lambda _{1}+\lambda _{2}+\dots +\lambda _{i}\geq \mu _{1}+\mu _{2}+\dots +\mu _{i} }$

A partir de n=6 se pueden encontrar particiones que no se pueden comparar en este sentido. Por ejemplo, (3, 1, 1, 1) y (2, 2, 2).

Para el orden natural, la equivalencia se cumple:

\lambda \geq \mu \Leftrightarrow \mu '\geq \lambda'.

Aplicación

Las particiones surgen naturalmente en una serie de problemas matemáticos. La más significativa de ellas es la teoría de la representación del grupo simétrico , donde las particiones parametrizan naturalmente todas las representaciones irreducibles . Las sumas sobre todas las particiones ocurren a menudo en el cálculo .

Véase también

Notas

↑ Secuencia A000041 en OEIS
↑ Tabachnikov S. L., Fuchs D. B. Diversión matemática. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
↑ Uspensky, Fórmulas asintóticas para funciones numéricas que ocurren en la teoría de las particiones, Bol. Academia ciencia URSS 14, 1920, S. 199–218

Literatura

Andrews G. Teoría de la partición. — M.: Nauka, 1982. — 255 p.
McDonald I. Funciones simétricas y polinomios de Hall. — M.: Mir, 1985. — 224 p.
Vainshtein F.V. Particionamiento de números // Kvant . - 1988. - Nº 11 . - S. 19-25 .
Fuchs D. Sobre la apertura de paréntesis, sobre Euler, Gauss, Macdonald y oportunidades perdidas // Kvant . - 1981. - Nº 8 . - S. 12-20 .
Nueva teoría prueba la naturaleza de los números .
Burman Yu. M. Particiones y permutaciones // Escuela de verano "Matemáticas modernas". — 2004.