Posted 12 Oct 2013 · Report post 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? 0 Share this post Link to post Share on other sites

0 Posted 12 Oct 2013 (edited) · Report post Please clarify if you mean how many positive increasing-digit integers in {the set of all possible digit combinations in the stated problem} or how many positive increasing-digit integers in {the set of all positive integers} (I have a feeling it's the latter option...) Edited 12 Oct 2013 by Dariusray 0 Share this post Link to post Share on other sites

0 Posted 12 Oct 2013 · Report post Correct. The latter: positive integers whose digits are strictly increasing left to right. 0 Share this post Link to post Share on other sites

0 Posted 12 Oct 2013 · Report post 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 0 Share this post Link to post Share on other sites

0 Posted 12 Oct 2013 · Report post 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 0 Share this post Link to post Share on other sites

0 Posted 12 Oct 2013 · Report post There's an even simpler observation that immediately gives the correct answer. 0 Share this post Link to post Share on other sites

0 Posted 13 Oct 2013 · Report post There's an even simpler observation that immediately gives the correct answer. I assumed there is, 2^{9}-1, but I'm not sure right now why that is. 0 Share this post Link to post Share on other sites

0 Posted 13 Oct 2013 · Report post There's an even simpler observation that immediately gives the correct answer. I assumed there is, 2^{9}-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^{n}. For 9 digits, n=9. Then subtract off the empty set. 0 Share this post Link to post Share on other sites

Posted · Report post

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?

## Share this post

## Link to post

## Share on other sites