How many ways are there to form a 16-digit number in which each digit appears at least once

Question

I need to calculate in how many ways we can create a 15 digit number in which every digit appears at least once.
My first thought was that this was easy -First, we arrange the all of the digits in ${16 \choose 10}$ ways, then fill in the gaps in $10^6$ ways and we get the answer of ${16 \choose 10}10^6$ ways.
However, now, I have realized that placing a $0$ in the first position really spoils everything because we are getting $15$-digit numbers instead. So, the fix is conceptually simple - let's rule out the arrangements featuring zero in the first position. - easier said than done. You cannot know whether or not this zero comes from the initial $10-$digit setup. It may well have been chosen in the second part. Therefore, I got stuck.

Any hints on solving this will be most appreciated!

Answer 1

You can calculate $A_{k,n}$ -- the number of nonzero $k$-digit numbers in which exactly $n$ digits have been used -- recursively. Start with $A_{1,1}=9$, since zero isn't allowed for the first digit. After that, each $A_{k,n}$ contributes to $A_{k+1,n}$ with a coefficient of $n$ (make the number one digit longer by choosing an already-used digit) and to $A_{k+1,n+1}$ with a coefficient of $10-n$ (make the number one digit longer by choosing a new digit). That is, $$A_{k,n}=n A_{k-1,n} + (11-n)A_{k-1,n-1}$$ for $k>1$. Running this recursion gives $A_{16,10}=632788296940800$.

An alternate approach is to use inclusion-exclusion, as suggested in the other answer. The number of $16$-digit strings using all digits is given by the total number of $16$-digit strings ($10^{16}$), minus the number that exclude a single digit ($10\cdot 9^{16}$), plus the number that exclude two digits (${{10}\choose{2}}\cdot 8^{16}$), etc. Exactly $9/10$ of these start with a nonzero digit. So the desired result is $$ \frac{9}{10}\sum_{i=0}^{10}(-1)^{i}{{10}\choose{i}}(10-i)^{16} = 632788296940800, $$ as before.