¿Cuántas maneras hay de formar un número de 16 dígitos en el que cada dígito aparezca al menos una vez?

Question

Necesito calcular de cuántas maneras podemos crear un número de 15 dígitos en el que cada dígito aparezca al menos una vez.
Mi primer pensamiento fue que esto era fácil -Primero, arreglamos los todos los dígitos en ${16 \choose 10}$ formas, y luego rellenar los huecos en $10^6$ formas y obtenemos la respuesta de ${16 \choose 10}10^6$ formas.
Sin embargo, ahora me he dado cuenta de que colocar un $0$ en la primera posición realmente estropea todo porque estamos recibiendo $15$ -números de dígitos en su lugar. Por lo tanto, la solución es conceptualmente sencilla: descartemos los arreglos que tengan un cero en la primera posición. - Es más fácil decirlo que hacerlo. No se puede saber si este cero procede o no de la posición inicial $10-$ configuración de dígitos. Es posible que se haya elegido en la segunda parte. Por lo tanto, me quedé atascado.

Cualquier sugerencia para resolver esto será muy apreciada.

Answer 1

Puede calcular $A_{k,n}$ -- el número de no-cero $k$ -números de dígitos en los que exactamente $n$ se han utilizado dígitos recursivamente. Comienza con $A_{1,1}=9$ ya que el cero no está permitido para el primer dígito. Después, cada $A_{k,n}$ contribuye a $A_{k+1,n}$ con un coeficiente de $n$ (hacer el número un dígito más largo eligiendo un dígito ya utilizado) y a $A_{k+1,n+1}$ con un coeficiente de $10-n$ (hacer el número un dígito más largo eligiendo un nuevo dígito). Es decir, $$A_{k,n}=n A_{k-1,n} + (11-n)A_{k-1,n-1}$$ para $k>1$ . La ejecución de esta recursión da como resultado $A_{16,10}=632788296940800$ .

Un enfoque alternativo es utilizar la inclusión-exclusión, como se sugiere en la otra respuesta. El número de $16$ -de dígitos utilizando todos los dígitos viene dado por el número total de $16$ -cadenas de dígitos ( $10^{16}$ ), menos el número que excluye un solo dígito ( $10\cdot 9^{16}$ ), más el número que excluye dos dígitos ( ${{10}\choose{2}}\cdot 8^{16}$ ), etc. Exactamente $9/10$ de estos comienzan con un dígito distinto de cero. Así que el resultado deseado es $$ \frac{9}{10}\sum_{i=0}^{10}(-1)^{i}{{10}\choose{i}}(10-i)^{16} = 632788296940800, $$ como antes.