What Number Falls on the 124th Position?

Date: 01/06/98 at 08:47:23
From: Kate
Subject: Combinatorics

There are 720 (or 6!) permutations of the digits 1,2,3,4,5,6. 
Suppose these permutations are arranged from smallest to largest 
numerical value, beginning with 123456 and ending with 654321:

  a. what number falls on the 124th position?
  b. what is the position of the number 321546?

Date: 01/06/98 at 13:10:33
From: Doctor Rob
Subject: Re: Combinatorics

  a. Among the 6! permutations, there are 5! = 120 beginning with 1.  
They would be numbered from 1 to 120. The next 120, including the 
124th, would begin with 2.
    
     Among the 5! permutations beginning with 2, there are 4! = 24,
including the 124th, which have second digit 1.

     Among the 4! permutations beginning with 21, there are 3! = 6,
including the 124th, which have third digit 3.

     Among the 3! permutations beginning with 213, there are 2! = 2 
with fourth digit 4 (numbers 121 and 122), 2 with fourth digit 5 
(numbers 123 and 124), and 2 with fourth digit 6 (numbers 125 and 
126). The 124th has fourth digit 5.

     Finally, among the 2! permutations beginning with 2135, there is 
one with 5th digit 4 (number 123) and one with 5th digit 6 (number 
124). The 124th is the latter one.
    
     Thus the 124th number is 213564.

This is related to the fact that

   124 - 1 = 123,
           = 1*5! + 1*2! + 1*1!
           = ((((1*5 + 0)*4 + 0)*3 + 1)*2 + 1)*1 + 0,
                 ^     ^      ^      ^      ^      ^
           <--> 100110,
           <--> 211221,

The last number is the recipe: 

   Take the 2nd smallest number, 2.  
   Take the 1st smallest number left, 1.  
   Take the 1st smallest number left, 3.
   Take the 2nd smallest number left, 5.  
   Take the 2nd smallest number left, 6.  
   Take the 1st smallest (and only) number left, 4.  
   This gives 213564.

 b. Reverse the above recipe:

    3,2,1,5,4,6 <--> 321211,
                <--> 210100,
                <--> ((((2*5 + 1)*4 + 0)*3 + 1)*2 + 0)*1 + 0,
                = 266,
                = 267 - 1,

so the number 321546 is the 267th on the list.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   

Date: 01/06/98 at 08:56:01
From: Kate
Subject: Combinatorics

How many integers between 1 and 10,000 have:

  a. exactly one 8 and one 9 as digits?
  b. at least one 8 and one 9 digits?

My attempt to answer:

a. If I use 8 for the ones digit and 9 for the tens digit, then I 
can't use it for the other digits any more. (1st possibility) 
Then if I reverse the order, 8 for the tens digit and 9 for the ones 
digit, I get another possibility. (2nd possibility). I can't go on 
doing this (trying 8 and 9 for all the digits). What formula could I 
use?

b. same thing as with a. I need a better formula!

Date: 01/06/98 at 14:20:59
From: Doctor Rob
Subject: Re: Combinatorics

Consider all the integers to have four digits, by inserting leading
zeroes if necessary. Make the identification 0000 <--> 10000.

 a. Place the 9 first, then the 8.  There are 4*3 = 12 ways to do 
that. The remaining two digits can be any of the other 8 digits, so 
there are 12*8^2 = 768 such integers.

 b. Count the ones with no 8 (9^4 - 6561 of them)(why?), the ones with
no 9 (9^4 = 6561 of them)(why?), and the ones with neither 8 nor 9 
(8^4 = 4096 of them). Then there are

   10^4 - 9^4 - 9^4 + 8^4 = 10000 - 6561 - 6561 + 4096,
                          = 974,

numbers satisfying these conditions.

Another approach. Consider cases based on the number of 8's and 9's:

   9's  8's  Others  Number
    1    1      2    [4!/(1!*1!*2!)]*8^2 = 768
    1    2      1    [4!/(1!*2!*1!)]*8^1 =  96
    1    3      0    [4!/(1!*3!*0!)]*8^0 =   4
    2    1      1    [4!/(2!*1!*1!)]*8^1 =  96
    2    2      0    [4!/(2!*2!*0!)]*8^0 =   6
    3    1      0    [4!/(3!*1!*0!)]*8^0 =   4
                                          -----
   Total                                   974

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/