El número de particiones de $n$ en partes distintas es igual al número de particiones de $n$ en partes de impar

Question

Este parece ser un resultado común. He tratado de seguir la prueba biyectiva de la misma, que se puede encontrar fácilmente en Internet, pero las explicaciones pasan por encima de mi cabeza. Sería estupendo que me dierais una explicación comprensible de la prueba y que me dijerais cómo debo hacer para encontrar dicha biyección.

Answer 1

Daré un esbozo de la prueba biyectiva; pregúntame si hay alguna parte que no entiendas y necesites que se desarrolle (o quizás alguien más publique una versión detallada).

La idea importante es que todo número puede expresarse de forma única como una potencia de 2 multiplicada por un número impar. (Dividir el número repetidamente por 2 hasta obtener un número impar.) Por ejemplo, $120 = 2^3 \times 15$ y $68 = 2^2 \times 17$ y $81 = 2^0 \times 81$ .

Partes Impares -> Partes Distintas

Supongamos que nos dan una partición de n en partes Impares. Cuente el número de veces que aparece cada número impar: suponga $1$ se produce $a_1$ veces, de manera similar $3$ se produce $a_3$ tiempos, etc. Así que $n = a_11 + a_33 + a_55 + \cdots$ .

Ahora escribe cada $a_i$ "en binario", es decir, como una suma de potencias distintas de dos. Así que tienes $n = (2^{b_{11}}+2^{b_{12}}+\cdots)1 + (2^{b_{31}}+2^{b_{32}}+\cdots)3 + \cdots$ .

Ahora sólo hay que deshacerse de los paréntesis, y observar que todos los términos son distintos. (¿Por qué?)

Por ejemplo, para $20 = 5+3+3+3+1+1+1+1+1+1$ que es una partición de $20$ en piezas de impar, hacemos
$20 = (1)5 + (3)3 + (6)1$
$20 = (1)5 + (2+1)3 + (4+2)1$ para que tengas la partición
$20 = 5 + 6 + 3 + 4 + 2$ en el que todas las partes son distintas.

Partes diferenciadas -> Partes Impares

Dada una partición en partes distintas, podemos escribir cada parte como una potencia de 2 multiplicada por un número impar, y recoger los coeficientes de cada número impar, y escribir el número impar tantas veces, para obtener una partición en partes impar.

Así, por ejemplo, con $20 = 5+6+3+4+2$ que es una partición de $20$ en partes distintas, escribimos $20 = 5 + (2)3 + 3 + (4)1 + (2)1$ y luego recoger los coeficientes de los números Impares $5$ , $3$ y $1$ :
$20 = 5 + (2+1)3 + (4+2)1$
$20 = 5+3+3+3+1+1+1+1+1+1$ que era nuestra partición original de impar.

---

Aparte: has preguntado por la demostración biyectiva, pero no me resisto a mencionar que cuando Euler demostró este teorema sobre las particiones, lo hizo con una demostración que utilizaba funciones generadoras. (Cuando entiendas ambas cosas, tal vez puedas pensar si esta prueba está relacionada con la prueba biyectiva).

Boceto: Deja $D(n)$ denotan el número de particiones en partes distintas, y $O(n)$ denotan el número de particiones en partes Impares. Entonces tenemos:

$$\begin{align} \sum_{n\ge0}D(n)x^n &= (1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5)\cdots \\ &= \frac{1-x^2}{1-x}\frac{1-x^4}{1-x^2}\frac{1-x^6}{1-x^3}\frac{1-x^8}{1-x^4}\frac{1-x^{10}}{1-x^5}\cdots \\ &= \frac{1}{(1-x)(1-x^3)(1-x^5)\cdots} \\ &= (1+x+x^{1+1}+\cdots)(1+x^3+x^{3+3}+\cdots)(1+x^5+x^{5+5}+\cdots) \\ &= \sum_{n\ge0}O(n)x^n \end{align}$$ que demuestra el teorema.