8.5: Particiones de un Entero

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.

Figura 8.15. Las particiones de 8, señalando esas en partes distintas y aquellas en partes impares.

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.

Teorema 8.16

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)$