# How many five-digit numbers can be formed using the digits 1-9 which have at least three identical digits?

How many five-digit nos. can be formed using the digits 1-9 having at least three identical digits?

My attempt:

Total no. of possible nos. with no restrictions $=9^5$

No. of numbers having two identical digits$=9\times 8^4$

Hence the answer should be

$( 9^5)-(9\times 8^4) = 22185$

Is this correct? If not then please suggest alternate method.....Thanks in advance!!

• You've forgotten to subtract the possibilities with all different digits. – Arthur Nov 3 '16 at 16:38
• Anything else that I missed out? I think the no. of such nos. will be equal to 9×8×7×6×5.....right? – SirXYZ Nov 3 '16 at 16:41
• The number of possible five-digit numbers with no restrictions is $5^9$. – Namaste Nov 3 '16 at 16:41
• Thats surely incorrect @ amWhy...It is 9^5. – SirXYZ Nov 3 '16 at 16:42
• Math SE is unusually quite today....seeing only 1 out of every 6-7 questions being answered. Unfortunately....I cant help....I dont much math myself!! Hahaha ... Note: This comment is is no way related to the question above. – SirXYZ Nov 3 '16 at 16:54

First approach: Pick which three spots host the identical digits; there are $\binom53$ ways to do this. Fill those three spots in one of $9$ ways, and then fill the other two spots in any of $9$ ways. Thus, $\binom53\times 9^3$

Problem with this approach: the number $12222$ has been counted $4$ times, once as $1\color{red}{222}2$, once as $1\color{red}{22}2\color{red}{2}$, once as $1\color{red}{2}2\color{red}{22}$, and once as $12\color{red}{222}$. Similarly, a number such as $44444$ has been overcounted by a factor of $\binom53$.

This can be fixed by subtracting out the repetitions. There are $5\times 9\times 8$ numbers with exactly $4$ digits identical, and $9$ numbers with exactly $5$ digits identical.

Thus: $\binom53\times 9^3 - (5\times 9\times 8)\times(4-1) - 9\times\left(\binom53 - 1\right)$

This comes out to $7290 - 1080 - 81 = 6129$

Doublecheck: Count the numbers with exactly $3$ identical digits, then the ones with exactly $4$, then the ones with exactly $5$:

$\binom53\times 9\times 8\times 8 + \binom54\times 9\times 8 + 9$

which comes out to: $5760 + 360 + 9 = 6129$

• Thanks for the help!! Your doublecheck approach is actually the shortest method to solve.... – SirXYZ Nov 3 '16 at 17:05
• Yeah, I'm not sure why I didn't think of it first. – G Tony Jacobs Nov 3 '16 at 17:05
• Python script shows that the answer is $7371$, which means your anwer is wrong (and so is mine). – barak manos Nov 3 '16 at 17:13
• Or else, Python script is wrong. – G Tony Jacobs Nov 3 '16 at 17:13
• How did you code it, exactly? – G Tony Jacobs Nov 3 '16 at 17:13