1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Permutations of digits

  1. Jun 13, 2007 #1
    1. The problem statement, all variables and given/known data

    [​IMG]


    2. Relevant equations

    The permutation & combinations equation? I don't quite know how to type them out in here, but there's the calculator :rofl:

    3. The attempt at a solution

    Since the maximum number of integers a value can have would up up to 1000000000, there would a total of 1digit+2digit + 3digit+...+8digit numbers +9 digit numbers altogether. 10 digit numbers don't count as the last number would be 0.

    For the 9 digit nos, it would be just 123456789 which is 1 way, 8 digit: 12345678 or 23456789, but as the digits get smaller I'm confused and at a loss to what to do.

    Any help would be greatly appreciated.
     
  2. jcsd
  3. Jun 13, 2007 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    For 8 digits how about 13456789? I think you are undercounting. To do 8 digits right, figure out how many ways to remove one digit from your 9 digit number. I guess to do 7 you'll want to figure how many ways to remove 2. Etc.
     
  4. Jun 13, 2007 #3
    :eek:it indeed does seem i undercounted, but then for the values with lesser digits there would be a lot of ways to remove each number wouldn't it??
     
  5. Jun 14, 2007 #4

    nrqed

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    yes, but with the smart trick of Dick, it's trivial. For example, if you need to keep only 5 digits, you need to remove 4 digits from the initial 9 digits number. How many ways can you do this? Simply 9x8x7x6 = 9!/(5!)
    For a 2 digits number, you will have 9!/2! ways. It's that simple.
     
  6. Jun 14, 2007 #5
    hmm no, I thought you can' t remove just any digits, since the digits have to be in ascending order.
     
  7. Jun 14, 2007 #6

    nrqed

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    but you start with 123456789 !!!!! So you can remove any digit!!
    That is the trick!
     
  8. Jun 14, 2007 #7
    so you mean it should be something like 9! + 9!/8! + 9!/7! + 9!/6! + 9!/5! + 9!/4! + 9!/3! + 9!/2! + 9(there are only 9 1-digit numbers) ?
     
  9. Jun 14, 2007 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I have a nine digit number. I wish to remove one digit. How many ways to do it? The answer is certainly NOT 9!. You didn't undercount that much.
     
  10. Jun 14, 2007 #9
    9 ways to remove 1 digit?
     
  11. Jun 14, 2007 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes. How many ways to remove 2? Are you using permutations or combinations?
     
  12. Jun 14, 2007 #11
    Combinations for this..since they have to be strictly ascending you can't change the order of the digits.

    ans: 9 + 9C1 + 9C2 + 9C3 + 9C4 + 9C5 + 9C6 + 9C7 + 9C8 + 9C9 =511

    It seems to tally with the answer I have, but somebody else told me that 2^9 -1 also works. Any idea how he got that?
     
  13. Jun 14, 2007 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You've got an extra 9 in there. 9C1=9. 'somebody' did it by counting all subsets of the nine digits and excluding the empty set. There is also an identity that says that the sum over k=0 to k=n of nCk=2^n.
     
  14. Jun 14, 2007 #13

    nrqed

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Sory about my previous post, I forgot to type in the division by the remaining factorials (to get a 5 gitis number, there are of course 9!/(5! 4!) ways since it does not matter in what order the digits are removed.

    As Dick pointed out, you have a 9 too many in your formula (but that's surely a typo because without that 9, the sum si indeed 511).

    Just to nitpick: it makes actually more sense to write

    9C0 + 9C1 + 9C2 + ... 9C8

    as opposed to what you wrote (again, assuming you remove the first 9).
    I do know that 9C0 is the same as 9C9 but the way you wrote it sounded like you were considering the case of removing all 9 digits which of course you can't do since it leaves no number. On the other hand, one possibility is to remove no digit at all, leaving 9C0 = 1 possibility, obviousy.

    Again, I understand that 9C0 + 9C1 + ... 9C8 is numerically equal to
    9C1 + .... 9C9 . I just want to make sure that the reasoning behind the formula is clear.
     
  15. Jun 14, 2007 #14

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    There are nine digits, for each digit it's either in the number, or not. That makes [itex]2^9[/itex] possibilities, the '-1' is because the 'empty list' is not an accepted answer.
     
  16. Jun 14, 2007 #15
    @ : nrqed

    Yeah, i got the reasoning behind it

    What I don't get is where did the 2 come from in the first place?
     
  17. Jun 14, 2007 #16

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    There are 2 choices for each digit. Is it in the number or not. So all possibilities are 2^9 including a 'number' with no digits.
     
  18. Jun 15, 2007 #17
    so you mean the 2 choices are actually

    a) to be included
    b) to not be included
     
  19. Jun 15, 2007 #18

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That's it exactly.
     
  20. Jun 15, 2007 #19
    cool I got it, thanks for all of your help :!!)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Permutations of digits
  1. Permutation proof (Replies: 7)

Loading...