# Permutations of digits

1. Jun 13, 2007

### kakab00

1. The problem statement, all variables and given/known data

http://img512.imageshack.us/img512/9990/untitledsm9.png [Broken]

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.

Last edited by a moderator: May 2, 2017
2. Jun 13, 2007

### Dick

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.

3. Jun 13, 2007

### kakab00

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??

4. Jun 14, 2007

### nrqed

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.

5. Jun 14, 2007

### kakab00

hmm no, I thought you can' t remove just any digits, since the digits have to be in ascending order.

6. Jun 14, 2007

### nrqed

but you start with 123456789 !!!!! So you can remove any digit!!
That is the trick!

7. Jun 14, 2007

### kakab00

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) ?

8. Jun 14, 2007

### Dick

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.

9. Jun 14, 2007

### kakab00

9 ways to remove 1 digit?

10. Jun 14, 2007

### Dick

Yes. How many ways to remove 2? Are you using permutations or combinations?

11. Jun 14, 2007

### kakab00

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?

12. Jun 14, 2007

### Dick

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.

13. Jun 14, 2007

### nrqed

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.

14. Jun 14, 2007

### NateTG

There are nine digits, for each digit it's either in the number, or not. That makes $2^9$ possibilities, the '-1' is because the 'empty list' is not an accepted answer.

15. Jun 14, 2007

### kakab00

@ : nrqed

Yeah, i got the reasoning behind it

What I don't get is where did the 2 come from in the first place?

16. Jun 14, 2007

### Dick

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.

17. Jun 15, 2007

### kakab00

so you mean the 2 choices are actually

a) to be included
b) to not be included

18. Jun 15, 2007

### Dick

That's it exactly.

19. Jun 15, 2007

### kakab00

cool I got it, thanks for all of your help :!!)