Número de formas de particionar un número$n$ de manera única.

Question

Dado cualquier número$n$, ¿cuál es el método de búsqueda de cuántas formas posibles (único) en el que hay puede partición de la misma, con la condición de que todos los números en cada "parte" debe ser mayor o igual a 5.

por ejemplo, decir $n = 17$

Por eso, $17$ puede ser escrita como:

1. $17$

2. $5 + 12$ (desde el número mínimo en cada parte debe ser de 5)

3. $ 6 + 11 $

4. $ 7 + 10 $

5. $ 8 + 9 $ (lo mismo que $9 + 8$)

6. $ 5 + 6 + 6 $

7. $ 5 + 7 + 7 $

Por lo $17$ puede ser dividido en $7$ maneras.

La pregunta entonces es, ¿cuál es el algoritmo para encontrar el número de todas las formas posibles (las formas en sí mismos no son importantes)?

A mi manera: uso de la DP.

Digamos que la función que se va a escribir es $f$.

Calcular $f(5)$ ( $= 1$), recuerde. Del mismo modo calcular el $f(6)...f(9)$

Ahora, llegando a $f(10)$ desde las 10, en la mayoría de nosotros puede cortar $5$ y, por tanto, $10 = 5 + 5$

Hacer esto de forma recursiva y la comprobación de duplicados.

El problema con mi método: Pero esto parece un muy ingenuo algoritmo y parece ser lento (con todas las de la comprobación de duplicados).

Por lo tanto, estoy buscando algún método mejor.

Answer 1

Tenga en cuenta que tenemos a la lista de particiones en orden creciente para evitar duplicados. De ello se desprende que necesitamos saber, en determinada instancia de este proceso, el número de $n$ a de la partición y un límite inferior que empezamos a partición de este número. Si consideras $f(n,m)$ significa que el número de maneras de partición de la $n$ con los números de $\geqslant m$, en orden creciente (posiblemente $0$ números si $m>n$), luego de una recurrencia es

$f(n,m) = \sum\limits_{i = m}^n {f(n - i,i)}$ si $n\geqslant1$,

y en el caso base sería al $n=0$, no importa el valor de $m$, el número de maneras de partiton $0$ es 1. Así

$f(0,m) = 1$.

A continuación, la respuesta va a ser $f(n,5)$.

Answer 2

La pregunta era realmente enorme y yo temía que la gente iba a rozar el texto. Así que voy a añadir este aquí (el siguiente es bastante respuesta-ish también!)

Una visión interesante:

Mientras se trabaja manualmente los números hasta 20, me enteré de todo un hecho sorprendente (que parece tener para todos los enteros) acerca de la repetición.

Así, calcular el $f$$ 10 $$15$.

$10 \to 10, 5+5$

$11 \to 11, 6+5$

...

$14 \to 14, 5+9, 6+8, 7+7$

... hasta que $16$.

La parte interesante viene aquí:

Considere la posibilidad de $f(17)$

$17 \to 17$

$17 \to 5+12 \to \{ 5+6+6, 5+5+7 \}$ (con el resultado de 12)

$17 \to 6+11 \to \mathfrak{\{ 6+5+6 \}}$ (REPETICIÓN utilizando el resultado de 11)

$17 \to 7+10 \to \mathfrak{\{ 7+5+5 \}}$ (REPETICIÓN utilizando el resultado de 10)

$17 \to 8+9$

La cosa que notamos es (como se verá por trabajar manualmente hasta 20 o más tal vez) es que una vez que obtenga una repetición, su más los intentos de ampliar el ampliable números (por ejemplo, 12,11,10 en los casos anteriores) será inútil - todos ellos serán repeticiones. La condición para que tal cosa ocurra es si se ve de esta manera:

En primer lugar, ir hacia abajo (es decir, en el 17 de ejemplo, dividir primero como $5+12$ y, a continuación, mueva hacia abajo a $6+11$ etc.) y, a continuación, para cada respuesta que usted acaba de conseguir, mientras que hacia abajo, 'ampliar' utilizando los resultados anteriores.

Segundo, cuando se están expandiendo a un número utilizando sus calculado previamente la partición, tomar las particiones de ese número en orden descendente.

por ejemplo, cuando se va a ampliar el$14$$20 = 6 + 14$, escribir $20$ como:

$20 = 6 + (7+7)$

$20 = 6 + (6+8)$

$20 = 6 + (5+9)$

etc.

Sé que esto es bastante extraño, pero parece estar funcionando. Sugerencias/ideas?

Answer 3

Este tipo de pensamiento conduce a relaciones de recurrencia que son una manera muy útil para enumerar las particiones entre otras cosas. Usted necesita tener cuidado-no veo la manera de asegurarse de que no cuenta tanto $17=6+11=6+5+6$$17=5+12=5+6+6$. Es una manera de mantener los números ordenados. Definir $F(n,k)$ como el número de particiones de $n$ en piezas de, al menos,$k$. A continuación, puede escribir $$F(n,5)=\sum_{i=5}^\infty F(n-5,i)\\F(n,6)=\sum_{i=6}^\infty F(n-6,i)$$,etc.