The best $n$-digit password? I suddenly thought of a question today: What is the best $n$-digit password? It is not specific so I'll write it in a better way:

There is a password lock that has $n$ digits. There are $t$ choices for every digit. There is a thief that wants to  crack the password lock, so he blows some powder into the lock that  will show the fingerprints and will tell him the digits used (If there are repeated digit in the password, it only shows one fingerprint on the repeated digit). If the password consists of $m$ distinct digits, then find $m$ ($m\le n$) that makes the number of the combination of the possible password $P\left(m\right)$ the most.

Let me show a example:
For $n=4,t=4$, 
$P\left(1\right)=1,$
$P\left(2\right)=C^4_2+2C^4_1=14$
$P\left(3\right)=3\times2C^4_2=36$
$P\left(4\right)=4!=24$
$\therefore m=3$ is the answer for the case $n=4,t=4$.
However, when $n,t$ are bigger number, it will be hard to calculate. Hence, I want to ask you guys the general case or making a table. Thank you!
 A: Since the thief knows which numbers are used - not just how many - I think $P(1)=1, P(2)=14, P(3)=36, P(4)=24$, so $m=3$ is still safest.  
In general, you need the Inclusion-Exclusion Principle.  You are looking for passwords that use all $m$ different characters in $n$ digits.


*

*The total count of $n$-digit passwords using $m$ different characters is $m^n$.  

*Subtract the number that lack a '1', which is $(m-1)^n$.  Also subtract those that lack '2', '3' and do on.  In all, subtract $m(m-1)^n$.  

*Those that lack both '1' and '2' were subtracted twice, and need to be added back in once.  In all, add in ${m\choose2}(m-2)^n$  

*Subtract ${m\choose3}(m-3)^n$, add ${m\choose4}(m-4)^n$ and so on until ${m\choose m}(m-m)^n$
Sorry I don't have a feel for which is safest as a function of $n$.
A: The thief is able to determine the digits, but not their multiplicities.

Let $m$ be the number of distinct digits, with $m\le n\le t$.

Without loss of generality, we can assume the digits are $1,...,m$.

Let $P(m,n)$ be the number of $n$-tuples with each component in $\{1,...,m\}$  such that each of the values$\;1,...,m\;$occurs at least once.

For example, for $n=4$, we have
$$P(1,4)=1,\;\;\;\;P(2,4)=14,\;\;\;\;P(3,4)=36,\;\;\;\;P(4,4)=24$$
For each positive integer $n$, let $f(n)$ be the least positive integer $m\le n$ such that $P(m,n)$ is as large as possible.

For $1\le n \le 20$, here are the values of $f(n)$, computed via Maple . . .
$$
\begin{array}
{
|c
|c|c|c|c|c|c|c|c|c|c|
|c|c|c|c|c|c|c|c|c|c|
} 
\hline
n 
& 1 
& 2 
& 3
& 4 
& 5 
& 6 
& 7
& 8
& 9
& 10
& 11 
& 12 
& 13
& 14 
& 15 
& 16 
& 17
& 18
& 19
& 20
\\ 
\hline
f(n) 
&1
&2
&2
&3
&4
&5
&5
&6
&7
&8
&8
&9
&10
&10
&11
&12
&13
&13
&14
&15
\\
\hline
\end{array}
$$
For example, the result $f(20)=15$ means that for $n=20$, an optimal strategy is to choose $a_1,...,a_5$ independently and uniformly at random from $\{1,...,15\}$, and then let the combination be a random reordering of the $20$-tuple$\;(1,...,15,a_1,...,a_5)$.

From the data, it appears that 


*

*$f(n)$ is approximately ${\large{\frac{3}{4}}}n$.$\\[4pt]$

*If $n$ is a multiple of $4$, $f(n)$ is exactly ${\large{\frac{3}{4}}}n$.

