8.5: Particiones de un Entero
- Page ID
- 118347
Un tema recurrente en este curso ha sido contar el número de soluciones enteras a una ecuación de la forma\(x_1+x_2+ \cdot \cdot \cdot +x_k=n\). ¿Y si quisiéramos contar el número de tales soluciones pero no nos\(k\) importaba lo que fuera? ¿Qué tal si tomamos esta nueva pregunta y requerimos que el\(x_i\) sea distinto (es decir,\(x_i \neq x_j\) para\(i \neq j\))? ¿Y si requerimos que cada uno\(x_i\) fuera extraño? Estas ciertamente no parecen preguntas fáciles de responder al principio, pero generar funciones nos permitirá decir algo muy interesante sobre las respuestas a las dos últimas preguntas.
Por una partición\(P\) de un entero, nos referimos a una colección de enteros positivos (no necesariamente distintos) tales que\(\sum_{i \in P} i =n\). (Por convención, escribiremos los elementos de\(P\) de mayor a menor.) Por ejemplo, 2+2+1 es una partición de 5. Para cada uno\(n \geq 0\), vamos a denotar pn el número de particiones del entero\(n\) (con\(p_0=1\) por convención). Obsérvese que\(p_8=22\) como lo evidencia la lista en la Figura 8.15.
Tenga en cuenta que hay 6 particiones de 8 en partes distintas. También hay 6 particiones de 8 en partes impares. Si bien puede parecer que esto es una coincidencia, de hecho siempre es el caso como afirma el Teorema 8.16. Antes de mirar ese teorema y su prueba, pensemos en cómo sería una función generadora\(p_n\), el número de particiones de\(n\),. Dada una partición de\(n\), podemos contar cuántos 1 aparecen, cuántos 2 aparecen, y así sucesivamente. Esto sugiere una similitud con los problemas de nuestra canasta frutal anterior en el capítulo, lo que lleva a la función generadora
\(P(x) = ( \displaystyle \sum_{m=0}^{\infty} x^m ) (\sum_{m=0}^{\infty}x^{2m})(\sum_{m=0}^{\infty}x^{3m}) \cdot \cdot \cdot (\sum_{m=0}^{\infty} x^{km}) \cdot \cdot \cdot = \prod_{m=1}^{\infty} \dfrac{1}{1-x^m}\).
Aquí el factor cuya suma contiene términos\(x^{km}\) es contabilizar el número de\(k\)'s en la partición. Si bien\(P(x)\) tiene una forma bastante elegante, eso no significa que sea terriblemente útil para la computación\(p_n\). De hecho, proporcionar una estimación asintótica para\(p_n\) era un problema notoriamente difícil, finalmente abordado por Hardy y Ramanujan en 1918. Un relato popular de esto se puede encontrar en el libro de 1991 de Robert Kanigel El hombre que conocía al infinito o la película de 2016 con el mismo título.
Demostrar la relación entre el número de particiones en partes distintas y el número de particiones en partes impares implicará versiones restringidas de la función generadora\(P(x)\) desde arriba.
Para cada una\(n \geq 1\), el número de particiones de\(n\) en partes distintas es igual al número de particiones de\(n\) en partes impares.
- Prueba
-
La función de generación\(D(x)\) para el número de particiones de\(n\) en partes distintas es
\(D(x) = \displaystyle \prod_{n=1}^{\infty}(1 + x^n)\).
Por otro lado, la función generadora\(O(x)\) para el número de particiones de\(n\) en partes impares es
\(O(x) = \displaystyle \prod_{n=1}^{\infty} \dfrac{1}{1-x^{2n-1}}\).
Para ver eso\(D(x)=O(x)\), señalamos que\(1−x^{2n}=(1−x^n)(1+x^n)\) para todos\(n \geq 1\). Por lo tanto,
\(D(x) = \displaystyle \prod_{n=1}^{\infty}(1+x^n) = \prod_{n=1}^{\infty} \dfrac{1-x^{2n}}{1-x^n} = \dfrac{\prod_{n=1}^{\infty}(1-x^{2n})}{\prod_{n=1}^{\infty}(1-x^n)}\)
\(= \dfrac{\prod_{n=1}^{\infty}(1-x^{2n})}{\prod_{n=1}^{\infty}(1-x^{2n-1}) \prod_{n=1}^{\infty}(1-x^{2n})} = \displaystyle \prod_{n=1}^{\infty} \dfrac{1}{1-x^{2n-1}}\)
\(= O(x)\)