2
$\begingroup$

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}.$

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

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.)

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

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}$.

$\endgroup$
3
$\begingroup$

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}$

$\endgroup$

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.