0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – астон вілла олоф мэллбэрг Oct 10 '16 at 9:31
  • $\begingroup$ Yeah thats one of the ways i thought about it thank you $\endgroup$ – maged rifaat Oct 10 '16 at 17:12
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – maged rifaat Oct 10 '16 at 17:14
  • $\begingroup$ 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 $\endgroup$ – Djura Marinkov Oct 10 '16 at 17:42
  • $\begingroup$ 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? $\endgroup$ – maged rifaat Oct 10 '16 at 20:36
  • $\begingroup$ 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 $\endgroup$ – maged rifaat Oct 10 '16 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.