3.4: Particiones de números enteros
- Page ID
- 117085
Definición\(\PageIndex{1}\): Partition
Una partición de un entero positivo\(n\) es un multiconjunto de enteros positivos que suman a\(n\). Denotamos el número de particiones de\(n\) por\(p_n\).
Por lo general, una partición se escribe como una suma, no explícitamente como un multiconjunto. Usando la convención habitual de que una suma vacía es 0, decimos eso\(p_0=1\).
Ejemplo\(\PageIndex{1}\)
Los tabiques de 5 son\[\eqalign{ &5\cr &4+1\cr &3+2\cr &3+1+1\cr &2+2+1\cr &2+1+1+1\cr &1+1+1+1+1.\cr }\nonumber\] Así\(p_5=7\).
No hay una fórmula simple para\(p_n\), pero no es difícil encontrar una función generadora para ellos. Al igual que con algunos ejemplos anteriores, buscamos un producto de factores para que cuando se multipliquen los factores, el coeficiente de\(x^n\) es\(p_n\). Nos gustaría que cada\(x^n\) término represente una sola partición, antes de que se recopilen términos similares. Una partición se describe de manera única por el número de 1s, el número de 2s, y así sucesivamente, es decir, por los números de repetición del multiconjunto. Dedicamos un factor a cada entero:\[(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^6+\cdots)\cdots (1+x^k+x^{2k}+x^{3k}+\cdots)\cdots =\prod_{k=1}^\infty \sum_{i=0}^\infty x^{ik}.\nonumber\] Cuando este producto se expande, elegimos un término de cada factor de todas las formas posibles, con la condición adicional de que solo elegimos un número finito de términos “no 1". Por ejemplo, si elegimos\(x^3\) del primer factor,\(x^3\) del tercer factor,\(x^{15}\) del quinto factor, y 1s de todos los demás factores, obtenemos\(x^{21}\). En el contexto del producto, esto representa\(3\cdot 1+1\cdot3+3\cdot 5\), correspondiente a la partición\(1+1+1+3+5+5+5\), es decir, tres 1s, uno 3 y tres 5s. Cada factor es una serie geométrica; el factor\(k\) th es\[ 1+x^k+(x^{k})^2+(x^{k})^3+\cdots= {1\over1-x^k},\nonumber\] así que la función generadora se puede escribir\[\prod_{k=1}^\infty {1\over 1-x^k}.\nonumber\] Tenga en cuenta que si nos interesa algún particular\(p_n\), no necesitamos todo el producto infinito, o incluso cualquier factor completo, ya que ninguna partición de\(n\) puede usar cualquier entero mayor que\(n\), y tampoco puede usar más de\(n/k\) copias de\(k\).
Ejemplo \(\PageIndex{2}\)
Encuentra\(p_8\).
Solución
Ampliamos
\[\eqalign{ (1+x&+x^2+x^3+x^4+x^5+x^6+x^7+x^8)(1+x^2+x^4+x^6+x^8)(1+x^3+x^6)\cr (1&+x^4+x^8)(1+x^5)(1+x^6)(1+x^7)(1+x^8)\cr &=1+x+2x^2+3x^3+5x^4+7x^5+11x^6+15x^7+22x^8+\cdots+x^{56},\cr }\nonumber \]
así\(p_8=22\). Tenga en cuenta que todos los coeficientes anteriores a esto también son correctos, pero los siguientes coeficientes no son necesariamente los números de partición correspondientes. Aquí se explica cómo usar Sage para el cómputo. Definimos\(f=\prod_{k=1}^8 {1\over 1-x^k}\) para asegurarnos de que el\(x^8\) coeficiente sea correcto. En lugar de hacer el producto explícito anterior, usamos Sage para calcular la serie Taylor, que tiene el mismo efecto.
f=prod([1/(1-x^k) for k in range (1,9)]); f; f.taylor(x,0,8)
Las particiones de enteros tienen algunas propiedades interesantes. Dejar\(p_d(n)\) ser el número de particiones de\(n\) en partes distintas; dejar\(p_o(n)\) ser el número de particiones en partes impares.
Ejemplo\(\PageIndex{3}\)
Para\(n=6\), las particiones en partes distintas son\[6,5+1,4+2,3+2+1,\nonumber\] así\(p_d(6)=4\), y las particiones en partes impares son\[5+1,3+3,3+1+1+1,1+1+1+1+1+1,\nonumber\] así\(p_o(6)=4\).
De hecho, para cada\(n\),\(p_d(n)=p_o(n)\), y podemos ver esto manipulando funciones generadoras. La función generadora para\(p_d(n)\) es\[f_d(x)=(1+x)(1+x^2)(1+x^3)\cdots=\prod_{i=1}^\infty (1+x^i).\nonumber\] La función generadora para\(p_o(n)\) es\[f_o(x)=(1+x+x^2+x^3+\cdots)(1+x^3+x^6+x^9+\cdots)\cdots= \prod_{i=0}^\infty {1\over 1-x^{2i+1}}.\nonumber\] Podemos escribir\[f_d(x)={1-x^2\over 1-x}\cdot{1-x^4\over 1-x^2}\cdot{1-x^6\over 1-x^3}\cdots\nonumber\] y notar que cada numerador es eventualmente cancelado por un denominador, dejando solo los denominadores que contienen potencias impares de\(x\), entonces\( f_d(x)=f_o(x)\).
También podemos usar una relación de recurrencia para encontrar los números de partición, aunque de una manera algo menos directa que los coeficientes binomiales o los números de Bell. Dejar\(p_k(n)\) ser el número de particiones de\(n\) en exactamente\(k\) partes. Encontraremos una relación de recurrencia para calcular la\(p_k(n)\), y luego\[ p_n=\sum_{k=1}^n p_k(n). \nonumber\] Ahora consideraremos las particiones de\(n\) en\(k\) partes. Algunas de estas particiones no contienen 1s, como\(3+3+4+6\), una partición de 16 en 4 partes. Al restar 1 de cada parte, obtenemos una partición de\(n-k\) en\(k\) partes; para el ejemplo, esto es\(2+2+3+5\). Las particiones restantes de\(n\) en\(k\) partes contienen un 1. Si retiramos el 1, nos quedamos con una partición de\(n-1\) en\(k-1\) partes. Esto nos da una correspondencia 1—1 entre las particiones de\(n\) en\(k\) partes, y las particiones de\(n-k\) en\(k\) partes junto con las particiones de\(n-1\) en\(k-1\) partes, entonces\(p_k(n)=p_k(n-k)+p_{k-1}(n-1)\).
Usando esta recurrencia podemos construir un triángulo que contenga el\(p_k(n)\), y las sumas de filas de este triángulo dan los números de partición. Para todos\(n\),\(p_1(n)=1\), lo que da la primera columna del triángulo, después de lo cual se aplica la recurrencia. También, tenga en cuenta que\(p_k(n)=0\) cuando\(k>n\) y dejamos\(p_k(0)=0\); estos son necesarios en algunos casos para computar el\(p_k(n-k)\) término de la recurrencia. Aquí están las primeras filas del triángulo; a la izquierda están los números de fila, y a la derecha están las sumas de fila, es decir, los números de partición. Para la última fila, cada entrada es la suma de los números de color similar en las filas anteriores. Tenga en cuenta que comenzando con\(p_4(7)=3\) en la última fila,\(p_k(7)=p_{k-1}(6)\), como\(p_k(7-k)=0\).
\[\matrix{ 1 & 1& & & & & & & 1\cr 2 & 1& 1& & & & & & 2\cr 3 & 1& 1& 1& & & & & 3\cr 4 & 1& 2& \color{green}1& 1& & & & 5\cr 5 & 1& \color{red}2& 2& 1& 1& & & 7\cr 6 & \color{red}1& \color{green}3& \color{blue}3& \color{orange}2& \color{purple}1& \color{fuchsia}1& & 11\cr 7 & 1& \color{red}3& \color{green}4& \color{blue}3& \color{orange}2& \color{purple}1& \color{fuchsia}1& 15\cr }\nonumber\]
Otra forma más a veces útil de pensar en una partición es con un diagrama de Ferrers. Cada entero en la partición está representado por una fila de puntos, y las filas se ordenan desde más largas en la parte superior hasta más cortas en la parte inferior. Por ejemplo, la partición\(3+3+4+5\) estaría representada por
El conjugado de una partición es el correspondiente al diagrama de Ferrers producido al voltear el diagrama para la partición original a través de la diagonal principal, convirtiendo así las filas en columnas y viceversa. Para el diagrama anterior, el conjugado es
con partición correspondiente\(1 + 2+4+4+4\). Este concepto ocasionalmente puede hacer que los hechos sobre particiones sean más fáciles de ver que de otra manera. Aquí hay un ejemplo clásico: el número de particiones de\(n\) con mayor parte\(k\) es el mismo que el número de particiones en\(k\) partes,\(p_k(n)\). La acción de la conjugación lleva cada partición de un tipo en una partición del otro: el conjugado de una partición en\(k\) partes es una partición con la parte más grande\(k\) y viceversa. Esto establece una correspondencia 1—1 entre particiones en\(k\) partes y particiones con mayor parte\(k\).