bonanova Posted October 12, 2013 Report Share 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? Quote Link to comment Share on other sites More sharing options...

0 jamieg Posted October 12, 2013 Report Share 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 Quote Link to comment Share on other sites More sharing options...

0 Dariusray Posted October 12, 2013 Report Share 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 Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted October 12, 2013 Author Report Share Posted October 12, 2013 Correct. The latter: positive integers whose digits are strictly increasing left to right. Quote Link to comment Share on other sites More sharing options...

0 Dariusray Posted October 12, 2013 Report Share 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 Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted October 12, 2013 Author Report Share Posted October 12, 2013 There's an even simpler observation that immediately gives the correct answer. Quote Link to comment Share on other sites More sharing options...

0 jamieg Posted October 13, 2013 Report Share 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. Quote Link to comment Share on other sites More sharing options...

0 bonanova Posted October 13, 2013 Author Report Share 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. Quote Link to comment Share on other sites More sharing options...

## Question

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

## Link to comment

## Share on other sites

## 7 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.