QuestionA lock combination code is made up of $4$ numbers ($0-9$). Each number can occur at most twice, e.g. $4764$ would be allowed but not $4464$ as the number $4$ has occurred more than $2$ times.Therefore, how many possible combination codes are there?
I know that there are $10,000$ possible combinations if repetitions are allowed. However I'm unsure as to how to answer the question. Any help is greatly appreciated, thanks!
$\endgroup$ 52 Answers
$\begingroup$Here is a possible solution using the Principle of Inclusion/Exclusion:
$\textbf{Case 1}$ (digit is repeated $3$ times):
Choose the repeated digit in $10 \choose 1$ ways.
Choose the remaining digit in $9 \choose 1$ ways.
Order the digits in $\frac{4!}{3!} = 4$ ways.
$\textbf{Case 2}$ (digit is repeated $4$ times):
Choose the repeated digit in $10 \choose 1$ ways.
Order the digits in $\frac{4!}{4!} = 1$ way.
So the number of combinations that don't satisfy your constraint is $(10 * 9 * 4) + (10 * 1) = 370$. Subtracting these from the $10,000$ total combinations yields $\textbf{9,630}$ ways.
$\endgroup$ $\begingroup$Solution without using the Principle of Inclusion/Exclusion:
Add by number of pairs of numbers: $0$ pairs $+$ $1$ pair $+$ $2$ pairs
$=$ (pick $4$ of the $10$ order matters) $+$ (pick which will be repeated and where and the other $2$ numbers order matters) $+$ (pick number for each pair and location of first and second pair)
$=P(10,4) + 10*{{4}\choose{2}}*P(9,2) + {{10}\choose{2}}*{{4}\choose{2}}*1$
$=5040$ $+$ $4320$ $+$ $290$
$= 9630$
$\endgroup$
