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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/