# 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.

• Your answer is basically $24$, since you have $3^3 = 27$ possibilities totally, but you have to remove $111,222,333$, so that gives you $24$. – астон вілла олоф мэллбэрг Oct 10 '16 at 9:31
• Yeah thats one of the ways i thought about it thank you – maged rifaat Oct 10 '16 at 17:12

## 1 Answer

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??

• The formula is pretty complicated for me if you can tell me what k and n stand for in the problem i mentioned so i can generalise it to myself.Thanks for your answer. – maged rifaat Oct 10 '16 at 17:14
• What do you mean what n stands for? It is the number of digits. And k is the number of pairs of same digits so if you have 9 digits then k is at most 4, like 112233445. that's what [n/2] stands for cos 9/2=4.5 – Djura Marinkov Oct 10 '16 at 17:42
• Oh i thought no. Of digits was n/2 thanks for your answer but just to make sure i understand k in my mentioned problem will be 1 and n will be 3 right? – maged rifaat Oct 10 '16 at 20:36
• After multiple reading your answer your approach seem to be right although i am having trouble linking between permutations and the summation formula (still learning,my bad) so i'll mark it as the answer Thanks for your time – maged rifaat Oct 10 '16 at 21:10