Consider all the six digit numbers that can be formed using the digits 1, 2, 3, 4, 5 and 6, each digit being used exactly once. Each of such six digit numbers have the property that for each digit, not more than two digits smaller than that digit appear to the right of that digit.

The examples of such numbers are 315426, 135462, 234651 ect. Number of the six digit numbers having desired property is:

  • $\begingroup$ I don't know even how to start solving this problem. no hint or idea in my mind. $\endgroup$ – Priyanka Vithani Jul 12 '17 at 13:09
  • $\begingroup$ question might be phrased wrong but what did you try ? $\endgroup$ – user451844 Jul 12 '17 at 13:10
  • $\begingroup$ counterexample 654321 . $\endgroup$ – user451844 Jul 12 '17 at 13:22
  • $\begingroup$ @RoddyMacPhee I think the OP wants to count the numbers with that property, not disprove the statement that all numbers have that property. $\endgroup$ – Arthur Jul 12 '17 at 13:28
  • 1
    $\begingroup$ Judging from your comments to the posted solutions below, I think we need clarity in the definition. All the solvers (and I ) read the condition this way: a good string has the property for each digit, $1,\cdots, 6$ , at most two digits to the right of it are smaller than it. Thus $234651$ is good. Let's check: The first digit to check is $4$...the digits less than $4$ are $3,2,1$ and of these only $1$ is to the right. East to check $5,6$ as well. If you are reading the definition differently, then you should clarify. $\endgroup$ – lulu Jul 12 '17 at 14:10

Hint: How many different places can the $6$ go? Once the $6$ is placed, how many different places can the $5$ go? Then keep going.


Let it be that $s_n$ denotes the number when this is asked for digits $1,2,\dots,n$. Then for $n>3$ the following relation can be deduced:$$s_n=3s_{n-1}$$

This because as utmost left digit only $1,2,3$ are allowed, and if the utmost left digit is placed then the same problem arises for $1$ digit less.

Next to that it also obvious that $s_3=3!=6$ so we arrive at:$$s_6=3s_5=3^2s_4=3^3s_3=3^3\cdot6=162$$

  • $\begingroup$ sorry but i didn't understand what you want to say. $\endgroup$ – Priyanka Vithani Jul 12 '17 at 13:39
  • $\begingroup$ Same solution, but derived differently: The largest digit ($n$) must be one of the last three digits. Then: There are bijections between the five-digit numbers formed with 1, 2, 3, 4, 5 that have the property and the six-digit numbers that have the property, with 6 in the last position. Also bijection to the six-digit numbers that have the property, with 6 in the fifth position. And the same with 6 in the fourth position. So $s_6=3s_5$, etc. $\endgroup$ – mathguy Jul 12 '17 at 13:39
  • $\begingroup$ @PriyankaVithani Do you agree that the utmost left digit can only be one of $1,2,3$? $\endgroup$ – drhab Jul 12 '17 at 13:43
  • $\begingroup$ but 654321 has the desired property $\endgroup$ – Priyanka Vithani Jul 12 '17 at 13:46
  • $\begingroup$ What makes you think that? First digit of $654321$ is $6$ and there are $5$ smaller digits at the right of that digit. At most $2$ are allowed. $\endgroup$ – drhab Jul 12 '17 at 13:49

Following the hint of @Artur
6 can be only at one of the last three places. 3 possibilities
Irrespective of where 6 is 5 can also come only in one of the last 3 remaining places.
Continuing similarly we get
Total number of possibilities are: $3^4\times2=162$


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.