This thing is confusing me for a long time and hence I am asking it here.
We have a given set of numbers $$ X = \{1,2,3,4,5\} $$
and we want to form a $4$- digit number of the form $aaac$(this is just symbolic; I want all the arrangements of this form for e.g. $aaca$ etc). (I know that such questions' answers do exist on MSE, but my doubt/ confusion is pertinent to something extraneous to such questions.)
To make such a number the first approach that we can induce in our solution is that of using simple combination technique and choose two numbers out of the set of $5$ numbers. This can be done in the following way:
$$\binom{5}{2} \cdot \frac {4!}{3!}=40 $$
That seems fine as far as the combination formula is confirmed.
Let us now take a naive approach and pretend as if we don't know the combination formula.
Here we use the gap method:
Let us make one of our configuration as:
$$\fbox{a} \fbox{a} \fbox{a} \fbox{c}$$
Here $a$ can be chosed in $5$ ways and $c$ can be chosen in $4$ ways
Total ways to make $aaac$ configuration $=5 \cdot 1\cdot 1\cdot 4 = 20$ ways
Every such configuration now needs to be permuted since we want $aaca$ etc. also. To permute such a configuration, we can write:
$$ \frac {4!}{3!} \cdot 20 = 80$$ which is exactly double that of the answer obtained from the combination formula (which makes be believe that either I have double counted things or I have snubbed some of the arrangements).
Now let us try to think about some cases manually:
Case $1$: When $a=1$
The cases are: $$\{1112\}, \{1121\},\{1211\},\{2111\},\{1113\},\{1131\},\{1311\},\{3111\},\{1114\},\{1141\},\{1411\},\{4111\},\{1115\},\{1151\},\{1511\},\{5111\}$$
Thus there are $16$ configurations regarding $1$ only which means that for all the whole set, there are $16 \cdot 5 =80$ configurations.
This proves that the problem is with my usage of the combination formula. Can anybody tell me how my usage of combination formula comes out to be fallacious?
Best Answer
The problem here is that $a$ and $c$ have two different roles. Therefore simply using $\binom{5}{2}$ will not work, as it denotes the number of ways of picking two elements out of five, but without distinguishing between them. What you can do is $$\binom{5}{2}\cdot2\cdot4 = 80\ ,$$ where we piked two numbers in $\{1,2,3,4,5\}$ using $\binom{5}{2}$, then we choose which one to assign to $a$ and which one to $c$ (whence the factor $2$), and finally we choose where to put the $c$ (the factor $4$).