el número de formas de dividir un número entero.

Question

Una partición de un entero positivo n es una forma de writingn como suma de enteros positivos.

Suma de dos que sólo difieren en el orden de los sumandos son considerados de la misma partición.

Por ejemplo, 4 se puede dividir en cinco formas distintas:

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

Vamos q(n) es el número de particiones de n en potencias de 2 (Aquí p(0) = 1, p(1) = 1).

Para ejemplo, si n = 4, tenemos

4

2 + 2

2 + 1+ 1

1 + 1 + 1 + 1

Demostrar que p(n) para todo n ≥ 2. Dar una combinatoria de la prueba.

Answer 1

El uso de la inducción. Verificación de la base de casos.

Echemos un vistazo a las particiones de $2n+1$. Cada partición de $2n+1$ incluye número impar de $1$s. Si la partición contiene $2k+1$ $1$s, todos los otros términos son incluso. Este tipo de particiones que pueden ser identificados con las particiones de $n-k$ mediante la división de los números pares, por $2$. Por eso, $q(2n+1)=q(n)+q(n-1)+\ldots+q(2)+q(1)+1$ donde $1$ al final representa la partición consiste únicamente en $1$s. Como todo, excepto $q(1)$ es incluso en esta suma, $q(2n+1)$ es también incluso.

Ahora, mira las particiones de $2n$. Una partición contiene un número par de $1$s. Si la partición contiene $2k$ $1$s, todos los otros términos son incluso. Este tipo de particiones que pueden ser identificados con las particiones de $n-k$ mediante la división de los números pares, por $2$. Por eso, $q(2n)=q(n)+q(n-1)+\ldots+q(2)+q(1)+1$ donde $1$ al final representa la partición consiste únicamente en $1$s. Como todo, excepto $q(1)$ es incluso en esta suma, $q(2n)$ es también incluso.