How many numbers consist of $4$ digits $a$, $b$, $c$, and $d$ such that
$$a\leq b\leq c\leq d$$
a is thousands, b is hundreds, c is tens, and d is unit
What i'm thinking is $6 \times6\times 6\times 6$, but it's wrong.
The multiple choice is :
a) $495$ numbers
b) $385$ numbers
c) $275$ numbers
d) $165$ numbers
e) $55$ numbers
Which one is the answer?
Consider the following table.
$$\begin{array}{|c|c|c|c|c|}\hline 9&9&9&9&\color{blue}9\\\hline 8&8&8&8&8\\\hline 7&7&7&7&7\\\hline 6&6&6&6&6\\\hline 5&5&5&5&5\\\hline4 &4&4&4&4\\\hline 3&3&3&3&3\\\hline 2&2&2&2&2\\\hline 1&1&1&1&1\\\hline \color{red}0&0&0&0&0 \\\hline\end{array}$$
We start at the square with the red zero and we want to get to the square with the blue nine. At each step, we can only walk one step to the right or one step in the upwards direction. Let $a$, $b$, $c$, and $d$ be the labels of the last squares we stay in the first column, the second column, the third column, and the forth column respectively.
If $R$ denotes a step that we walk to the right and $U$ denotes a step that we walk upwards, then we can identify our walk with a sequence of $4$ $R$s and $9$ $U$s. For example, $RUUURRUUUURUU$ gives $(a,b,c,d)=(0,3,3,7)$. Likewise, $UURURUUUUURUR$ gives $(a,b,c,d)=(2,3,8,9)$.
If $a$ is allowed to be $0$, the first step can be anything. Therefore, the job can be done in $$\frac{(4+9)!}{4!9!}=\frac{13\cdot 12\cdot 11\cdot 10}{4\cdot 3\cdot 2\cdot 1}=715$$ ways. If $a$ cannot be $0$, then the first step must be $U$. Therefore, the job can be done in $$\frac{(4+8)!}{4!8!}=\frac{12\cdot 11\cdot 10\cdot 9}{4\cdot 3\cdot 2\cdot 1}=495$$ ways.