How many are there?

[Barcallica]

How many natural numbers are there, whose digits increase left to right? (this is from a book, so some of you might already know this one)

[bonanova]

Let's disallow leading zeros - e.g. disallow 0123456789, permitting only 9 digits.
Then we start with 123456789 (no digits missing) - 1
Then go to numbers like 12_456789 (one digit missing) - 9
Proceeding to 12_456_89 (two digits missing) and so forth.

The answer immediately becomes 2⁹. Why?

 

Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit.

 

Since there are 2ⁿ n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers)

there are 2⁹ nine-digit binaries, and thus 2⁹ natural numbers with (strictly) increasing digits.

[bonanova]

Since the natural numbers are countable, any subset of them can be no more than countable.

Here is a countably infinite subset of those whose digits increase left to right:

1, 12, 123, 1234, ... ah, we have to stop at 123456789.

Assuming strict increase and disallowing 1, 11, 12, 112, 122, 123, and numbers like that with repeats in them.

OK so it's finite, and they are of the form 123456789 with various digits removed.

I'll think about it.

[Perhaps check it again]

bonanova,

 

I see no sense in you disallowing 12 or 123, because each of those numbers have strict increases

in their digits.

[Barcallica]

bonanova,

 

I see no sense in you disallowing 12 or 123, because each of those numbers have strict increases

in their digits.

 

He didn't disallow 12 or 24, he correctly disallowed 112, 224 etc. Without strcict increase, the asnwer would be infinite.

[Perhaps check it again]

Barcallica.

 

the quoted pair of numbers in question are 12 and 123, not 12 and 24 as you stated.

 

 

And here is bonanova's pertinent quote so you can see to which am referring:

 

"Assuming strict increase and disallowing 1, 11, 12, 112, 122, 123, and numbers like that with repeats in them."

[bonanova]

[disallowing ... a sequence such as this .... that has ... ] numbers like that with repeats in them

 

You didn't understand?

 

Seriously?

[k-man]

Let's disallow leading zeros - e.g. disallow 0123456789, permitting only 9 digits.

Then we start with 123456789 (no digits missing) - 1

Then go to numbers like 12_456789 (one digit missing) - 9

Proceeding to 12_456_89 (two digits missing) and so forth.

The answer immediately becomes 2⁹. Why?

 

Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit.

 

Since there are 2ⁿ n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers)

there are 2⁹ nine-digit binaries, and thus 2⁹ natural numbers with (strictly) increasing digits.

 

That's a cool solution, but a small correction is required...

 

Zero is not a natural number, so if single digit numbers are permitted then the answer is 2

⁹-1. Otherwise, 2⁹-10.

[Perhaps check it again]

bonanova,

 

you communicated wrong.  You included 12 and 123.  Those are strictly numbers and not parts of sequences of numbers.

 

If you wanted numbers that began with those digits, then you need to put ellipses after those, as in:

 

"Assuming strict increase and disallowing 1..., 11..., 12..., 112..., 122..., 123..., and numbers like that with repeats in them."

 

Next time you can type out the word "sequence" or put in the ellipses so you don't pass on the wrong information.

 

 

And no single digit numbers should be included, because they do not consist of numbers where the digits

are increasing from left to right.

Edited August 22, 2014 by Perhaps check it again

[bonanova]

 

Let's disallow leading zeros - e.g. disallow 0123456789, permitting only 9 digits.

Then we start with 123456789 (no digits missing) - 1

Then go to numbers like 12_456789 (one digit missing) - 9

Proceeding to 12_456_89 (two digits missing) and so forth.

The answer immediately becomes 2⁹. Why?

 

Because we can associate 12_456_89 with the binary number 110111011, where 0 shows a missing digit.

 

Since there are 2ⁿ n-digit binary numbers (n=2: 00 01 10 11 = 4 numbers)

there are 2⁹ nine-digit binaries, and thus 2⁹ natural numbers with (strictly) increasing digits.

 

That's a cool solution, but a small correction is required...

 

Zero is not a natural number, so if single digit numbers are permitted then the answer is 2

⁹-1. Otherwise, 2⁹-10.

 

 

You're right. Good catch.