[alfil]

Buenos días a todos.
En un libro de combinatoria leí el siguiente problema: "¿cuántos números de entre el 1 y el 100000 suman 20?" (se entiende que suman sus dígitos, por ejemplo 11928 suma 21). Yo había hecho hace poco el caso de cuántos números suman 18 entre el 1 y el 10000, pero en este caso lo hice considerando las distintas clases de números (es decir iguales salvo permutaciones) y considerando la combinatoria de cada uno. Ya con 10000 era pesado porque resultaban 43 clases, así que no me quiero imaginar las clases que habrá entre 1 y 100000 ... ¿Hay algún método más sencillo de enfocar el problema?

Gracias por adelantado

[Luis Fuentes]

Hola

 Tu problema puede reformularse así. Se trata de contar cuantas soluciones enteras tiene la siguiente ecuación:

 \( c_1+c_2+c_3+c_4+c_5=20 \)

 con

 \( 0\leq c_i\leq 9 \)

 Hay unas técnicas para resolver este tipo de problemas basadas en funciones generatrices.

 La idea en este caso es la siguiente. Consideramos el polinomio:

\(  p(x)=(1+x+\ldots+x^9)(1+x+\ldots+x^9)(1+x+\ldots+x^9)(1+x+\ldots+x^9)(1+x+\ldots+x^9) \)

 Ahora fíjate que si hacemos ese producto, para obtener un término de la forma \( x^{20} \) hemos de escoger un \( x^{c_1}  \) con \( 0\leq c_1\leq 9 \) del primer término; un \( x^{c_2}  \) con \( 0\leq c_2\leq 9 \) del segundo; etcétera, de manera que \( c_1+\ldots+c_5=20 \).

 Por tanto el número de soluciones buscado corresponde con el coeficiente del monomio \( a_{20}x^{20} \) del polinomio \( p(x) \).

 Este coeficiente (piensa en las series de Taylor) se obtiene como:

 \( a_{20}=\dfrac{p^{20)}(0)}{20!} \)

 Por último el polinomio \( p(x) \) puede reescribirse de manera cómoda como:

 \( p(x)=\dfrac{(x^{10}-1)^5}{(x-1)^5} \)

Saludos.

[alfil]

Increible ... Agradecido de verás, me gustaría en cualquier caso dejarte un par de asuntos:
i) ¿Cómo sabes que el polinomio admite una expresión tan sencilla?
ii) A pesar de que el problema está resuleto, hallar el coeficiente de orden 20 de ese polinomio -sin emplear ordenador, claro- parece tirando a pesado ... ¿me equivoco?

Gracias

[Luis Fuentes]

Hola

 i) Simplemente uso la identidad conocida:

\(  (1+x+x^2+x^3+\ldots+x^{n-1})(x-1)=(x^n-1) \)

 ii) Si. El cálculo del coeficiente puede ser latoso. Intenta obtener una expresión moderadamente manejable para la derivada n-sima de una función de éste tipo \( f(x)=g(x)^5 \).

 En el peor de los casos suelen obtenerse soluciones recursivas.

Saludos.

[Fernando Revilla]

La fórmula de Newton -Leibnitz para la derivada enésima del producto de un número finito de funciones, está relacionada con este problema.

Para \( g(x)=\displaystyle\sum_{i=0}^{9}x^i \) tenemos \( g^{(\alpha_i)}(0)=\alpha_i !\;(0 \leq \alpha_i\leq{9}) \) y \( g^{(\alpha_i)}(0)=0\;(\alpha_i >{9}) \). Por otra parte, si \( f(x)=g(x)^5 \), tenemos:

\( \displaystyle\frac{f^{(20)}(0)}{20!}=\displaystyle\frac{1}{20!}\displaystyle\sum_{\alpha_1 +\ldots+\alpha_5=20}{\displaystyle\frac{20!}{{\alpha_1 !\ldots \alpha_5 !}}}\; g^{(\alpha_1)}(0)\ldots g^{(\alpha_5)}(0)}}}=\displaystyle\sum_{\alpha_1 +\ldots+\alpha_5=20\;(0\leq{\alpha_i}\leq{9})}1 \)

Saludos.

[Luis Fuentes]

Hola

 Veamos una forma para obtener una expresión de la solución de tu problema.

 Si es fácil de calcular el número de soluciones enteras de una ecuación de este tipo:

 \( c_1+\ldots+c_n=M \)

 con \( c_i\geq 0 \).

 Razonando como antes podemos ver que es el coeficiente de grado \( M \) del polinomio:

 \( p(x)=\dfrac{1}{(1-x)^n} \)

 Es decir:

 \( a_M=\dfrac{p^{M)}(0)}{M!}=\dfrac{(M+n-1)!}{M!(n-1)!}=\displaystyle\binom{M+n-1}{n-1} \)

 Entonces para nuestro problema primero contamos cuantas soluciones tenemos:

 \( c_1+\ldots+c_5=20 \)

 \( c_i\geq 0 \)

 Son \( \displaystyle\binom{24}{4} \).

 Vamos a descontarle aquellas que cumplen:

  \( c_1+\ldots+c_5=20 \)

 \( c_i\geq 0,\qquad c_1\geq 10 \)

 El truco es llamar \( a_1=c_1-10 \) y entonces eso equivale a contar el número de soluciones enteras de:

 \( a_1+c_2+\ldots+c_5=10 \)

 \( c_i\geq 0,\qquad a_1\geq 0 \)

 Esto lo sabemos contar: \( \displaystyle\binom{14}{4} \).

 Análogamente descontamos aquella en que \( c_2 \) pasa de 9 ó \( c_3 \) ó \( c_4 \) ...

 Obtenemos:

 \( \displaystyle\binom{24}{4}-5\displaystyle\binom{14}{4} \).

 Pero hay que tener en cuenta que hemos descontados dos veces aquellas en que \( c_i\geq 10,c_j\geq 10 \) al mismo tiempo para cada par \( \{i,j\}\subset \{1,2,3,4,5\} \) (técnicamente aplicamos el principio de inclusión-exclusión). Pero como la suma es \( 20 \) por cada par \( i,j \) hay sólo una posibilidad para que dos coeficientes superen el \( 9 \) al mismo tiempo.

 Por tanto el número de combinaciones buscado es:

 \( \displaystyle\binom{24}{4}-5\displaystyle\binom{14}{4}+\displaystyle\binom{5}{2}=5631 \).

Saludos.

[alfil]

Eso era lo exactamente lo que buscaba. Gracias por la ayuda prestada y un saludo.