How many $5$ digit numbers can be formed from the integers $\{1,2,...,9\}$ if no digit can appear more than twice.(for example 41434 is not allowed)
My approach is : Since, $max $ 2$ digits can repeat: $=9\times9\times8\times7\times6$
Total Numbers $=27216$.
My Questions:
1) Is this approach correct?
2) Do we need to add the total distinct digit numbers or it is already included. Please advise best ways to solve these type of questions.
Without the restriction, the answer would be $9^5$.
For every way to distribute $3$, $4$ and $5$ digits over the five positions, we have to exclude all numbers with those positions being fixed to any of the nine digits.
Thus the final answer is
$$ 9^5 - 9 \times \binom{5}{3} \times 8^2 - 9 \times \binom{5}{4} \times 8^1 - 9 \times \binom{5}{5} \times 8^0 = 52920 $$
The 5 digits reminded me of poker ! Instead of cards, we choose #s, and we permute the "hands"
Two Pairs: $2-2-1:{9\choose 2}\cdot{7\choose 1}\cdot 5!/(2!2!)= 7560$
One Pair: $2-1-1-1: {9\choose 1}\cdot{8\choose3}\cdot 5!/2! = 30,240$
No Pair: $1-1-1-1-1: {9\choose 5}\cdot5!= 15,120$
Add to get answer = 52,920
It may be better to count how many do repeat at least three of the same, since every number repeats at most one digit more than two times this is easy.
How many numbers repeat the digit $1$ at least three times?
If there are exactly $3$ ones there are $\binom{5}{3}$ ways to choose the positions of the ones and then $8\cdot8$ ways to fill the other positions, so $10\cdot64$ total.
If there are four ones there are $5$ ways to choose the position of the other digit and then $8$ options for that digit, so $40$ total.
If there are $5$ ones it is clearly only one option.
Hence there are $640+40+1=681$ that have at least three ones. Hence there are $9\cdot681=6129$ that repeat a digit more than twice.
Hence there are $9^5-6129=52920$ that do not.
