How many $9-\text{digit}$ number can be formed by using the digits $1, 2, 3, 4, 5, 6, 7,8, 9$ so that each number has $7$ digits in such place where that digit is less than the next digit?
Example: In number $2314; \; 2, 1$ are two digits such that each of them is less than the next digit.

Source: BDMO 2015 , Dhaka regional

  • $\begingroup$ Exactly seven digits in such a place, or at least seven? Note that there are only eight digits with a successor, so there is only one nine-digit number where each of its first eight digits are followed by a greater digit. Thus, this question on its own makes only a small difference, but it might get you thinking down the right path. $\endgroup$ – Brian Tung Jan 3 '17 at 1:29
  • $\begingroup$ exactly $7$ digit $\endgroup$ – steinum Jan 3 '17 at 1:29
  • 3
    $\begingroup$ Right. So there is only one "downward step". What can you say about the digits before that downward step, and about the digits after it? $\endgroup$ – Brian Tung Jan 3 '17 at 1:30
  • $\begingroup$ I'll let you think about that for a while. If you haven't got it after some thinking, and no one writes up an answer, I'll sketch out a solution in a bit. $\endgroup$ – Brian Tung Jan 3 '17 at 1:32
  • $\begingroup$ Possible duplicate of Number of $n$-digit permutations with exactly $n-2$ digits smaller than the next $\endgroup$ – Rezwan Arefin Feb 2 '17 at 6:25

Consider the difference between each of the $8$ pair of digits in the $9$ digit number. $7$ digits are in such place where that digit is less than the next digit. So there must be ONLY ONE pair so that the difference is positive.
Now let this positive difference happen between $i^{th}$ and $(i+1)^{th}$ digit in the number. Now we can choose any set of $i$ numbers and arrange them in increasing order, and place other $9-i$ numbers after them, in order.
Since $i$ ranges from $1 \to 9-1 = 8$, so our final answer is -
$$\sum_{i = 1}^{8} \left\{\binom{9}{i}-1\right\} \\ \sum_{i = 1}^{8}\binom{9}{i} - 8\\ \sum_{i=0}^{9}\binom{9}{i} - \binom{9}{9} - \binom{9}{0} - 8\\ 2^9 - 10 = \color{red}{\boxed{502}}$$

BTW, I am also Bangladeshi ... This problem repeated in some other regional too, with different constrains. Like we need to make $8$-digit numbers from $\{1,2,\cdots,8\}$ such that $6$ of them are in that such place. Here the answer will be $2^8-9$


Given that the nine-digit number has exactly one point at which a digit's successor is less than itself, it can thus be divided into two parts, both of which are strictly ascending, neither of which is empty. (That is to say, the entire number isn't as a whole strictly ascending.)

What's more, you can construct the number in exactly this fashion: Select a subset of the nine digits, and let those digits, in ascending order, form the prefix of the number. Then put the remaining digits in ascending order, and those form the suffix of the number. There are $2^9 = 512$ different subsets, so there are at most that many ways to generate a satisfactory number.

However, there are a few subsets that won't work—namely, those subsets that are the $k$ smallest digits, for $k = 0$ to $9$. There are $10$ such non-satisfactory subsets, so the actual result should be $512-10 = 502$.


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.