Cuántas $10$ número de dígitos que existe de que la suma de sus dígitos es igual a $15$?
Información adicional: el Primer dígito de la izquierda no es $0$.podríamos usar cualquier dígitos de $0$$9$.
He visto en algunas preguntas relacionadas con la que utiliza Inclusión-exclusión .Aún tengo que estudiar así que me gustaría que alguien continúe uno de los enfoques de una manera que no necesita de Inclusión-exclusión.Sin embargo,si no es posible sin la Inclusión-exclusión,escriba sus respuestas de todos modos.
Lo que he hecho hasta ahora:El desafío principal de este problema es contar las malas situaciones. Porque sabemos que el número de maneras en que la suma de $10$ número es igual a $15$.
Tengo dos approachs:
Enfoque #1:$$x_1+x_2+\cdots+x_{10}=15\space, \space x_1\geq 1\space ,\space 0\leq x_i\leq9$$
Using stars and bars number of answers of this equation:$$x_1+x_2+\cdots+x_{10}=15\space, \space 0\leq x_i\leq15$$
Is equal to :$${15+10-1 \choose 10-1}={24 \choose 9}$$
Now counting situations that one of $x_i$ is bigger than $10$:$$x'_1=x_1-10 \space, \space x'_2=x_2\space,\cdots,x'_{10}=x_{10}\space, \space x'_{1}+\cdots+x'_{10}=5\space,\space0\leq x'_i\leq5$$
I assume here that $x_1$ is bigger than $10$ but any of $x_i$ could be.So number of situations that one of them is bigger than $10$ is : ${5+10-1 \elegir 10-1}\times10={14 \elegir 9}\times 10$
Now I don't now what about situations where $x_1= 0$
Approach #2(I like this more):
I was thinking that getting rid of those situations that $x_1 = 0\espacio$ is much easier.So $$x_1+x_2+\cdots+x_{10}=15\space, \space x_1\geq 1\space ,\space x_2,x_3,\cdots,x_{10}\geq 0$$ Por lo que el número de respuestas de esta ecuación es ${15+10-1-1 \choose 10-1}={23 \choose 9}$
Ahora debo contar el número de maneras en que uno de los dígitos es mayor de 10.No sé qué hacer aquí.
Algunas actualizaciones en el enfoque #2:
si mayor $x_i$$15$, entonces no es $1$ situación posible con $x_1 \geq 1$.
si mayor $x_i$$14$, entonces no es $9+9=18$ situación posible con $x_1 \geq 1$.
Así que mi pregunta ahora es algo como esto:
una forma inteligente de situaciones de conteo donde $x_1\geq 1$ más grande y $x_i$ es igual a $10$.
Aquí es un código c++ que cuenta con todos estos números.
#include <iostream> using namespace std; bool a(int n) { int i; int sum=0; while(n != 0) { i= n % 10; sum= sum + i; n= n /10; } if (sum == 15) return true; return false; } int main() { int k=0; for(int j=1000000000;j<9600000000;j++) { if(a(j)) { k++; } } cout<<k+1<<endl; }Que imprime $808753$.
Y ${23 \choose 9}-(18+1)=817171$.
Por lo $817171 -808753 = 8418$
si mayor $x_i$$13$, entonces no es $18+{9 \choose 2}\times 3=126$ situación posible con $x_1 \geq 1$.
Por lo $8418 -126 =8292$.
si mayor $x_i$$12$, entonces no es $18+6{9 \choose 2}+4{9 \choose 3}=570$ situación posible con $x_1 \geq 1$.
Por lo $8292 - 570=7722$
Respuestas
¿Demasiados anuncios?
Suponga que usted puede tener "dígitos" de cualquier tamaño. Si usted imgagine llenando los dígitos mediante la adición de 1 para cada uno de ellos uno a la vez, usted tiene que poner un 1 en la primera, para empezar. Después de eso, usted tiene 14 1 lugar en los 10 dígitos. Ahora usted puede imaginar la organización de 14 1 y 9 + signos para lograr el mismo efecto. Es decir, tenemos 23 símbolos y tenemos que elegir 9 de ellos a ser + signos. Por lo que el número de maneras de hacer esto es: $$ \begin{align} &\text{Ways to choose digits adding to 15}\\ &\text{ with more than 9 allowed in some digits} ={{23}\choose{9}} \end{align} $$
Sin embargo, hemos incluido algunas opciones donde hay más de nueve en una posición. Si hay 10 puntos en cualquier lugar, entonces no puede haber otro con 10 porque no agregar a 15. Por lo que podemos contar las maneras para el resto de añadir a 5. Tenga en cuenta que si uno de ellos tiene 10 1 para empezar y luego añadir 1 esto cubrirá formas cuando no se les permite ser más de 10 en ese lugar.
Si el primer "digit" es 10 o más, ponemos 10 1 en esa posición, y luego tenemos 5 1 izquierda a cabo entre el 9 + signos. Así que el 14 de símbolos donde tenemos que elegir 9 + signos. Así que tenemos esta muchas maneras con 10 o más en el primer dígito: $$ \begin{align} &\text{Ways to fill digits adding to 15}\\ &\text{ with 10 or more in only the first digit} ={{14}\choose{9}} \end{align} $$
Si algunos de los otros dígitos es 10 o más, entonces vamos a poner 10 1 en esa posición. Tenemos que poner un 1 en la primera posición. Así que ahora hay 4 1 izquierda a cabo entre el 9 + signos. Este es el 13 de símbolos, 9 de los cuales debe ser + signos. Así que para cada uno de los otros dígitos de la posición, se obtiene: $$ \begin{align} &\text{Ways to fill digits adding to 15}\\ &\text{with 10 or more in a particular digit other than first} = {{13}\choose{9}} \end{align} $$
Hay 9 dígitos para elegir, por lo tanto tenemos: $$ \begin{align} &\text{Ways to fill digits adding to 15}\\ &\text{with 10 or more in any one digit} = {{14}\choose{9}} + 9{{13}\choose{9}} \end{align} $$
Por lo tanto, esto restando del total de maneras para llenar dígitos podemos obtener la respuesta final: $$ \begin{align} &\text{Ways to fill digits adding to 15} \\ &\text{so there are no more than 9 in any digit} = {{23}\choose{9}} - {{14}\choose{9}} - 9{{13}\choose{9}} \end{align} $$
También puede utilizar funciones de generación:
1er dígito podría ser del 1 al 9, de modo que corresponde a $(x+\dots+x^9)$. Los otros dígitos puede ser de 0 a 9 que corresponde a $(1+x+\dots+x^9)$. Por lo que el número de maneras de hacerlo es el coeficiente de $x^{15}$ en esta expresión: $$ \begin{align} (x+\dots+x^9)(1+x+\dots+x^9)^9 &= x(1+\dots+x^8)\left( \frac{1-x^{10}}{1-x} \right)^9\\ &= x\frac{1-x^9}{1-x}\frac{(1-x^{10})^9}{(1-x)^9}\\ &= x \frac{(1-x^9)(1-x^{10})^9 }{(1-x)^{10}}\\ &= x (1-x^9)(1-x^{10})^9(1-x)^{-10}\\ &= x(1-x^9)\left(1-{9\choose1}x^{10}+{9\choose2}x^{20} - \dots\right)\\ &\quad \times \left(1 -{{-10}\choose{1}}x + {{-10}\choose2}x^{2} - {{-10}\choose3}x^{3} + \dots \right) \end{align} $$ Con el fin de producir un $x^{15}$, podemos elegir los términos de los cuatro multiplicands. Tenemos estas opciones:
- $x \times 1 \times 1 \times {{-10}\choose{14}}x^{14}$
- $x \times 1 \times -{9\choose 1}x^{10} \times {{-10}\choose{4}}x^4$
- $x \times - x^9 \times 1 \times - {{-10}\choose{5}}x^5$
Por lo que el número total de opciones es: $$ \begin{align} {{-10}\choose{14}} - {9 \choose 1}{{-10}\choose{4}} + {{-10}\choose{5}} &={{23}\choose{14}} - {9\choose 1}{{13}\choose{4}} - {{14}\choose{5}}\\ &={{23}\choose{9}} - 9{{13}\choose{9}} - {{14}\choose{9}} \end{align} $$
Contar las formas en las que un 'dígito' es mayor que 9 (tenga en cuenta que el problema en la mayoría de uno "dígito" puede ser mayor que 9) asciende a contar el número de maneras en que el mayor "dígito" es 10, 11, 12, 13, 14, o 15. He aquí cómo se podría calcular el número de maneras en que el mayor "dígito" es de 10.
Primer lugar, calcular el número de maneras en que el primer dígito es de 10 $$\binom{13}{8}.$$ Aquí tenemos un 9 dígitos (sin restricción de que el primer dígito distinto de cero), cuyos dígitos agregar a 5. A continuación, calcular el número de maneras en que el más grande de los dígitos es 10 y el primer dígito no es 10 $$\binom{12}{8}\cdot9.$$ Este es el número de 9 dígitos de números cuya suma de los dígitos a 5 con un primer dígito distinto de cero y un '10' dígitos colocados después de cualquiera de los dígitos. El número de maneras en que el mayor dígito es el '10' es la suma de estos dos casos. Repitiendo este proceso para 11, 12, 13, 14, y 15 debe dar a todos los de la 'mala' de los casos.
Alternativamente, si dejamos caer el requisito de que el primer dígito distinto de cero en los cálculos se vuelven un poco más fácil, ya que entonces el número de maneras en que el más grande de los dígitos es 10 se convierte en $$\binom{13}{8}\cdot 10.$$ Si desea contar cuántos números tiene una suma de dígitos de 15 años con un primer dígito distinto de cero, se puede hacer el problema de los 9 números de dos dígitos (sin restricción en el primer dígito) y restar el resultado. Ambos enfoques parecen requieren aproximadamente la misma cantidad de cálculo.
Coeffecient de x^15 en la expansión de $$(x+x^2+...+x^9)(1+x+x^2+...+x^9)^9$$ debe hacerlo. El primer término es para el dígito de más a la izquierda y el segundo término para los restantes 9.
Se simplifica a $$ x\frac{1-x^9}{1-x} \frac{1-x^{10}}{1-x} = x\frac{1-x^9-x^{10}+x^{19}}{(1-x)^2} $$ Cual es el coeficiente de $x^{14}$ $ \frac{1-x^9-x^{10}}{(1-x)^2}$
Intente esto: Usted tiene 15 1s separados por 9 bares: $$11|1|111|...|1$$ El número de 1s en el n-ésimo bloque representa el n-ésimo dígito. entonces usted tiene que distribuir $9$ $|$ en $9+15=24$ posiciones. Que es $ 24 \choose 9$ maneras. Ahora overcounted, ya que no quiero un $0$ en el primer lugar (algo parecido a $|11|...|1$). Ahora el recuento de los: Igualmente esta $23\choose 8$. Así que no debería ser $24 \choose 9$ - $23 \choose 8$ formas de hacerlo.
Edit: también es necesario excluir los casos en que $10, \ldots, 15$ 1s están en el mismo cuadro. Que no debería ser demasiado difícil. Usted puede poner $10$ $1$s en cualquier bloque en el inicio y, a continuación, para el mismo truco (Cuidado: Si usted lo pone en el primer bloque no es necesario excluir a cualquiera de las soluciones).
Como ya se ha dicho el número que estamos buscando es el coeficiente de $x^{15}$ $(\sum_{i=1}^9 x^i)(\sum_{i=0}^9 x^i)^{9}$ Una manera de calcular este número:
$$ \begin{eqnarray} \left(\sum_{i=1}^9 x^i\right)\left(\sum_{i=0}^9 x^i\right)^{9} = \\ x\left(\frac{1-x^{9}}{1-x}\right)\left(\frac{1-x^{10}}{1-x}\right)^{9}= \\ x(1-x^{9})(1-x^{10})^{9} \frac{1}{(1-x)^{10}}= \\ x(1-x^{9})(1-x^{10})^{9} \frac{1}{9!}\frac{d^9 }{dx^9}\frac{1}{(1-x)^{10}}= \\ x(1-x^{9})(1-x^{10})^{9} \frac{1}{9!} \frac{d^9 }{dx^9}\sum_{i=0}^{\infty}x^i = \\ x(1-x^{9})(1-x^{10})^{9} \frac{1}{9!} \sum_{i=0}^{\infty}\frac{(9+i)!}{i!}x^i = \\ x(1-x^{9})(1-x^{10})^{9} \sum_{i=0}^{\infty}\binom{9+i}{9}x^i = \\ x(1-x^{9})(1-9x^{10}+x^{20}p_1(x)) \sum_{i=0}^{\infty}\binom{9+i}{9}x^i = \\ (x-x^{10}-9x^{11}+x^{20}p_2(x)) \sum_{i=0}^{\infty}\binom{9+i}{9}x^i \\ \end{eqnarray}$$
El coeficiente de $x^{15}$ es $$\binom{9+14}{9}-\binom{9+5}{9}-9\binom{9+4}{9}=808753\\ $$
