1
$\begingroup$

I'm working on the problem "how many $8$ digit numbers can be formed with the digits $0-9$ where $0$ can also come in the first place with exactly $2$ identical pairs "

So I have $2$ ways to do it, and $1$ is wrong and I'm struggling to understand how to fix it if possible at all.

First way: Each number satisfying the condition of the problem will have $6$ unique digits from the set 0,... 10 and those digits can be chosen in $\binom{10}{6}$ ways. Out of those $6$ digits the $2$ that will form the pair can be chosen in $\binom{6}{2}$ ways. Finally the number of permutations of $8$ characters with $2$ pairs is $\frac{8!}{2! 2!}$ Multiplying those yields the answer.

2nd way: The number of permutations of a sequence AABBCEDF is $\frac{8!}{2! 2!}$. Now A can be choosen in 10 ways, B in 9 ways, E in 8 ways etc to yield the number $\frac{8!}{2! 2!}*10*9*8*7*6*5$ I understand how I'm double counting here but I want to know if there is an approach to this problem along this line of thought. Can I resolve the double counting? This answer comes out $48$ times larger than the correct first answer i.e in my calculation im missing a factor of $\frac{1}{48}$.

$\endgroup$
5
  • 1
    $\begingroup$ Hint: $48 = 2!\times 4!$. Further Hint: AABBCDEF where $1$ is put in place of the $A$'s and $2$ in place of the $B$'s and $3,4,5,6$ in place of $C,D,E,F$ respectively results in $11223456$ while BBAAFEDC where instead $2$ is put in place of the $A$'s and $1$ in place of the $B$'s and $6,5,4,3$ in place of $C,D,E,F$ respectively also results in $11223456$. $\endgroup$ – JMoravitz Sep 30 '19 at 18:33
  • $\begingroup$ Yup, I did figure out $48 = 2! \times 4!$ but I'm having trouble coming up with the mathematical explanation for it. I know it has to do with the permutation of block of $4$ of "AABB" - looking at it as a block of "XXXX" permuted with "CDEF" $\endgroup$ – Myro Sep 30 '19 at 18:52
  • $\begingroup$ @JMoravitz it has to do with extra permutations of $A_1A_2B_1B_2$ where $A_1 = A_2$ and $B_1 = B_2$ but im struggling with explaining it. I think we can permute this sequence in 4! ways among A and B and then since we can change between A and B we are also overcounting by an additional 2!. As in if the total number of permutations (with repetition, disreguarding equality) is $P_t$ then my answer $P$ is related as $P_t = P*2!*4!$ and $P_t = \frac{8!}{2! 2!}*10*9*8*7*6*5$ $\endgroup$ – Myro Sep 30 '19 at 19:43
  • $\begingroup$ Does $22245678$ count as one pair or two? $\endgroup$ – Andrew Chin Sep 30 '19 at 21:50
  • $\begingroup$ That doesnt meet the conditions of the problem, I'm looking for strings where there are 2 pairs of different digits and all other digits are distinct. $\endgroup$ – Myro Sep 30 '19 at 21:54
0
$\begingroup$

You do not need to make an ordered selection of the two digits that will appear twice or an ordered selection of the digits that will appear once since you have accounted for the order in which the digits appear in string by counting the $$\frac{8!}{2!2!}$$ permutations of the sequence AABBCDEF. This is what JMoravitz was hinting at in the comments.

We can choose the two digits that each appear twice in the string in $\binom{10}{2}$ ways. We can choose the four digits that each appear once in the string from the eight remaining digits in $\binom{8}{4}$ ways. Therefore, the number of eight-digit decimal strings in which exactly two digits appear twice and the rest of the digits appear once is $$\binom{10}{2}\binom{8}{4}\frac{8!}{2!2!}$$ Notice that $$10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = \binom{10}{2}\binom{8}{4} \cdot 2!4!$$ since $$\binom{10}{2}\binom{8}{4} \cdot 2!4! = \frac{10!}{2!8!} \cdot \frac{8!}{4!4!} \cdot 2!4! = \frac{10!}{4!} = 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4$$ By choosing the two numbers that appear twice in the string in order, you introduced an extra factor of $2!$; by choosing the four numbers that appear once in the string in order, you introduced an extra factor of $4!$. This is why your second answer was $2!4! = 48$ times your correct first answer.

$\endgroup$
1
  • 1
    $\begingroup$ Yeah, got it, thank you for the explanation :) $\endgroup$ – Myro Sep 30 '19 at 21:56

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.