The best $n$-digit password?

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$.

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.

1. The total count of $n$-digit passwords using $m$ different characters is $m^n$.
2. 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$.
3. 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$
4. 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$.