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.
Asked
Active
Viewed 1,173 times
0
-
3Your 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$. – Sarvesh Ravichandran Iyer Oct 10 '16 at 09:31
-
Yeah thats one of the ways i thought about it thank you – maged rifaat Oct 10 '16 at 17:12
1 Answers
0
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??
Vinyl_cape_jawa
- 4,794
Djura Marinkov
- 2,595
-
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