Should I have a repeated digit in a $4$-digit pin code?

Question

A small argument my colleague and I were having...

Say I've got a $4$-digit security code on my burglar alarm, and I'm too lazy to ever change it. Over time, the digits involved will become worn.

If I've used $4$ different digits (as is common, eg $1357$), then an attacker, knowing those are the digits in the code, needs (if I'm right!) $24$ goes to try all combinations.

If I've repeated a digit (eg, $1317$), the attacker just knows $1$, $3$ and $7$ are used (assume that all wearing is indistinguishable). How many different possible $4$-digit codes are possible, using each digit at least once? I say it's more than $24$, my colleague is convinced otherwise.

Bonus kudos for generalizing the problem to knowing $k$ digits in an $n$-digit pin. ;)

Answer 1

If the burglar knows which digit is repeated, (s)he has \begin{equation*} \dfrac{4!}{2!} = 12 \end{equation*} codes to try. Since (s)he doesn't know which digit is repeated, (s)he will have to try $3 \cdot 12=36$ different codes.

Answer 2

I really like that problem, it is very visual and easy to understand. I'll show the case of a code lenght of $n$ where $l<n$ digits are repeated exactly twice. That makes for a total of $k = n-l$ different digits. (i.e. for your particular question please set $n=4$, $l=1$.)

Given $n$ different digits without repetition, you got $n!$ ways to order them. That is a fairly basic problem.

Now assume you still have $n$ digits, but $l$ „marked“ ones are repeated twice. (i.e. the attacker knows which digit you double) This will reduce your possibilities by a factor of $2^k$.

Why? Your set of numbers looks like $\{1_1,1_2,2_1,2_2,...,l_1,l_2,l+1,l+2,...,n-l=k\}$. That is still $n$ elements, because the first $l$ are doubled. When ordering those we have $n!$ choices, because we can see those little indices. But you burglar alarm can't, we are counting to many possibilities! We need to figure out how often each possibility was counted and adjust for this. Each pair of doubled numbers $j_1, j_2$ (here $j\leq l$) could be placed as $..,j_1,..,j_2,..$ or the other way round as $..,j_2,..j_1,..$ giving you two possibilities in total. As changing that around is independent we need to multiply all those twos together.

The final step now considers the burglar, who doesn't know which digits are doubled. He will have to try each possible subset with $l$ elements. This is known as the binomial coefficient $n\choose l$. In total this gives us:

$${n \choose l} \cdot \frac{n!}{2^l}$$

Note that $2^l$ grows faster than $n \choose l$, but the later start with a higher initial amount. In conclusion: A small number of doubled keys is sensible, depending on your $n$. But make sure you don't double to many!

Answer 3

Your question of "using each digit at least once" is kind of confusing, because you should emphasize that there are nonetheless $3$ different digits involved, all of which are known to the attacker.

Having emphasized this, the attacker has a total of $36$ possible combinations:

 Digit #1 occurs | Digit #2 occurs | Digit #3 occurs | Combinations
-----------------|-----------------|-----------------|--------------
 1 time          | 1 time          | 2 times         | 12
-----------------|-----------------|-----------------|--------------
 1 time          | 2 times         | 1 time          | 12
-----------------|-----------------|-----------------|--------------
 2 times         | 1 time          | 1 time          | 12

---

Each case can be calculated in any of the following ways:

• $\binom41\cdot\binom31\cdot\binom22=12$
• $\binom41\cdot\binom32\cdot\binom11=12$
• $\binom42\cdot\binom21\cdot\binom11=12$

Answer 4

Here is my answer for a code of length $n$ using $k$ different digits which may be repeated arbitrarily often. Each digits must appear at least once. (otherwise it won't be worn out.)

This uses the corresponding sequence “A019538” which Barry Cipra mentioned.

Now, referencing OEIS is all nice and all, but if you aren't a mathematician chances are that page is quite confusing. It has a bunch of comments all seemingly pointing at a different meaning. None of those meanings in the one we actually have. (The “Number of $k$ dimensional 'faces' of the $n$ dimensional permutohedron” doesn't look like like numbers on a keypad to me at all... And WTF even is a permutohedron?)

Here is a formulation we can turn into a keypad: “Number of surjections (onto functions) from an $n$-element set to a $k$-element set.”

What is a “surjection from an $n$-element set to a $k$-element set”? It's an assignment which assigns one out of $k$ numbers each of $n$ places. Numbers can occur arbitrarily often and the “surjection” tells us each of the $k$ elements must be picked at least once. Great! That is exactly what we are looking for. Each position $n$ positions of the code is assigned one out of $k$ worn out keys and each key is picked at least once.

We are on the right OEIS page, let's get a formula. (There are many) $$T(n, k) = k*\left(T(n-1, k-1)+T(n-1, k)\right) \text{ with } T(0, 0) = 1$$ That is not exactly a “plug in your numbers and get a result” formula – but with a small table getting a value is easy enough. And this formula happens to be easy to explain.

First of, why is $T(0,0) = 1$? This counts the ways you can enter a code of length $0$ using no digits. It sounds slightly insane if you see this the first time, but there is exactly one way to do that: Stand there and don't do anything.

Now where does $T(n, k) = k*\left(T(n-1, k-1)+T(n-1, k)\right)$ come from? For the first place, we have $k$ different possibilities. What about the other $n-1$ places which follow? We split this into two cases:

• The first digit is never used again. Then there are $T(n-1, k-1)$ ways to fill out the last $n-1$ digits with $k-1$ numbers.
• The first digit is used again. There there are $T(n-1, k)$ ways to fill out the last $n-1$ digits with $k$ numbers.

In sum, that gives us $T(n-1, k-1)+T(n-1, k)$ ways to fill out the last $n-1$ places times $k$ ways to fill out the first digit.

Here are some values which were also kindly supplied by OEIS:

n\k 1    2     3      4       5        6        7        8        9
1:  1
2:  1    2
3:  1    6     6
4:  1   14    36     24
5:  1   30   150    240     120
6:  1   62   540   1560    1800      720
7:  1  126  1806   8400   16800    15120     5040
8:  1  254  5796  40824  126000   191520   141120    40320
9:  1  510 18150 186480  834120  1905120  2328480  1451520   362880

In conclusion, if you use a lenght from three to six, double a single digit. For seven, eight and nine you should use two less and if you are using even longer codes, ask on stackoverflow for coding help.

I hope that helps.

Answer 5

If
$n$...the total number of digits,
$k$...the number of the same digits.
then the number of different options (and numbers) $c$ equals to:
$$c=\binom{n}{k}\cdot (n-k)!$$ and because of the $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ the $c$ can be simplified:
$$c=\frac{n!}{k!}$$ For $n=4$[digits], and $k=1$(all numbers are different): $c=\frac{4!}{1!}=24$,
for $n=4$[digits], and $k=2$[the same numbers]: $c=\frac{4!}{2!}=12$,
for $n=4$[digits], and $k=3$[the same numbers]: $c=\frac{4!}{3!}=4$,
and for $n=4$[digits], and $k=4$(4 the same numbers): $c=\frac{4!}{4!}=1$.
If you have $n$ digits containing $k$ the same numbers, then you can create $\binom{n}{k}$ combinations representing different number patters(where each contains (n-k) empty positions). The (n-k) remaining positions can contain any permutation remaining numbers. For example, for numbers $1,1,3,4$, this means $n=4$ and $k=2$ you can create $\binom{4}{2}=6$ these diffrerent patterns:
1)$1,1,-,-$;
2)$1,-,1,-$;
3)$1,-,-,1$;
4)$-,1,1,-$;
5)$-,1,-,1$;
6)$-,-,1,1$
Now for each combination you can replace pair of $-$ with permutation of two remaining numbers, this mean $3,4$ or $4,3$. For first combination $1,1,-,-$: $1,1,3,4$ and $1,1,4,3$. And, therefore, $6\cdot{2}=12$.

Answer 6

For those less mathematically inclined, here are all 36 combinations for a 4 digit pin, using 3 digits, where 1 digit can be repeated. This might be useful for proving it to someone without having to explain permutations and combinations:

AABC
AACB
ABAC
ABCA
ACAB
ACBA
BAAC
BACA
BCAA
CAAB
CABA
CBAA

ABBC
ABCB
ACBB
BABC
BACB
BBAC
BBCA
BCAB
BCBA
CABB
CBAB
CBBA

ABCC
ACBC
ACCB
BACC
BCAC
BCCA
CABC
CACB
CBAC
CBCA
CCAB
CCBA