Another approach is to code a recursion in two variables. If we have n places and r digits, and each has to be used at least once, then call the number of possibilities f(n,r). The rules are as follows.
If there is but one digit, we only have one possibile value for a given n (every digit is the one that's allowable).
If we have fewer places than digits there are no possibilities that fulfill the requirements.
If number digits = number of places, call it r, then there are r! possibilities; each is a permutation of the available digits. (I didn't check whether this rule is really needed; maybe not.)
for other n, r the recurrence is that we have f(n,r-1) ways to fill out the first n-1 positions using all r digits, times r possibilities for the last, PLUS we have f(n-1,r-1) ways of filling out the first n-1 places using only r-1 digits, and the last pace is then forced on us, but multiply by the r choices for which digit gets omitted until the end.
In code this is as follows.
f[n_,1] = 1
f[n_,r_] /; n<r := 0
f[r_,r_] := r!
f[n_, r_] := f[n,r] = r*f[n-1,r] + r*f[n-1,r-1]
This gives:
f[64,21]
(* Out[16]= 1510109515792918244116781339315785081841294607960614956302330123544242628820336640000 *)
I was not able to convince RSolve or RecurrenceTable to do this but perhaps those might be used in a similar manner.