+0  
 
0
1889
4
avatar

The numbers $1,2,3,4,5,6,7,8,9$ are arranged in a list so that each number is either greater than all the numbers that come before it or is less than all the numbers that come before it. For example, $4,5,6,3,2,7,1,8,9$ is one such list: notice that (for instance) the 6 is greater than all the numbers that come before it, and the 2 is less than all the numbers that come before it.

How many such lists of the numbers $1,2,3,4,5,6,7,8,9$ are possible?

Guest Mar 5, 2015

Best Answer 

 #3
avatar+889 
+11

The method is to look at the final digit, it has to be a 1 or a 9. (Choose an intermediate digit like 5 for example  and some of those to the left will be bigger, and some smaller.)   Similarly there will be two choices for the digit in the eighth position, two choices for the digit in the seventh position and so on.  There will only one choice left for the first digit, so 2 to the eight or 256 possibles

Bertie  Mar 6, 2015
 #1
avatar+93363 
+5

I have no idea where to start.

Some of the permutations are obvious but how you would count them I have no idea

Melody  Mar 5, 2015
 #2
avatar+26973 
+11

I conjecture that the answer is 256 (= 29-1) based on extrapolating results for sets {1,2}, {1,2,3} and {1,2,3,4}.  However, I have yet to find an elegant proof!

 

Partial reasoning:

If we have a number of arrangements for the set A = {1,...,n-1} then we can immediately get that many again for the set B = {1, ...,n} by simply putting n after all the arrangements for A.  Any extra arrangements for B must end in 1, because if they end in anything other than 1 or n, the end value will be bigger than 1 and smaller than n, violating the criteria.  It seems that there are just as many arrangements ending in 1 as there are ending in n, hence, since there are just 2 arrangements, for the set {1.2} each extra digit doubles the number of arrangements.  There must be a simple proof of the fact that there are just as many arrangements ending in 1 as there are ending in n (if it's true!), but I'm having a mental block trying to see it!

.

Alan  Mar 5, 2015
 #3
avatar+889 
+11
Best Answer

The method is to look at the final digit, it has to be a 1 or a 9. (Choose an intermediate digit like 5 for example  and some of those to the left will be bigger, and some smaller.)   Similarly there will be two choices for the digit in the eighth position, two choices for the digit in the seventh position and so on.  There will only one choice left for the first digit, so 2 to the eight or 256 possibles

Bertie  Mar 6, 2015
 #4
avatar+93363 
+5

Thanks Alan and Bertie,

I finally get it!  I think that I do anyway.   I never would of by myself.  Thanks!

Melody  Mar 7, 2015

42 Online Users

avatar
avatar
avatar
avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.