Cuántos números enteros entre 3,000 y 8,000] suma de dígitos de 20?

Question

Bueno, he estado casi perdiendo mi mente a través de este.

La pregunta es: ¿cuántos números enteros en el intervalo de $[3000, 8000]$ tienen una suma de dígitos de 20?

Bien, la primera cosa que hice fue separar a los grupos de acuerdo con el primer dígito. y luego:

3 - A+B+C=17

4 - A+B+C=16

5 - A+B+C=15

6 - A+B+C=14

7 - A+B+C=13

Ahora mi problema principal es: Desde a, B, y C son dígitos, lo que significa que están en el intervalo de $[0, 9]$. Cómo puedo hacer que la restricción en cuenta?

Answer 1

Método 1: Usando funciones de generación, desea que el coeficiente de $x^{20}$ $$(x^3+x^4+ \ldots +x^7)(1+x+ \ldots +x^9)^3=\frac{x^3(1-x^5)(1-x^{10})^3}{(1-x)^4}$$

Equivalentemente, podemos soltar el $x^3$ factor de y busque el coeficiente de $x^{17}$.

Tenemos $(1-x)^{-4}=\sum_{i=0}^{\infty}{\binom{i+3}{3}x^i}$. La expansión de $(1-x^5)(1-x^{10})^3$ e ignorando $x^n, n>17$ da $(1-x^5)(1-3x^{10})=1-x^5-3x^{10}+3x^{15}$.

Finalmente, el coeficiente de $x^{17}$ $$\binom{(17-0)+3}{3}-\binom{(17-5)+3}{3}-3\binom{(17-10)+3}{3}+3\binom{(17-15)+3}{3}$$

que fácilmente se evalúa para dar a $355$.

Método 2: Como usted puede no estar familiarizado con las funciones de generación, aquí es un más acercamiento elemental.

Procedemos exactamente como usted lo hizo. Si el 1er dígito es $i$, luego tenemos a $A+B+C=20-i$. Esto le da a $\binom{(20-i)+2}{2}$, pero también hemos contado aquellos donde$A, B, C$$\geq 10$. Para esos casos, exactamente 1 de los dígitos es $\geq 10$. Si es $A$,$A=k=10, 11, \ldots , 20-i$. A continuación,$B+C=20-i-k$, dando $21-i-k$ maneras. El número de maneras para $B, C$ son los mismos. Por lo tanto, debemos restar $3\sum\limits_{k=10}^{20-i}{(21-i-k)}=3\sum\limits_{j=1}^{11-i}{j}=3\frac{(11-i)(12-i)}{2}$.

Por lo tanto, el número total es de

$$\sum_{i=3}^{7}{\left(\binom{(20-i)+2}{2}-3\frac{(11-i)(12-i)}{2}\right)}=355$$