Posted October 12, 2013 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 October 12, 2013 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 October 12, 2013 (edited) 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 October 12, 2013 by Dariusray 0 Share this post Link to post Share on other sites

0 Posted October 12, 2013 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 October 12, 2013 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 October 12, 2013 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 October 13, 2013 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 October 13, 2013 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

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