Consider all the 5 digit numbers where each of the digits is chosen from the set $\{1,2,3,4\}$. The number of numbers which contain all the four digits, is....

Now, I attempted this question in two different ways.

First is as follows,

$$C(4,1)\frac{5!}{2!} = \frac{4!5!}{3!1!2!} = 240$$ which indicates selection of one number from the set and then arranging it with the others.

And the second is as follows,

$$C(5,4)4! \times 4 = 480$$ which indicates the selection of four spots from the five digit number and arranging the four digits on them and then multiplying it by four as the spot left can take four forms.

Now the first solution gives right answer while the second doesn't, and I am not getting what's wrong with it. So, I want you guys to point that out for me.


The second solution double counts. It considers the two choices

  • Pick the four last spots and arrange the digits in increasing order, then put a $1$ in the remiaining spot
  • Pick the first and three last spots, and arrange the digits in increasing order there, then put a $1$ in the remaining spot

as two different choices, even though they both end up with $11234$.


There are two ways to arrive at e.g. $23431$ if we apply the second method:

  • $\begin{array}{ccccc} 2 & 3 & 4 & \star & 1\end{array}$ followed by end result $\begin{array}{ccccc} 2 & 3 & 4 & 3 & 1\end{array}$
  • $\begin{array}{ccccc} 2 & \star & 4 & 3 & 1\end{array}$ followed by end result $\begin{array}{ccccc} 2 & 3 & 4 & 3 & 1\end{array}$

This is a great example of how you can use the Twelvefold Way to avoid the risk of mis-analyzing a standard problem.

You are looking for the number of surjections with a domain of five elements (the place values) and a codomain of four elements (the digits). This is $4!\{^5_4\}=24\cdot10=240$, where the curly braces denote a Stirling number of the second kind.


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.