# Find the number of five digit numbers of the form $d_1d_2d_3d_4d_5$ and satisfying $d_1<d_2\le d_3<d_4\le d_5.$

Find the number of five digit numbers of the form $d_1d_2d_3d_4d_5$ and satisfying $d_1<d_2\le d_3<d_4\le d_5.$

I considered $d_1,d_2,d_3,d_4,d_5$ as 5 baskets and these have to be filled with 0 to 9 apples.I found total ways as $\binom{10+5-1}{5-1}$ but the answer given is $\binom{11}{6}.$

• if $d_5$ is less than 9 so are all the rest etc. – user451844 Jul 23 '17 at 14:01

You're asked to choose integers $d_1, d_2, d_3, d_4, d_5$ such that $1 \le d_1 < d_2 \le d_3 < d_4 \le d_5 \le 9$.

Equivalently, you can choose $c_1, c_2, c_3, c_4, c_5$ such that $1 \le c_1 < c_2 < c_3 < c_4 < c_5 \le 11$. Then you can take $d_1 = c_1, d_2 = c_2, d_3 = c_3 - 1, d_4 = c_4 - 1, d_5 = c_5 - 2$ and they'll satisfy the original set of inequalities. This works because, for example, you have $c_2 < c_3$; so $d_2 < d_3 + 1$ and since $d_2$ and $d_3$ are integers you get $d_2 \le d_3$. The same basic argument works to show that $c_4 < c_5$ implies $d_4 \le d_5$.

So then if you have $(c_1, c_2, c_3, c_4, c_5) = (1, 3, 4, 6, 8)$ then you'll get $(d_1, d_2, d_3, d_4, d_5) = (1, 3, 3, 5, 6)$ and your five-digit number will be $13356$.

And since $c_1, c_2, c_3, c_4, c_5$ are all distinct and between 1 and 11, inclusive, there are ${11 \choose 5}$ ways to choose them.

(It's interesting that the answer key you have gives ${11 \choose 6}$. This is equal to ${11 \choose 5}$ but I don't see a "natural" way to get ${11 \choose 6}$ as the answer since you're choosing five numbers, not six.)

• This is "Method 2" from N. F. Taussig's answer, which I didn't realize when I answered the question. – Michael Lugo Jul 23 '17 at 20:41

Method 1: The leading digit must be at least $1$, so $d_1, d_2, d_3, d_4, d_5 \in \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

There are three possibilities:

1. All the digits are different: There are $\binom{9}{5}$ such cases since selecting five of the nine digits completely determines the number since $d_1 < d_2 < d_3 < d_4 < d_5$
2. Four different digits are used: There are $\binom{9}{4}$ such cases in which $d_2 = d_3$ since the repeated digit must be the second smallest digit selected. There are also $\binom{9}{4}$ such cases in which $d_4 = d_5$ since the repeated digit must be the largest digit selected. Thus, there are $2\binom{9}{4}$ such cases.
3. Three different digits are used: There are $\binom{9}{3}$ such cases since the two repeated digits must be the two largest digits selected.

Total: Since the three cases are disjoint, there are \begin{align*} \binom{9}{5} + 2\binom{9}{4} + \binom{9}{3} & = \binom{9}{5} + \binom{9}{4} + \binom{9}{4} + \binom{9}{3}\\ & = \binom{10}{5} + \binom{10}{4} && \text{by Pascal's Identity}\\ & = \binom{11}{5} && \text{by Pascal's Identity} \end{align*} numbers with the desired property.

Method 2: Since the leading digit must be at least $1$, $d_1, d_2, d_3, d_4, d_5 \in \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

We can set up a bijection between selections of five numbers from the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ satisfying $d_1 < d_2 \leq d_3 < d_4 \leq d_5$ and selections of five distinct elements $x_1, x_2, x_3, x_4, x_5$ of the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$ by setting $x_1 = d_1$, $x_2 = d_2$, $x_3 = d_3 + 1$, $x_4 = d_4 + 1$, and $x_5 = d_5 + 2$. For instance, the number $35579$ corresponds to the selection $\{3, 5, 6, 8, 11\}$. Hence, the number of five-digit numbers with the desired property is $\binom{11}{5}$.

Note that the $d_1$ cannot be zero and hence, none of the others can be.

We have four cases to consider:

1. $d_2 \lt d_3$ and $d_4 \lt d_5$: The number of ways of choosing 5 numbers out of 9 such that $d_1 \lt d_2 \lt d_3 \lt d_4 \lt d_5$ is $\binom{9}{5}$

2. $d_2 = d_3$ and $d_4 \lt d_5$: Number of ways is $\binom{9}{4}$

3. $d_2 \lt d_3$ and $d_4 = d_5$: Number of ways is $\binom{9}{4}$

4. $d_2 = d_3$ and $d_4 = d_5$: Number of ways is $\binom{9}{3}$

Adding them all up, we get $\binom{11}{6}$