La pregunta :
En cuántos números diferentes entre $1$ $100000000$ tiene la suma de sus dígitos igual a $45$?
Estoy pensando en usar las estrellas y las barras de la fórmula, pero no estoy seguro de si es posible y cómo.
Gracias de antemano !
Respuestas
¿Demasiados anuncios?
Usted puede usar la inclusión de exclusión para obtener la respuesta 2706880. Primero vamos a reformular el problema. Tenemos que encontrar el número de entero no negativo soluciones a
$$ x_1 \, + \, x_2 \, + \; ... \; + \, x_k = n \;\;\;\;\;\;\;\;\;\; (*)$$
donde $x_i < \mu$. Si podemos resolver esto, entonces podemos simplemente enchufe en $n=45, k=8$ $\mu=10$ a resolver su problema. Cada una de las $x_i$ representa el $i$'th dígito de un número dado entre el$0$$10^k$. Ahora, si no tenemos la restricción de que el $x_i<\mu$, entonces las soluciones son conocidas como la debilidad de las composiciones, y el número de la debilidad de las composiciones se ve fácilmente ser ${ n+k-1 \choose k-1}$ el uso de estrellas y barras 
Para manejar la restricción $x_i < \mu$, se puede utilizar el principio de inclusión-exclusión que va de la siguiente manera: Vamos a $S$ ser un conjunto de objetos, vamos a $A,B,C$ ser subconjuntos de a $S$ que satisfacen las propiedades de $a,b,c$, respectivamente. Supongamos que queremos saber el número de elementos que no cumplen alguna de las propiedades de $a,b$ o $c$. Es decir, queremos recuento $|S - (A \cup B \cup C)|$ o de la parte sombreada en el diagrama siguiente.
$\qquad \qquad \qquad \qquad \qquad \qquad \qquad$ 
Podemos contar esto por tamizado
$$|S| \; - \; (|A|+|B|+|C|) \; + \; \left( |A \cap B|+|A \cap C|+|B \cap C| \right) \; - \;|A \cap B \cap C| $$
$ \qquad \qquad \qquad \quad $ 
Esto es fácilmente generalizado para $k$ propiedades diferentes. Volviendo a tu problema, dejamos $S$ ser el conjunto de todas las soluciones de (*) y deje $P_i$ ser el subconjunto donde $x_i \geq \mu$. A continuación, queremos contar
$$\left|S - (P_1 \cup P_2 \, \cup \; ... \; \cup \, P_k \right)| = \left| \, S \, \right| - \sum_i\, \left|P_i\right| \; + \; \sum_{i,j} \left |P_i \cap P_j \right| \; - \;\; ...$$
Pero ¿cuáles son los sumandos? O, más específicamente, ¿qué es $|P_i|$? Soluciones en $P_i$ son soluciones el problema
$$ \begin{array} (x_1 \, + \, x_2 \, + \; ... \; +&(x_i)_{\geq\mu} &+ \; ... \; + \, x_k &= n \\ x_1 \, + \, x_2 \, + \; ... \; + &(\mu+x_i') &+ \; ... \; + \, x_k &= n \\ x_1 \, + \, x_2 \, + \; ... \; + &(x_i')_{\geq 0} &+ \; ... \; + \, x_k &= n-\mu \end{array}$$
Pero ya sabemos que este ser ${n-\mu+k-1 \choose k-1}$. Siguiendo un patrón similar, nos damos cuenta de
$$ \begin{array} ( \left| S \right| &= {n+k-1 \choose k-1} \\ \left| P_i \right| &= {n+k-1-\mu \choose k-1} & \small{\;\;\;\;\; \forall \, i}\\ \left| P_i \cap P_j \right| &= {n+k-1-2\mu \choose k-1} & \small{\;\;\;\;\; \forall i,j}\\ \left| P_i \cap P_j \cap P_\ell \right| &= {n+k-1-3\mu \choose k-1} &\small{\;\;\;\;\; \forall \, i,j,k}\\ &... \end{array} $$
Así que nuestra suma deseada se convierte en
$$\begin{array} (\displaystyle \left|S - (P_1 \cup P_2 \, \cup \; ... \; \cup \, P_k) \right| & = \left| \, S \, \right| - {k \choose 1} \left|P_i\right| \; + \; {k \choose 2} \left |P_i \cap P_j \right| \; - \;\; ... \\ \\ & = \displaystyle \sum_{i=0}^{\min \{k, \lfloor n/\mu \rfloor \}} (-1)^i {k \choose i} {n+k-1-i\mu \choose k-1} \\ \end{array} $$
Nos truncar la suma de $min \{k, \lfloor n/\mu \rfloor \} $ debido a que los sumandos son iguales a cero, a partir de entonces en adelante (por definición). Para contar el número de números enteros de menos de $10^8$ con la suma de dígitos $45$, enchufamos $n=45, k=8$, e $\mu=10$ y obtener
$$\sum_{i=0}^4 (-1)^i {8 \choose i} {52-10i \choose 7} = 2706880$$
Rus May
Puntos
885
Sí, esto es similar a una de las estrellas-y-bares problema. Sin embargo, existe la restricción adicional de que cada dígito ser en la mayoría de los nueve. Por lo tanto, su problema es equivalente a este (con $k=45$, $n=8$ y $c=9$). Para la respuesta en la pregunta dado como una suma de $n=8$ términos, Arce da 2,706,880 números entre 1 y 100.000.000 de cuyos dígitos tienen una suma de 45.
Como alternativa se indicó en los comentarios, puedes aproximar este resultado con el teorema del límite central. Usted puede pensar de cada uno de los dígitos como una variable aleatoria uniformemente distribuida entre 0 y 9 (con una media de $\frac92$ y la desviación estándar $\frac{\sqrt{33}}2$). Entonces, por el teorema central del límite, la suma de $S$ de los dígitos en un niño de ocho dígitos número tendría una distribución aproximadamente normal (con una media de $8\cdot\frac92$ y la desviación estándar $\frac{\sqrt{8\cdot33}}2$). El uso de esta distribución normal, $\text{prob}(44.5<S<45.5)\approx 0.0266$, con lo que obtenemos una aproximación de $100,000,000\cdot0.0266=2,660,000$ números de la satisfacción de su condición.
