¿Lo que ' s el nombre de este problema?

Question

Problema: contar el número de maneras distintas de escribir el número de X como la suma de los números {a, b, c,...} con la sustitución. Por ejemplo, hay 3 formas de escribir las 11:
2+2+7
2+2+2+2+3
2+3+3+3

Y si recuerdo correctamente, no hay una manera de resolver esto mediante la generación de funciones o polinomios de algún tipo?

(esta pregunta inspirado por: http://www.topcoder.com/stat?c=problem_statement&pm=42&rd=2001)

Answer 1

Creo que el problema se llama contando restringido particiones. (Advertencia: combinatorialists usar la palabra "partición" de dos maneras diferentes, y a veces no está completamente claro en el contexto que se supone. Uno debe distinguir entre las particiones de un número, que es el sentido que significa aquí, y las particiones de un conjunto.) Con la sustitución, la respuesta es que el número de $s_n$ de las maneras que tiene la generación de la función

$$\sum_n s_n x^n = (1 + x^a + x^{2a} + ...)(1 + x^b + x^{2b} + ...)(1 + x^c + x^{2c} + ...)...$$

o, equivalentemente,

$$\frac{1}{(1 - x^a)(1 - x^b)(1 - x^c)...}.$$

Esto es debido a que la elección de un término de cada factor corresponde a la elección de cómo muchas veces se utiliza cada número que usted puede utilizar. Por ejemplo, con las opciones de $\{ 1, 2, 5, 10, 25 \}$, este es el problema de contar el número de maneras posibles de hacer el cambio de una cierta cantidad de dinero.

La generación de la función se puede convertir en una fórmula explícita cuando el conjunto de posibilidades es finito, pero que es complicado en el caso general, y realmente no vale la pena cuidar. Esto conduce a una sencilla asintótica que me podría explicar si usted está interesado.

Answer 2

Si usted está, de hecho, buscando en primer particiones, esta es una muy complicado problema. La costumbre de contar la generación de series de aproximación por desgracia no ceder demasiado, sin más potente de las técnicas analíticas.

Aquí está el resumen de hormigón armado de Vaughn papel "En el número de particiones en números primos.":

Deje $p(n)$ denotar el número de maneras de escribir un entero positivo $n$ como una suma de números primos. Debido a la irregularidad en la distribución de los números primos, se ha creído por mucho tiempo que no es posible obtener una fórmula asintótica para $p(n)$. (Por supuesto, esto depende de qué se entiende por una fórmula asintótica.) En este trabajo, el autor obtiene una fórmula para $p(n)$ en forma $$ p(n)=M(n)(1+O(n^{-1/5})) \quad (n\to\infty), $$ donde $M(n)$ es una función suave cuya definición implica la generación de la función de $p(n)$. Por otra parte, utilizando el mismo método analítico, el autor obtiene el siguiente resultado notable: $$ p(n+1)-p(n)\sim\frac{\pi p(n)}{\sqrt{3n\log n}} $$

La lectura de este documento sin duda le dará algunas ideas. También, para ver la secuencia $p(n)$ usted puede visitar este OEIS página.

Espero que ayude,