How many possible lock combinations if digits known? I have a keypad lock with digits 0-9. It takes an $n$ digit keycode to successfully open, with repetitions allowed. Magically, let's say I know every distinct digit that goes into the correct keycode. There are $m$ such digits. How many possible combinations are there with those digits?
Here's what I have so far. Let's say there are n distinct digits in the keycode (i.e., $m$ = $n$). The answer then is, trivially, $n!$.
If $m = n-1$, we know that one of the digits appears twice. So, we have the number of combinations as, $\frac{m \cdot n!}{2!}$.
Is there a general formula for $(m,n)$?
 A: There are $n$ empty positions in which we can put our available digits
$$\underbrace{\text{_ _ _ _ ... _ _}}_{n\text{ positions}}$$
each successive position may take on any of the $m$ possible digits hence there are
$$\text{possible key codes}=m^n\qquad\blacksquare$$
However, this counts keycodes length $n$ that use at most $m$ digits.
In order to count those keycodes that use at least one of each digit form sets $A_k$ of keycodes that use only the $m$ known digits but don't use the digit $k$ (which is amongst those $m$ digits). Then there are $\binom{m}{1}$ sets $A_k$ with cardinality:
$$|A_k|=(m-1)^n$$
because there are $(m-1)^n$ keycodes using the remaining $m-1$ digits. 
Similarly there are $\binom{m}{2}$ set intersections (keycodes that don't use digits $k$ and $l$) which have cardinality:
$$|A_k\cap A_l|= (m-2)^n$$
this time there are $m-2$ digits for each position of the the keycode. higher order intersections look similar, for the $\binom{m}{3}$ 3-intersections we have:
$$|A_k\cap A_l\cap A_p|=(m-3)^n\\\vdots$$
Using the principle of inclusion-exclusion the number of valid keycodes that belong to none of the $A_k$ is given by:
$$\boxed{\text{valid keycodes}=m^n-\binom{m}{1}(m-1)^n+\binom{m}{2}(m-2)^n-\binom{m}{3}(m-3)^n+\ldots +(-1)^{m-1}\binom{m}{m-1}1^n\qquad\blacksquare}$$
This is related to the Stirling Numbers of the second kind $S(n,m)$ via
$$\text{valid keycodes}=m!S(n,m)$$
