Permutations of digits

1. Jun 13, 2007

kakab00

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

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. 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 :!!)