Digits on the rise

[bonanova]

What do 15 489 1256 and 24578 have in common?

They are positive integers whose digits are strictly increasing left to right.

How many of them are there?

[Dariusray]

Please clarify if you mean

1. how many positive increasing-digit integers in {the set of all possible digit combinations in the stated problem} or
2. how many positive increasing-digit integers in {the set of all positive integers}

(I have a feeling it's the latter option...)

Edited October 12, 2013 by Dariusray

[bonanova]

Correct. The latter: positive integers whose digits are strictly increasing left to right.

[Dariusray]

First, my thinking about some restrictions for the strictly-increasing-digit integers:

*No numbers may have a zero digit (beginning zeroes disappear and any other position of zero ruins the strictly-increasing pattern)
*No single-digit integers (not technically a digit increase)
*The highest integer with [n] digits must start with [10-n] digit (highest 2-digit number must start with 8 and highest 9-digit number must start with 1)

Now, a brute-force count (2-digit number starting with 8, plus those starting with 7, etc.) for 2-digit and 3-digit permutations revealed a pattern that a number with [n] digits will need [10-n] addends to result in the total count of permutations...

Once I began the first few addends in my brute-force count for 4-digit permutations, I saw that aligning the addends revealed a vertical pattern that increased my new addends by the counts I had for my previous [n]-digit permutations. (This pattern is much easier for me to visualize than to explain)...

Once I saw the two patterns, I found it much easier to compute with far less brute force (I wish I could make a grid here for alignment):

2-digit integers==>(1+2+3+4+5+6+7+8+9) permutations==> 45 valid integers
3-digit integers==>(1+3+6+10+15+21+28) permutations==>84 valid integers [saw horiz. pattern here; # of addends decreased to 7]
4-digit integers==>(1+4+9+16+25+36) permutations==>91 valid integers [saw vert. pattern here; # of addends decreased to 6 and values increased by 3, then 6, then 10, etc. from counts directly above]
5-digit integers==>(1+5+13+25+41) permutations==>85 valid permutations [now 5 addends & increases of 1, 4, 9, etc. from counts directly above]
6-digit integers==>(1+6+18+38) permutation==>63 valid permutations [continuing horiz. & vert. patterns from here]
7-digit integers==>(1+7+24) permutations==>32 valid permutations
8-digit integers==>(1+8) permutations==>9 valid permutations
9-digit integers==>(1) valid permutation

TOTAL strictly-increasing-digit integers possible==>(45+84+91+85+63+32+9+1)==>410

Provided my patterned computations are accurate, I believe there are 410 valid integers

[jamieg]

First group it by number of digits (so group 1 will be 1 digit, group 2 will be 2 digits, etc). Then each group will be the functional equivalent of asking, "what are the possible combinatorics for n numbers?" where n is the group number. The reason for this is that any combination of (non-repeating) digits can be ordered from lowest to greatest, and the combination function (nCr) basically takes this into account (as opposed to a permutation, in which the order of items creates unique possibilities). So the final solution will be

SUM (from n=1 to n=9) of 9Cn

=511

[bonanova]

There's an even simpler observation that immediately gives the correct answer.

[jamieg]

There's an even simpler observation that immediately gives the correct answer.

I assumed there is,

2

⁹-1

, but I'm not sure right now why that is.

[bonanova]

There's an even simpler observation that immediately gives the correct answer.

I assumed there is,

2

⁹-1

, but I'm not sure right now why that is.

The power set (the set of all subsets) of a set of n objects has size 2ⁿ. For 9 digits, n=9. Then subtract off the empty set.