How many permutations can be made with digits 1-9?

[kakab00]

Homework Statement

http://img512.imageshack.us/img512/9990/untitledsm9.png

Homework Equations

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

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.

 

[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.

 

[kakab00]

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.

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

 

[nrqed]

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

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.

 

[kakab00]

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.

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

 

[nrqed]

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

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

 

[kakab00]

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

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

 

[Dick]

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

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.

 

[kakab00]

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 ways to remove 1 digit?

 

[Dick]

9 ways to remove 1 digit?

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

 

[kakab00]

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

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?

 

[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.

 

[nrqed]

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?

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.

 

[NateTG]

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?

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.

 

[kakab00]

@ : nrqed

Yeah, i got the reasoning behind it

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.

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

 

[Dick]

@ : nrqed

Yeah, i got the reasoning behind it



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

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.

 

[kakab00]

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.

so you mean the 2 choices are actually

a) to be included
b) to not be included

 

[Dick]

That's it exactly.

 

[kakab00]

That's it exactly.

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