Q:

How many $n$ digit numbers formed from $n$ digits where a digit can be repeated twice?

So I had a problem saying how many $3$ digit numbers can be formed from the numbers $\{1,2,3\}$ where a digit can be repeated twice and the written answer was $18$.
When I tried to solve it myself by tree diagram and counting it was $24$ numbers. Then I tried by the techniques I know so I said the first digit would have $3$ possibilities the second one is also $3$ as we can repeat and the third one will be $2$ possibilities. So it will be $3\cdot 3\cdot 2=18$ but after some thinking I realised I am forgetting the numbers where there is no repetition which will be $3!$ added to the $18$ which make it $24$.
My question is am I right?And is there like a law for this?
Thanks in advance.

A:

For general $n$ you can have $k$ pairs of same digits $k$ in $\{0,1,...,[n/2]\}$
You have to pick $n-2k$ digits that would appear once, then among rest of $2k$ digits you have to pick $k$ which will appear twice. Now you have to permute all those digits, it will be $n!/2^k$ cos you have to divide by $2$ for each pair, so total will be $$\sum_{k=0}^{[n/2]}(\frac{n!}{(2k)!(n-2k)!}\frac{(2k)!}{k!k!})\frac{n!}{2^k}=\sum_{k=0}^{[n/2]}\frac{n!^2}{(k)!^2(n-2k)!2^k}$$
Maybe someone can handle this sum to get a simple formula??

